mahaaoo
0%

JavaScript数据结构笔记-二叉树、二叉查找树

Posted on Edited on In

二叉树

二叉树是一种树形结构，它的特点是每个节点最多只有两个分支节点，一棵二叉树通常由根节点，分支节点，叶子节点组成。而每个分支节点也常常被称作为一棵子树。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
// 二叉树节点
class TreeNode {
  constructor(val) {
    this.value = val;
    this.left = null;
    this.right = null;
  }
}
// 二叉树
class Tree {
  constructor() {
    this.tree = null;
    this.size = 0;
  }
  // 向二叉树中添加一个元素
  // 顺序向树添加节点，通过广度优先遍历寻找左孩子或者右孩子缺失的节点，将新节点添加在这个节点上
  push = (item) => {
    if (typeof(item) == 'object') {
      item.forEach(element => {
        this.pushItem(element);
      });
    } else {
      this.pushItem(item);
    }
  }
  pushItem = (val) => {
    let node = new TreeNode(val);
    
    if (this.tree == null) {
      this.tree = node;
    } else {
      
      let re = [this.tree];
      let insertNode;
      while(re.length > 0) {
        let length = re.length;
        for(let i=0; i<length; i++) {
          let indexNode = re.shift();
          if(indexNode.left == null || indexNode.right == null) {
            insertNode = indexNode;
            re = [];
            break;
          } else {
            re.push(indexNode.left);
            re.push(indexNode.right);
          }
        }
      }

      if (insertNode != null) {
        if (insertNode.left == null) {
          insertNode.left = node;
          return;
        }
        if (insertNode.right == null) {
          insertNode.right = node;
          return;
        }
      }
    }
  }
  // 搜索树中是否包含某节点
  // 时间复杂度O(N)
  search = (val) => {
    let re = [this.tree];
      while(re.length > 0) {
        let length = re.length;
        for(let i=0; i<length; i++) {
          let indexNode = re.shift();
          if(indexNode.value == val) {
            return true;
          }
          if (indexNode.left != null) re.push(indexNode.left);
          if (indexNode.right != null) re.push(indexNode.right);
        }
      }
    return false;
  }
// 基于BFS的删除操作
  removeBFS = (val) => {
    let re = [this.tree];
    while(re.length > 0) {
      let length = re.length;
      for(let i=0; i<length; i++) {
        let indexNode = re.shift();
        if(indexNode.left.value == val) {
          indexNode.left = null;
          this.size--;
          return;
        }
        if(indexNode.right.value == val) {
          indexNode.right = null;
          this.size--;
          return;
        }
        if (indexNode.left != null) re.push(indexNode.left);
        if (indexNode.right != null) re.push(indexNode.right);
      }
    }
  }
// 基于DFS的删除操作
  removeDFS = (val) => {
      this.removeItem(this.tree, val);
  }

  removeItem = (node, val) => {
    if(node == null || node.left == null || node.right == null) {
      return;
    }
    if(node.left.value == val) {
      node.left = null;
      this.size--;
      return;
    }

    if(node.right.value == val) {
      node.right = null;
      this.size--;
      return;
    }

    this.removeItem(node.left, val);
    this.removeItem(node.right, val);
  }

  print = () => {
    let re = [this.tree];
    let printString = '';
    while(re.length > 0) {
      let length = re.length;
      for(let i=0; i<length; i++) {
        let node = re.shift();
        printString = printString + '|' + node?.value;
        if (node.left != null) re.push(node.left);
        if (node.right != null) re.push(node.right);
      }
      printString = printString + '\n';
    }
    console.log(printString);
  }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
// 测试二叉树
function testTree() {
  let myTree = new Tree();
  // myTree.push('树节点1');
  // myTree.push('树节点2');
  // myTree.push('树节点3');
  // myTree.push('树节点4');
  // myTree.push('树节点5');
  // myTree.push('树节点6');
  // myTree.push('树节点7');
  // myTree.push('树节点8');

  myTree.push([1,2,3,7,8,4,11,7]);
  myTree.print();

  console.log(myTree.search(3));
  console.log(myTree.search(9));

  myTree.removeBFS(11);
  myTree.removeDFS(8);
  myTree.print();
}


|1
|2|3
|7|8|4|11
|7
true
false
|1
|2|3
|7|4
|7

二叉查找树

二叉查找树，又称二叉排序树或二叉搜索树，是属于二叉树的一种。它最大的特点是每个节点的左子节点永远比该节点小，而每个节点的右子节点却永远比该节点大，即任意节点的左子树上所有结点永远比该节点的右子树上所有结点的值小，它的任意左、右子树也分别为二叉查找树。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
// 二叉树节点
class TreeNode {
  constructor(val) {
    this.value = val;
    this.left = null;
    this.right = null;
  }
}

// 二叉查找树
class BinaryTree {
  constructor() {
    this.tree = null;
    this.size = 0;
  }
  // 向查找树中添加元素
  push = (val) => {
    let newNode = new TreeNode(val);

    if(this.tree == null) {
      return this.tree = newNode; 
    }
    let currentNode = this.tree;
    let parentNode;
    while(true) {
      parentNode = currentNode;
      if(currentNode.value >= val) {
        currentNode = currentNode.left;
        if(currentNode == null) {
          parentNode.left = newNode;
          break;
        }
      } else {
        currentNode = currentNode.right;
        if(currentNode == null) {
          parentNode.right = newNode;
          break;
        }
      }
    }
  }
  // 中序遍历
  inOrder = () => {
    let result = [];
    const dfs = (node) => {
      if(node == null) return;
      dfs(node.left);
      result.push(node.value);
      dfs(node.right);
    }
    dfs(this.tree);
    return result;
  }
  // 查找节点
  // 时间复杂度O(logN)
  search = (val) => {
    let currentNode = this.tree;
    while(currentNode != null) {
      if(currentNode.value == val) {
        return currentNode;
      }
      if(currentNode.value >= val) {
        currentNode = currentNode.left;
      } else {
        currentNode = currentNode.right;
      }
    }

    return null;
  }

  remove = (val) => {
    const getMax = (node) => {
      console.log(node);
      if(node.right == null) {
        return node;
      } else {
        return getMax(node.right);
      }
    }
    // 删除节点
    // 删除一个节点之后，仍需要保证二叉搜索树的特性，删除操作包含两个过程，先是寻找到要删除的节点
    // 找到节点之后，这个位置就空下来了，为了保证最小限度的操作树，需要在余下的节点中，寻找到一个
    // 与删除节点最接近的一个节点（要么是左子树的最大值，要么是右子树的最小值）只需要将这两个值的其
    // 中一个，放到删除后的位置中，就能保证剩下的节点不动，从而完成了删除操作
    const removeItem = (node, val) => {
      if(node == null) return;
      if(node.value == val) {
        // 左右都没有节点
        if(node.left == null && node.right == null) {
          return null;
        }
        // 右节点为空，需要将左子树“提拔"上来
        if(node.right == null) {
          return node.left;
        }
        //  左节点为空，需要将右子树“提拔"上来
        if(node.left == null) {
          return node.right;
        }
        // 左右两边都有节点 
        let tempNode = getMax(node.left); // 找到左子树的最大值
        node.value = tempNode.value; // 将左子树的最大值，换到要删除的节点里
        node.left = removeItem(node.left, tempNode.value); // 把左子树中原来的最大值删除
        return node;
      } else if(node.value >= val) {
        // 在左边寻找
        node.left = removeItem(node.left, val);
        return node;
      } else {
        // 在右边寻找
        node.right = removeItem(node.right, val);
        return node;
      }
    }

    removeItem(this.tree, val);
  }

  print = () => {
    let re = [this.tree];
    let printString = '';
    while(re.length > 0) {
      let length = re.length;
      for(let i=0; i<length; i++) {
        let node = re.shift();
        printString = printString + '|' + node.value;
        if (node.left != null) re.push(node.left);
        if (node.right != null) re.push(node.right);
      }
      printString = printString + '\n';
    }
    console.log(printString);
  }
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
function testBinaryTree() {
  let myTree = new BinaryTree();
  myTree.push(3);
  myTree.push(28);
  myTree.push(44);
  myTree.push(2);
  myTree.push(11);
  myTree.push(8);
  myTree.push(7);
  myTree.push(4);
  myTree.push(3);

  myTree.print();
  console.log(myTree.tree);

  console.log(myTree.inOrder());

  console.log(myTree.search(11));
  console.log(myTree.search(12));

  myTree.remove(28);
  myTree.print();
}

|3
|2|28
|3|11|44
|8
|7
|4

TreeNode {value: 3, left: TreeNode, right: TreeNode}
(9) [2, 3, 3, 4, 7, 8, 11, 28, 44]
TreeNode {value: 11, left: TreeNode, right: null}
null
TreeNode {value: 11, left: TreeNode, right: null}
TreeNode {value: 3, left: TreeNode, right: TreeNode}
|3
|2|11
|3|8|44
|7
|4