数据结构 - 二叉树

概念

又被称为二叉搜索树（binarySearchTree）

  • 根节点
  • 左子树
  • 右子树

创建二叉树

创建节点

1
2
3
4
5
6
7
class CreateNode {
  constructor(key) {
    this.key = key;
    this.left = null;
    this.right = null;
  }
}

创建根节点

1
2
3
4
5
class BinarySearchTree {
  constructor() {
    this.root = null;
  }
}

创建插入节点方法

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
class BinarySearchTree {
  constructor() {
    this.root = null;
  }
  insert(key) {
    const node = new CreateNode(key);
    if (this.root === null) {
      this.root = node;
    } else {
      this.insertNode(this.root, node);
    }
  }
  insertNode(root, node) {
    // 左子树
    if (root.key > node.key) {
      if (root.left === null) {
        root.left = node;
      } else {
        this.insertNode(root.left, node);
      }
    }
    // 右子树
    else {
      if (root.right === null) {
        root.right = node;
      } else {
        this.insertNode(root.right, node);
      }
    }
  }
  print() {
    console.log(this.root);
  }
}

const bst = new BinarySearchTree();
bst.insert(10);
bst.insert(5);
bst.insert(15);
bst.insert(3);
bst.insert(8);
bst.insert(1);
bst.insert(20);
bst.insert(13);
bst.print();

按照上述代码，我们可以得到下图的树形结构（图有点糙，自行脑部-。-）

获得树形结构的最大值&最小值

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
class BinarySearchTree {
  min() {
    return this.minNode(this.root);
  }
  minNode(root) {
    if (root === null) return null;

    // 通过递归循环，直到找到没有left子树的节点并返回，就是树中最小的节点
    while (root.left != null) {
      return this.minNode(root.left);
    }
    return root;
  }
  max() {
    return this.maxNode(this.root);
  }
  maxNode(root) {
    if (root === null) return null;

    // 通过递归循环，直到找到没有left子树的节点并返回，就是树中最小的节点
    while (root.right != null) {
      return this.maxNode(root.right);
    }
    return root;
  }
}

遍历二叉树

前序遍历：根节点->左子树->右子树
中序遍历：左子树->根节点->右子树
后序遍历：左子树->右子树->根节点

先序遍历

  • 按照从左到右的顺序从根节点开始
  • 依次遍历左子树节点（左子树左边、左子树右边）
  • 右子树节点（右子树左边、右子树右边）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class BinarySearchTree {
  prevOrderSearch(callback) {
    this.prevOrderSearchNode(this.root, callback);
  }
  prevOrderSearchNode(node, callback) {
    if (node != null) {
      callback(node.key);
      this.prevOrderSearchNode(node.left, callback);
      this.prevOrderSearchNode(node.right, callback);
    }
  }
}

bst.prevOrderSearch((key) => {
  console.log(key);
});

中序遍历

  • 左子树按照从小到大依次查找 （如果最小的左子树没有了子节点，查找同级的右子树）
  • 直到找到根节点
  • 右子树按照从小到大依次查找 （如果最小的左子树没有了子节点，查找同级的右子树）

1
2
3
4
5
6
7
8
9
10
11
12
class BinarySearchTree {
  inOrderTranvers(callback) {
    this.inOrderTranversNode(this.root, callback);
  }
  inOrderTranversNode(node, callback) {
    if (node != null) {
      this.inOrderTranversNode(node.left, callback);
      callback(node.key);
      this.inOrderTranversNode(node.right, callback);
    }
  }
}

后序遍历

  • 从小到大从左到右依次查找
  • 找到左子树最小的值
  • 判断有没有同级右子树，查找右子树
  • 返回到父子树，判断父子树有没有同级，有的话查找同级，没有的话继续向上查找，
1
2
3
4
5
6
7
8
9
10
11
12
class BinarySerachTree {
  lastOrderTranvers(callback) {
    this.lastOrderTranversNode(this.root, callback);
  }
  lastOrderTranversNode(node, callback) {
    if (node != null) {
      this.lastOrderTranversNode(node.left, callback);
      this.lastOrderTranversNode(node.right, callback);
      callback(node.key);
    }
  }
}

完整代码

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
142
143
144
145
146
147
148
149
150
151
/*
 * @Author: gaocaipeng
 * @Date: 2021-09-18 10:05:20
 * @Last Modified by:   gaocaipeng
 * @Last Modified time: 2021-09-18 10:05:20
 */
class BinarySearchTree {
  constructor() {
    this.root = null;
  }
  createNode(key, left = null, right = null) {
    return {
      key,
      left,
      right,
    };
  }
  // 递归插入节点
  insert(key) {
    const newNode = this.createNode(key);
    if (this.root == null) {
      this.root = newNode;
    }
    this.insertNode(this.root, newNode);
  }
  insertNode(node, newNode) {
    if (node.key > newNode.key) {
      if (node.left === null) {
        node.left = newNode;
      } else {
        this.insertNode(node.left, newNode);
      }
    } else if (node.key < newNode.key) {
      if (node.right === null) {
        node.right = newNode;
      } else {
        this.insertNode(node.right, newNode);
      }
    }
  }
  // 判断二叉树是否包含某个值，返回布尔值
  has(key) {
    return this.hasNode(this.root, key);
  }
  hasNode(node, key) {
    if (node === null) return false;
    if (node.key < key) {
      return this.hasNode(node.right, key);
    } else if (node.key > key) {
      return this.hasNode(node.left, key);
    } else {
      return true;
    }
  }

  // 打印
  print() {
    return this.root;
  }

  // 根据某个值，查找节点树
  find(key) {
    return this.findNode(this.root, key);
  }

  findNode(node, key) {
    if (node.key === key) return node;
    if (node.key < key) {
      if (node.right !== null) {
        return this.findNode(node.right, key);
      }
    } else if (node.key > key) {
      if (node.left !== null) {
        return this.findNode(node.left, key);
      }
    } else {
      return node;
    }
  }

  // 先序列遍历 root-root-left-root-right
  prevTraval(calllback) {
    this.prevTravalNode(this.root, calllback);
  }
  prevTravalNode(node, calllback) {
    if (node !== null) {
      calllback(node.key);
      this.prevTravalNode(node.left, calllback);
      this.prevTravalNode(node.right, calllback);
    }
  }
  // 后序遍历 root-left 最小值从左到右，找到root-right  最小值从左到右，最后输出root
  lastTraval(calllback) {
    this.lastTravalNode(this.root, calllback);
  }
  lastTravalNode(node, calllback) {
    if (node !== null) {
      this.lastTravalNode(node.left, calllback);
      this.lastTravalNode(node.right, calllback);
      calllback(node.key);
    }
  }

  // 中序遍历 从left小往大-root节点值-到right
  middleTraval(calllback) {
    this.middleTravalNode(this.root, calllback);
  }
  middleTravalNode(node, calllback) {
    if (node !== null) {
      this.middleTravalNode(node.left, calllback);
      calllback(node.key);
      this.middleTravalNode(node.right, calllback);
    }
  }
  del(key) {
    this.root = this.delNode(this.root, key);
    console.log(this.root);
  }
  delNode(root, key) {
    if (root == null) return root;
    if (key < root.key) {
      root.left = this.delNode(root.left, key);
    } else if (key > root.key) {
      root.right = this.delNode(root.right, key);
    } else {
      //找到要删除的节点
      //删除没有叶节点元素，直接将当前节点等于null
      if (root.left === null && root.right === null) {
        root = null;
      }
      //删除没有左叶节点的节点，直接将当前节点，等于右节点
      else if (root.left === null) {
        root = root.right;
      }
      //删除没有右叶节点的节点，直接将当前节点，等于左节点
      else if (root.right === null) {
        root = root.left;
      } else {
        let prevNode = root.left;
        while (prevNode.right) {
          prevNode = prevNode.right;
        }
        root.key = prevNode.key;
        root.left = this.delNode(root.left, prevNode.key);
      }
    }
    return root;
  }
}

const bst = new BinarySearchTree();