二叉树(Binary tree)

发表于 | 更新于 | 阅读次数：

二叉树的定义

在计算机科学中，二叉树（英语：Binary tree）是每个节点最多只有两个分支（即不存在分支度大于2的节点）的树结构。通常分支被称作“左子树”或“右子树”。二叉树的分支具有左右次序，不能随意颠倒。

与普通树不同，普通树的节点个数至少为1，而二叉树的节点个数可以为0；普通树节点的最大分支度没有限制，而二叉树节点的最大分支度为2；普通树的节点无左、右次序之分，而二叉树的节点有左、右次序之分。

二叉树通常作为数据结构应用，典型用法是对节点定义一个标记函数，将一些值与每个节点相关系。这样标记的二叉树就可以实现二叉搜索树和二叉堆，并应用于高效率的搜索和排序。

遍历二叉查找树

在二叉查找树中，要执行 insert() 方法进行数据的插入。
遍历二叉查找树的方法有：中序，前序，后序

遍历 定义 用途
中序 按照节点上的键值，以升序访问BST上的所有节点（左－根－右） 可用于复制一颗二叉树
前序 先访问根节点，然后以同样方式访问左子树和右子树（根－左－右） 用于排序
后序 先访问叶子节点，从左子树到右子树，再到根节点（左－右－根） 可以用在文件系统里

二叉查找树的构造函数(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
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
function Node (data, left, right) {
  this.data = data;
  this.left = left;
  this.right = right;
}
Node.prototype.show = function () {
  return this.data;
}

function BinaryTree () {
  this.root = null;
}

BinaryTree.prototype  = {
  insert: function (data) {
    var n = new Node(data, null, null);
    if(this.root === null) {
      this.root = n;
    } else {
      var current = this.root;
      var parent;
      while (current) {
        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;
          }
        }
      }
    }
  },
  inOrderTraversal: function (node, callback) {
    if(!(node == null)) {
      this.inOrderTraversal(node.left, callback);
      callback(node.data)
      this.inOrderTraversal(node.right, callback);
    }
  },
  preOrderTraversal: function (node, callback) {
    if(!(node == null)) {
      callback(node.data)
      this.preOrderTraversal(node.left, callback);
      this.preOrderTraversal(node.right, callback);
    }
  },
  postOrderTraversal: function (node, callback) {
    if(!(node == null)) {
      this.postOrderTraversal(node.left, callback);
      this.postOrderTraversal(node.right, callback);
      callback(node.data)
    }
  },
  // Find a given value
  find: function (data) {
    var current = this.root;
    while (current !== null) {
      if (current.data == data) {
        return current;
      }
      else if (data < current.data) {
        current = current.left;
      }
      else {
        current = current.right;
      }
    }
    return null;
  },
  // get min value
  getMin: function () {
    var current = this.root;
    while(current.left !== null) {
        current = current.left;
    }
    return current.data;
  },
  // get max value
  getMax: function () {
    var current = this.root;
    while(!(current.right == null)) {
        current = current.right;
    }
    return current.data;
  },
  // get smallest node
  getSmallest: function (node) {
    if (node.left == null) {
       return node;
    }
    else {
       return getSmallest(node.left);
    }
  },
  remove: function(data) {
    return this.removeNode(this.root, data);
  },
  removeNode: function (node,data) {
    if(node == null) {
        return null;
    }
    if(data == node.data) {
        // 没有子节点的节点
        if(node.left == null && node.right == null) {
            return null;
        } 
        // 没有左子节点的节点
        if(node.left == null) {
            return node.right;
        }
        // 没有右子节点的节点
        if(node.right == null) {
            return node.left;
        }
        // 有2个子节点的节点
        var tempNode = this.getSmallest(node.right);
        node.data = tempNode.data;
        node.right = this.removeNode(node.right,tempNode.data);
        return node;
    }else if(data < node.data) {
        node.left = this.removeNode(node.left,data);
        return node;
    }else {
        node.right = this.removeNode(node.right,data);
        return node;
    }
  }
}

验证:

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
var tree = new BinaryTree();

var arr = [8, 3, 10, 1, 6, 14, 4, 7, 13]

arr.forEach(function (v) {
  tree.insert(v)
})
var res1 = [];
var res2 = [];
var res3 = [];
function callback (list) {
  return function (node) {
    list.push(node)
  }
}
tree.inOrderTraversal(tree.root, callback(res1));
tree.preOrderTraversal(tree.root, callback(res2));
tree.postOrderTraversal(tree.root, callback(res3));
console.log(res1); // [ 1, 3, 4, 6, 7, 8, 10, 13, 14 ]
console.log(res2); // [ 8, 3, 1, 6, 4, 7, 10, 14, 13 ]
console.log(res3); // [ 1, 4, 7, 6, 3, 13, 14, 10, 8 ]

// 获取最小值
console.log(tree.getMin()); // 1

// 获取最大值
console.log(tree.getMax()); //14

// 删除节点
tree.remove(8);

生成的二叉树如图: