树和二叉树，以及基本操作详解

树，一种重要的非线性结构。

树的一些概念

1. 树是n个节点的有限集合。在任意一颗非空树中:

 //链式存储结构
    var arr = [];//存储遍历结果
    function BinaryTree(data,leftChild,rightChild) {
        this.data = data || null;
        this.leftChild = leftChild || null;
        this.rightChild = rightChild || null;
    }
    function postOrderTraverse(tree){
        if(tree.leftChild){
            postOrderTraverse(tree.leftChild)
        }
        if(tree.rightChild){
            postOrderTraverse(tree.rightChild)
        }
        if(tree.data){
            arr.push(tree.data)
            return;
        }
    }
    postOrderTraverse(BinaryTree)

有且仅有一个特定的根节点(Root)

当n>1时，其余及节点可分为m(m>0)个互不相交的有限集T1,T2,T3....Tm，其中每一个集合本身又是一棵树，并且称为个子树(subTree)

2. 树的结点包含一个数据元素及若干指向其子树的分支。结点拥有的子树称为结点的度（Degree）。例如在（b）中A的度为3，B的度为2，L的度为0。度为0的结点称为叶子结点（Leaf）。树的度是树内各个结点的度的最大值，（b）的度为3。

3. 结点的层次（Level）从根结点开始计算，根结点为第一层，根的孩子结点为第二层。如果某种结点在第n层，那么它如果有孩子结点，孩子结点在第n+1层。在同一层的结点称为堂兄弟，例如B C D就互为堂兄弟。树中结点的最大层次称为树的深度（depth）或者高度。（b）树的高度为5。

4. 森林（Forest）是m（m>=0）棵互不相交的树的集合。对于树中每个结点而言，其子树的集合即为森林。

二叉树

二叉树是一种特殊的树形结构，它的特点是每个结点至多有两颗子树（即二叉树中不存在度大于2 的结点）。而且二叉树的子树有左右之分，不能任意颠倒。

性质

在二叉树的第i层上最多有2的i-1次方个结点（i>=1）

深度为K的二叉树至多有（2^k）-1个结点（可以用等比数列求和来求解a1(1-q^n)/(1-q)）

对任何一颗二叉树T，如果其终端结点树为n0，度为2的结点数为n2，则n0=n2+1

一颗深度为k且有（2^k）-1个结点的二叉树，称为满二叉树

深度为k的，有n个结点的二叉树，当且仅当每个结点都与深度为k的满二叉树中编号从1-n的结点一一对应时，称为完全二叉树

完全二叉树的特点：

具有n个结点的完全二叉树的深度为Math.floor(log 2n)+1

如果有孩子结点，孩子结点的编号为2n+1和2n+2

二叉树的存储结构

1 顺序存储结构

用一组连续的存储单元依次自上而下，自左而右存储完全二叉树上的结点元素，即将二叉树上编号为i的结点元素存储在加上定义的一堆数组中下标为i-1的位置中。“0”表示不存在此结点。这种顺序存储结构仅使用与完全二叉树。

在最坏情况下，一个深度为k且只有k个结点的单枝树，却需要2的n次方-1的数组

2 链式存储结构

二叉树的结点有一个数据元素和分别指向其左右子树的两个分支构成，则表示二叉树的连标中的结点至少包含3个域：数据域和左右指针域。

顺序存储格式

链式存储

二叉树的遍历分为三种：

先序遍历：根左右

中序遍历：左根右

后序遍历：左右根

顺序存储

 //顺序存储结构
    var tree = [1,2,3,4,5,6,7];
    
    //链式存储结构
    function BinaryTree(data,leftChild,rightChild) {
        this.data = data || null;
        this.leftChild = leftChild || null;
        this.rightChild = rightChild || null;
    }

遍历二叉树：

是指按制定规律对二叉树中的每一个结点进行访问，且访问一次

先序遍历二叉

算法过程：

如果二叉树为空，则遍历结束；否则：

(1)访问根结点

(2)先序遍历左子树

(3)先序遍历右子树

算法实现

对于线性存储而言，一个结点如果存在孩子结点，如果结点在数组中的位置为i, 左孩子的位置为2i+1，右孩子的位置为2i+2.

  //顺序存储结构,0表示该结点为空
    var tree = [1,2,3,4,5,6,7,0,0,8,9,10,11,12,0,0,0,0,0,0,13];

    //顺序存储的递归遍历
    var arr = [];//存储遍历结果

    function PreOrderTraverse(tree,x) {
        arr.push(tree[x]);
        if(tree[x*2+1]&&tree[x*2+1]!=0){PreOrderTraverse(tree,x*2+1)}
        if(tree[x*2+2]&&tree[x*2+2]!=0){PreOrderTraverse(tree,x*2+2)}
    }
    PreOrderTraverse(tree,0)
    console.log(arr)

对于链式算法：

 var arr = [];//存储遍历结果
    function BinaryTree(data,leftChild,rightChild) {
        this.data = data || null;
        this.leftChild = leftChild || null;
        this.rightChild = rightChild || null;
    }
    
    function PreOrderTraverse(tree){
        if(tree.data){
            arr.push(tree.data)
            return;
        }
        if(tree.leftChild){
            PreOrderTraverse(tree.leftChild)
        }
        if(tree.rightChild){
            PreOrderTraverse(tree.rightChild)
        }
    }

中序遍历二叉树

算法过程：

如果二叉树为空，则遍历结束；否则：

(1)中序遍历左子树

(2)访问根结点

(3)中序遍历右子树

线性存储

   //顺序存储的递归遍历
var arr = [];//存储遍历结果
function inOrderTraverse(tree,x) {
    if(tree[x*2+1]&&tree[x*2+1]!=0){inOrderTraverse(tree,x*2+1)}
    arr.push(tree[x]);
    if(tree[x*2+2]&&tree[x*2+2]!=0){inOrderTraverse(tree,x*2+2)}
}
inOrderTraverse(tree,0)
console.log(arr)

链式存储

 //链式存储结构
    var arr = [];//存储遍历结果
    function BinaryTree(data,leftChild,rightChild) {
        this.data = data || null;
        this.leftChild = leftChild || null;
        this.rightChild = rightChild || null;
    }

    function inOrderTraverse(tree){
        if(tree.leftChild){
            inOrderTraverse(tree.leftChild)
        }
        if(tree.data){
            arr.push(tree.data)
            return;
        }
        if(tree.rightChild){
            inOrderTraverse(tree.rightChild)
        }
    }
    inOrderTraverse(BinaryTree)

后序遍历二叉树

算法过程：

如果二叉树为空，则遍历结束；否则：

(1)后序遍历左树

(2)后序遍历右子树

(3)访问根结点

线性存储

 var arr = [];//存储遍历结果

    function postOrderTraverse(tree,x) {
        if(tree[x*2+1]&&tree[x*2+1]!=0){postOrderTraverse(tree,x*2+1)}
        if(tree[x*2+2]&&tree[x*2+2]!=0){postOrderTraverse(tree,x*2+2)}
        arr.push(tree[x]);
    }
    postOrderTraverse(tree,0)
    console.log(arr)

链式存储

 //链式存储结构
    var arr = [];//存储遍历结果
    function BinaryTree(data,leftChild,rightChild) {
        this.data = data || null;
        this.leftChild = leftChild || null;
        this.rightChild = rightChild || null;
    }
    function postOrderTraverse(tree){
        if(tree.leftChild){
            postOrderTraverse(tree.leftChild)
        }
        if(tree.rightChild){
            postOrderTraverse(tree.rightChild)
        }
        if(tree.data){
            arr.push(tree.data)
            return;
        }
    }
    postOrderTraverse(BinaryTree)