二叉树

2021-04-05 上次更新时间：4/29/2022, 9:34:08 AM 0

二叉树(Binary Tree) 是 n 个结点的有限集合，该集合或者为空集，或者由一个根节点和两个互不相交的、分别为根节点左子树和右子树对的二叉树组成。

# 二叉树分类

斜树：又分为左斜树、右斜树（只有一边）。
满二叉树：左右都有，非常漂亮的二叉树。
完全二叉树: 二叉树中编号为 i 的结点在二叉树中位置完全相同(如编号为5，它的位置就在树的第五个结点)。

# 二叉树性质

# 存储结构

顺序存储结构：使用数组下标标识每个结点，一般只用于完全二叉树，否则会造成空间浪费。

链式存储结构：二叉链表。每个结点含有一个数据域和两个指针域。

如果有需要，可以再加一个指向双亲的指针域，这种就叫做三叉链表

# 二叉树的实现

// 结点
function Node(data, left, right) { 
    this.data = data; 
    this.left = left; 
    this.right = right; 
    this.show = show; 
}
function show() { 
    return this.data; 
}
// 二叉树
function BST() { 
    this.root = null; 
    this.insert = insert;
}
// 插入结点
function insert(data) { 
    var n = new Node(data, null, null); 
    if (this.root == null) { 
        this.root = n;
    } else {
        var current = this.root;
        var parent; 
        while (true) {
            parent = current;
            // 较小的放在左边
            if (data < current.data) { 
                current = current.left; 
                if (current == null) { 
                    parent.left = n; 
                    break; 
                } 
            } else {
                current = current.right; 
                if (current == null) {
                    parent.right = n; 
                    break; 
                } 
            } 
        } 
    } 
}

var b = new BST()
// 为了更好的演示，手动设置树
b.insert('A')

b.root.left = new Node('B', null, null)
b.root.left.left = new Node('D', null, null)
b.root.left.left.left = new Node('G', null, null)
b.root.left.left.right = new Node('H', null, null)

b.root.right = new Node('C', null, null)
b.root.right.left = new Node('E', null, null)
b.root.right.left.right = new Node('I', null, null)
b.root.right.right = new Node('F', null, 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
46
47
48
49
50
51
52
53
54
55
56
57

了解了二叉树是怎样实现的，接下来需要了解二叉树的遍历方法了。

为什么要了解遍历方法？

其实是为了把树中的结点变成某种意义上的线性序列，就可以根据这些序列的特征进行各种处理。不同的遍历方法就对应着不同的算法。

# 二叉树遍历

二叉树遍历( traversing binary tree) 是指从根结点出发，按照某种次序一次访问二叉树中所有结点，使得每个结点被访问一次且仅被访问一次。

类别	遍历方法	时间复杂度	空间复杂度
深度(优先)遍历，DFS	1. 前序遍历 2. 中序遍历 3. 后序遍历	O(n)，n 是结点数	O(n)，n 是结点数
广度(优先)遍历，BFS	层序遍历	O(n)，n 是结点数	O(h)，h 是树的最大深度

# 前序遍历

前序遍历：从根结点开始，先遍历左子树，再遍历右子树。

function preOrder(node) { 
    if (!(node == null)) {
        console.log(node.show() + " ");
        preOrder(node.left); 
        preOrder(node.right); 
    } 
}
preOrder(b.root); // A B D G H C E I F

1
2
3
4
5
6
7
8

# 中序遍历

中序遍历：中序遍历根结点左子树，然后访问根结点，最后中序遍历右子树。

function inOrder(node) { 
    if (!(node == null)) { 
        inOrder(node.left); 
        console.log(node.show() + " "); 
        inOrder(node.right); 
    } 
}
inOrder(b.root); // G D H B A E I C F

1
2
3
4
5
6
7
8

# 后序遍历

后序遍历：从左到右先叶子后结点的方式遍历左右树，最后访问根结点。

function postOrder(node) { 
    if (!(node == null)) { 
        postOrder(node.left); 
        postOrder(node.right); 
        console.log(node.show() + " ");
    } 
}
postOrder(b.root); // G H D B I E F C A

1
2
3
4
5
6
7
8

# 层序遍历(广度遍历)

层序遍历(广度遍历)：从根结点开始，从上而下逐层遍历，在同一层中，按从左到右的顺序对结点逐个访问。(通常借助队列来实现)

var levelOrder = function (root) {
  if(!root) return [];
  const q =[root]; // 执行队列
  const res = []; // 下一层级结点
  while (q.length) {
    let len = q.length;
    res.push([]);
    while(len--) {
      const n = q.shift();
      res[res.length -1].push(n.data);
      if(n.left) q.push(n.left);
      if(n.right) q.push(n.right);
    }
  }
  return res;
}

levelOrder(b.root); // [A] [B, C] [D, E, F] [G, H, I]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

# 二叉树的应用

查找给定值：比较该值与当前节点的值大小，就能确定不在当前节点时，是该向左遍历，还是向右遍历。
查找最大值：右子树的最深层右结点。
查找最小值：左子树的最深层左结点。

← 树图 →