白筱汐

想都是问题，做都是答案

0%

二叉树的基本操作

发表于 更新于 分类于

二叉树的定义

二叉树是一种数据结构，它由一组称为节点的元素组成，这些节点通过边连接。每个节点最多可以有两个子节点，分别称为左子节点和右子节点。

二叉树的主要方法有：

  • 创建
  • 添加节点
  • 查找节点
  • 删除节点
  • 获得树的高度
  • 获得树的节点树
  • 各种遍历方法（请参考我的博客里对于二叉树的前序、中序、后续遍历描述的文章）

二叉树的实现

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
class Node {
  constructor(data) {
    this.parent = null
    this.data = data
    this.left = null
    this.right = null
  }
}

class Tree {
  constructor() {
    this.root = null
    this.size = 0
  }
  // 插入
  insert(data) {}

  // 删除
  remove(data) { }
  // 节点树
  size() { }
  // 最小节点
  minNode() { }
  // 最大节点
  maxNode() { }
  // 高度
  height() {}
}

插入节点

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
class Tree {
    constructor() {
        this.root = null
        this.size = 0
    }

    // 插入
    insert(data) {
        const newNode = new Node(data)
        // 如果树为空
        if (!this.root) {
            this.root = newNode
        } else {
            this.insertNode(this.root, newNode)
        }
    }

    insertNode(node, newNode) {
        // 要插入的值小于当前节点的值
        if (newNode.data < node.data) {
            // 左子节点不存在
            if (!node.left) {
                node.left = newNode
                newNode.parent = node
            } else {
                // 向左子树递归进行对比判断，是插入到左子树还是右子树
                this.insertNode(node.left, newNode)
            }
        } else {
            // 要插入的值大于等于当前节点的值
            if (!node.right) { // 右子节点不存在
                node.right = newNode
                newNode.parent = node
            } else {
                // 向右子树递归进行对比判断，是插入到左子树还是右子树
                this.insertNode(node.right, newNode)
            }
        }
    }
}

查找节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Tree {
    // ...

    find(data) {
        return this.find(this.root,data)
    }

    //查找节点
    findNode(node,data) {
        if (!node) {
            return null
        }
        // 找到节点
        if (data == node.data) {
            return node
            // 检查目标值是否在左子树中
        } else if (data < node.data) {
            return this.findNode(node.left, data)
            // 检查目标值是否在右子树中
        } else {
            return this.findNode(node.right, data)
        }
    }
}

删除节点

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
remove(data) {
    // 先找到要删除的节点
    let node = this.find(data)
    if (node) {
        this.size--
        // 被删除的节点是根节点
        if (node === this.root) {
            this.root = null
            return true
        }
        let left = node.left,right = node.right // 左右子树
        let parent = node.parent // 父节点
        let isLeft = parent && parent.left === node // 是左子树还是右子树
        // 1. 被删除节点没有子节点，直接删除
        if (!left && !right) {
            if (isLeft) {
                parent.left = null
            } else {
                parent.right = null
            }
        } else if (left && !right) {
            // 2. 被删除节点只有左子节点 (被删除节点的左子节点指向父节点)
            if (isLeft) {
                parent.left = left
            } else {
                parent.right = left
            }
            left.parent = parent
        } else if (!left && right) {
            // 3. 被删除节点只有右子节点 (被删除节点的右子节点指向父节点)
            if (isLeft) {
                parent.left = right
            } else {
                parent.right = right
            }
            right.parent = parent
        } else if (left && right) {
            // 4. 被删除节点既有左子节点，又有右子节点
            // 假设使用右子树继位，则需要找到右子树中最靠左边的值
            let child = right
            while (child.left) {
                child = child.left
            }
            this.remove(child.data) // 然后改删除叶子节点
            node.data = child.data // 找到右子树中最接近的值，覆盖原先要删除的节点的值
        }
    }
}

删除二叉树的节点比较复杂，主要有4种情况，这里解释一下每种情况的处理方法：

  1. 被删除的节点是叶子节点，直接删除即可。判断它是父节点的哪一边的孩子节点，将相应的属性设置为null。
  2. 被删除的节点只有左子节点，需要用它的左子节点把它自己给替换下去。
  3. 被删除的节点只有右子节点，需要用它的右子节点把它自己给替换下去。
  4. 被删除的节点有左右2个子节点。这时候我们需要考虑是用左子树继位还是用右子树继位。如果用左子树继位（实例代码中使用右子树继位），需要找到左子树最靠右的节点。如果该节点没有子节点，只需用它替换目标节点。如果该节点有一个左子节点，请将其替换为左子节点，然后将目标节点替换为最右边的节点。

删除节点的第四种情况最为复杂，一般书中给出的操作方式读起来非常的费劲。上面的解释来自书籍《算法基础》，但是具体操作的时候有一些技巧。在使用左子树继位的时候，找到了最右边的节点值，把它的值记录下来，然后删除这个节点，最后把原先要删除的值与记录的值替换。这样就相当于完成了上面的节点替换的操作（操作来自《JavaScript算法》）。

最大值与最小值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// 最小节点
  minNode(node) {
    var cur = node || this.root
    while (cur.left) {
      cur = cur.left
    }
    return cur
  }
  // 最大节点
  maxNode() {
    var cur = this.root
    while (cur.right) {
      cur = cur.right
    }
    return cur
  }
  getMax() {
    var node = this.maxNode()
    return node ? node.data : null
  }
  getMin() {
    var node = this.minNode()
    return node ? node.data : null
  }

高度

1
2
3
4
5
6
7
8
9
10
11
height() {
    return this.getNodeHeight(this.root)
}
getNodeHeight(node) {
    if (node == null) {
        return 0
    }
    let leftChildHeight = this.getNodeHeight(node.left)
    let rightChildHeight = this.getNodeHeight(node.right)
    return Math.max(leftChildHeight, rightChildHeight) + 1
}

节点数量

1
2
3
4
5
6
7
8
9
10
11
size() { // this.getNodeSize(this.root)
  return this.size
}
getNodeSize(node) {
  if (node == null) {
    return 0
  }
  let leftChildSize = this.getNodeSize(node.left)
  let rightChildSize = this.getNodeSize(node.right)
  return leftChildSize + rightChildSize + 1
}

翻转二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 翻转二叉树
invertTree() {
    if (root === null) {
        return null;
    }

    // 交换左右子树
    let temp = root.left;
    root.left = root.right;
    root.right = temp;

    // 递归翻转左右子树
    this.invertTree(root.left);
    this.invertTree(root.right);

    return root
}