一些常用的数据结构（五）：树

     树中元素的度是指其孩子的个数，树的度是指其元素度的最大值，树的级应该是指树的层数，树根的级为1。

     二叉树中每个元素的度均小于等于二即可，并没有其他额外的限制。

     若设二叉树的高度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的节点都连续集中在最左边，这就是完全二叉树。 完全二叉树通俗一点说就是上面一行不满不能往下面添加元素的树，好处是可以用编号找到指定位置的元素，堆是一棵完全二叉树。

     满二叉树一棵深度为h且有 2h-1个结点的二叉树。

 

 

     关于树的遍历那些前序中序后序中的前中后指的是当前节点的值，逐层遍历则采用队列来实现。

        得到树的高度：

 int getHeight(BinaryTreeNode t)
{
   if(!t)return 0;//t是指传入的数结点
   int lHeight=getHeight(t->leftChild);
   int rHeight=getHeight(t->rightChild);
   return (lHeigt>rHeight?lHeight:rHeight)++;
} 

 最大堆是指所有节点的值都大于或等于其子节点的值的完全二叉树。

向堆中插入元素：

//向堆中插入元素
void Insert(int x)
{
    int i=++Size;//size为堆当前的大小
    while(i!=1&&x>heap[i/2])
    {
        heap[i]=heap[i/2];
        i=i/2;
    }
    heap[i]=x;
}

 //删除：删除根节点，然后抽出最后一个节点，

//从根位置开始往下找合适的位置插入

int HeapDelete(int h[])
{
    int x = h[1]; //最大元素，即根
    //-------------重构堆---------------
    int y = h[CurrSize--]; //最后一个元素
    int i=1/*当前节点*/,pi=2/*i的孩子*/;
    while(pi <= CurrSize)
    {
        if(pi < CurrSize && h[pi] < h[pi+1])
            pi++; //若存在右孩子且右孩子较大，则pi指向右孩子
        //此时pi已指向i的孩子中较大者
        if(y >= h[pi]) break; //y可插入h[i]
        h[i] = h[pi]; //不可插入则上移较大孩子
        i = pi; pi = pi*2;  //继续往下做比较
    }
    h[i] = y;  //插入
    return x;  //返回删除的元素
}

 

/*--- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --
初始化：从最后一个有孩子的节点开始一直到根，对每一个有孩子的节点，
        都在以其为根的子树中寻找合适的位置插入，过程类似于删除
--- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --- --*/
void HeapInit(int h[],int cs,int ms)
{
    int i,y,pi;
    CurrSize = cs;  MaxSize = ms;
    for(i = CurrSize/2; i >= 1; i--)
    {
        y = h[i];  //子树的根
        pi = 2*i;  //其左孩子
        while(pi <= CurrSize) //一直往下寻找合适的位置
        {
            if(pi < CurrSize && h[pi] < h[pi+1])
                pi++; //若存在右孩子且右孩子较大，则pi指向右孩子
            //此时pi已指向i的孩子中较大者
            if(y >= h[pi]) break; //y可插入h[i]
            h[pi/2] = h[pi]; //不可插入则上移较大孩子
            pi = pi*2;  //继续往下做比较
        }
        h[pi/2] = y;  //插入
    }
}

 

左高树和哈夫曼树之类的先不写了。