数据结构----树（笔记）

树对我来说是个比较生疏的概念，有必要好好看一看。在学生管理的结构里面，学生最上面的是学校，然后学院，专业，年级，班级最后个人，画出图形来就像是一棵树，这种问题是很普遍的。

树的常用术语

节点：一个元素数据和若干指向子树的分支。 度：节点上拥有的子树的个数 终端节点：度为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;
        }
    }
}