資料結構----樹（筆記）

樹對我來說是個比較生疏的概念，有必要好好看一看。在學生管理的結構裡面，學生最上面的是學校，然後學院，專業，年級，班級最後個人，畫出圖形來就像是一棵樹，這種問題是很普遍的。

樹的常用術語

節點：一個元素資料和若幹指向子樹的分支。 度：節點上擁有的子樹的個數 終端節點：度為0的節點 分支節點：度不為0的節點 孩子：節點的子樹的根為該節點的孩子 層次：從根開始算起，根是第一層，跟的孩子是第二層，以此類推。 兄弟：同一雙親的孩子互稱兄弟 祖先：節點的祖先是從根到該節點所經分支的所有的節點 子孫：某一節點為根的子樹的任一節點都稱為該節點的子孫 深度：樹的一個節點的高度是從該節點到作為它的子孫的各葉子節點的最長路徑的長度。 森林：0棵或有限棵不相交的樹的集合成為森林。

樹的基本操作               

1. Initiate(t), 初始化一 空樹 2.root (x) 所在的樹的根節點 3.parent(t，x) 求樹t中節點x的雙親節點 4.child(t,x,i)求樹t 裡的節點x的第i個孩子節點 5.rightsibling(t,x) 求樹t的節點x的第一個右邊的兄弟節點 6.insert (t,x,i,s)把以s為根節點的樹插入到樹t裡作為節點x的第i棵子樹 7.deletet(t,x,i) 在樹t裡面删除節點x的第i棵子樹 8.tranverse(t)是樹的周遊操作，即按照某種方式通路樹t的每個節點，且使得每個節點隻通路一次。

二叉樹的性質

一個深度為k的二叉樹中最多有2^k-1 節點

一棵非空的二叉樹的第i層最多有2^(i-1)個節點

對于一棵非空的二叉樹，如果葉子節點數為n0，度數為2的節點數n2, 則n0=n2+1；

具有n個節點的完全二叉樹的深度k=|_log2（n）_|+1.

int InitTree(Tree **bt)
{   //初始化建立二叉樹，*bt的頭節點
    if((*bt=(Tree *)malloc(sizeof(Tree)))==NULL)
        return 0;
    *bt->lchild=NULL;
    *bt->rchild=NULL;
    return 1;
}
Tree* Create(int x,Tree *l,Tree*r)
{
    Tree *p;
    if((p=(Tree *)malloc(sizeof(Tree)))==NULL)
    {
        return NULL;
    }
    p->data=x;
    p->lchild=l;
    p->rchild=r;
    return p;
}
Tree *Insert_l(Tree *bt,int x,Tree *parent)
{
    Tree *p;
    if(parent==NULL)
    {
        printf("\n插入出錯.");
        return NULL;
    }
     if((p=(Tree *)malloc(sizeof(Tree)))==NULL)
         return NULL;
     p->data=x;
     p->lchild=NULL;
     p->rchild=NULL;
     if(parent->lchild=NULL)
         parent->lchild=p;
     else
     {
         p->lchild=parent->lchild;
         parent->lchild=p;
     }
    return bt;
}
Tree *Insert_r(Tree *bt,int x,Tree *parent)
{
    Tree *p;
    if(parent==NULL)
    {
        printf("\n插入出錯.");
        return NULL;
    }
     if((p=(Tree *)malloc(sizeof(Tree)))==NULL)
         return NULL;
     p->data=x;
     p->lchild=NULL;
     p->rchild=NULL;
     if(parent->rchild=NULL)
         parent->rchild=p;
     else
     {
         p->rchild=parent->rchild;
         parent->rchild=p;
     }
    return bt;
}
Tree * delete_l(Tree*bt,Tree *parent)
{
    Tree *p;
    if(parent->lchild==NULL||parent==NULL)
    {
        printf("删除出錯.\n");
        return NULL;
    }
    p=parent->lchild;
    parent->lchild=NULL;
    free(p);
    return bt;
}
Tree * delete_r(Tree*bt,Tree *parent)
{
    Tree *p;
    if(parent->rchild==NULL||parent==NULL)
    {
        printf("删除出錯.\n");
        return NULL;
    }
    p=parent->rchild;
    parent->rchild=NULL;
    free(p);
    return bt;
}
void PreOrder(Tree *bt)//先根序，先節點，再左邊，最後右邊
{
    if(bt==NULL)
        return;
    printf("%d  ",bt->data);
    PreOrder(bt->lchild);
    PreOrder(bt->rchild);  
}
void InOrder(Tree *bt)//中序周遊根節點的左子樹，通路根節點，中序周遊裡節點的右子樹
{
    if(bt==NULL)
    {
        return ;
    }
    InOrder(bt->lchild);
    printf("%d  ",bt->data);
    InOrder(bt->rchild);
}
void PostOrder(Tree*bt)//後序周遊根結點的左子樹，後序周遊根結點的右子樹，通路根節點
{
    if(bt==NULL)
    {
        return ;
    }
    PostOrder(bt->lchild);
    PostOrder(bt->rchild);
    printf("%d  ",bt->data);
}
void LeveOrder(Tree*bt)//層次周遊
{
    Tree *q[MAX];
    int front,rear;
    if(bt==NULL)
    {
        return;   
    }
    front=-1;
    rear=0;
    q[rear]=bt;
    while(front!=rear)
    {
        front++;
        printf("%d  ",q[front]->data);
        if(q[front]->lchild!=NULL)
        {
            
            rear++;
            q[rear]=q[front]->lchild;
        }
        if(q[front]->rchild!=NULL)
        {
            rear++;
            q[rear]=q[front]->rchild;
        }
    }
 
}
void Order(Tree *bt)//非遞歸
{
    Tree *stack[MAX],*p;
    int top;
    if(bt==NULL)
        return;
    top=0;
    p=bt;
    while(!(p==NULL&&top==0))
    {
        while(p!=NULL)
        {
             printf("%d  ",bt->data);
             if(top<MAX-1)
             {
                 stack[top]=p;
                 top++;
             }
             else
             {
                 printf("棧溢出.\n");
                 return;
             }
             p=p->lchild;
        }
        if(top<=0)
            return ;
        else
        {
            top--;
            p=stack[top];
            p=p->rchild;
        }
    }
}