二叉树与二叉查找树

发表于 | 分类于

什么是树？

  • 树由一组以边连接的节点组成

一棵树最上面的节点称为根节点

一个节点下面有多个节点，那这个节点被称为父节点

没有任何子节点的节点称为叶子节点

从一个节点到另一个节点的这一组边被称为路径

以某种顺序访问树中所有节点称为树的遍历

树的层数就是树的深度

每一个节点都有一个与之相关的值，这个值被称为键

二叉树是一种特殊的树，它的特点是子节点的个数不超过两个

二叉查找树是一种特殊的二叉树，特点是较小的值保存在左节点，较大的值保存在右节点

无论是二叉树还是二叉查找树，都是由节点组成的，因此我们首先定义Node节点类

1
2
3
4
5
6
7
8
9
10
function Node(data, left, right){
    this.data = data
    this.left = left
    this.right = right
    this.show = show
}

function show(){
    return this.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
function BST(){
    this.root = null
    this.insert = insert
    this.inOrder = inOrder
}

function insert(data){
    let node = new Node(data, null, null)
    if(this.root == null){
        this.root = node
    }else {
        let current = this.root
        let parent
        while(true){
            parent = current
            if(data < current.data){
                current = current.left
                if(current == null){
                    parent.left = node
                    break
                }
            }else{
                current = current.right
                if (current == null) {
                    parent.right = node
                    break
                }                
            }
        }
    }
}

至此，我们已经能够向二叉树中插入节点了，我们还需要能够遍历这棵二叉树（以一定的顺序来显示节点）

遍历二叉树有三种方式：中序，先序，后序。其中，中序按节点键值的升序来遍历；先序则是先访问根节点，再访问左子树和右子树；后序则先访问叶子节点，然后是左子树、右子树、根节点

1
2
// 中序代码如下
function