在计算机科学中，二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用于实现二叉查找树和二叉堆。
二叉树的每个结点至多只有二棵子树(不存在度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒。二叉树的第i层至多有2^{i-1}个结点；深度为k的二叉树至多有2^k-1个结点；对任何一棵二叉树T，如果其终端结点数为n_0，度为2的结点数为n_2，则n_0=n_2+1。
一棵深度为k，且有2^k-1个节点称之为满二叉树；深度为k，有n个节点的二叉树，当且仅当其每一个节点都与深度为k的满二叉树中，序号为1至n的节点对应时，称之为完全二叉树。
二叉树的结构
从上图中可以看出 二叉树一个左指针一个右指针 每一个节点 最多有两个分叉
下面来写一个数组里的元素按照大小规律放入二叉树中的示范：
var arr = [123,12,2,14,144,1245,1,546,568,234,36,42,3467];
左指针放小 右指针放大
先把 第一个元素 放入根节点 1图
1
然后放入 第二个元素 12 12比123小 所以放在 123的左边 2图
2
接下来放第三个元素 先和根节点相比 2比123 小 所以去左边 左边已经有了 就和左边第一个先相比一下 2比12小 所以 2放在 12的左边 3图
3
接下来放第四个 14 还是先和 根结点相比 比 123 小在和左边的12相比 比12 大 所以 放在 12右边 4图
4
再放第五个 144 先和根节点相比 比 123 大 然后去根节点右边 根结点右边没有节点 那么直接放在根节点右边即可 5 图
5
然后同样的理论 放第六个
6
第七个
7
第八个
8
第九个
9
最后全部放入 就是这个样子
最终
我们按照 先左 再根 再右的 遍历方法（中序遍历，前序和后序会在后面的章节讲到）来进行遍历
注意：有两个分叉的 就可以成为 根 其中 12 1245 546 还有123这是最根本的根 父根
就有了 1，2，12，14，36，42，123，144，234，546，568，1245，3467 从小到大排好的顺序。
下面用js来写一个二叉树：
先建立一个节点方法：
function Node(value){
this.value = value;//作为根结点的值 所以创建节点的一瞬间 就变成了根节点
this.left = null;//左指针
this.right = null;//右指针
this.add = function(value){ //插入节点的方法
if(value<this.value){ //先判断一下传入的值是否小于根节点的值 如果小于 就去右面操作 不小于 就去左边操作
if(this.left!=null){ //如果右指针已经有节点了 那么 用右指针去调用 add 直到 右边或者左边没有值了
this.left.add(value);
}else{
this.left = new Node(value);
}
}else{
if(this.right!=null){//如果左指针已经有节点了 那么 用左指针去调用 add 直到 右边或者左边没有值了
this.right.add(value);
}else{
this.right = new Node(value);
}
}
}
this.iterate = function(arr){ //中序遍历 将一个数组传入这个方法中，用于接受遍历的值
if(this.left!=null){//先判断右边有没有节点 如果有 就再次调用iterate方法 一直到右边没有的时候 把值赋给arr 这个过程结束时 会把最根节点右边所有的值排好序 给arr
this.left.iterate(arr);
}
arr.push(this.value);
if(this.right!=null){//然后再判断左边
this.right.iterate(arr);
}
}
}
网友评论