数据结构–树

1.树的有关定义和术语

1.术语 1.树（tree): 树是n(n≥0)个结点的有限集T, 当n=0时，T为空树；当n>0时, (1)有且仅有一个称为T的根的结点, (2)当n>1时,余下的结点分为m(m>0)个互不相交的有限集

,…,

,每个Ti(1≤i≤m)也是一棵树,且称为根的子树。这个定义是递归的,是一层套一层的

树的定义都是一级套一级的

2.结点的度(degree): 结点的子树数目 3.树的度: 树中各结点的度的最大值 4.n度树: 度为n的树 //注意这里度和图的度之间的区别 //2度树一定是二叉树,二叉树不一定是二度树 5.叶子(终端结点): 度为0的结点 6.分枝结点(非终端结点,非叶子): 度不为0的结点 7.双亲(父母,parent)和孩子(儿子,child) : 若结点C是结点P的子树的根,称P是C的双亲，C是P的孩子。 8.结点的层(level): 规定树T的根的层为1，其余任一结点的层等于其双亲的层加1。 9.树的深度(depth,高度): 树中各结点的层的最大值。 10.兄弟(sibling): 同一双亲的结点之间互为兄弟。 11.堂兄弟: 同一层号的结点互为堂兄弟。 12.祖先: 从树的根到某结点所经分枝上的所有结点为该结点的祖先。 13.子孙: 一个结点的所有子树的结点为该结点的子孙。 14.有序树:若任一结点的各棵子树，规定从左至右是有次序的,即不能互换位置,则称该树为有序树。二叉树一般是有序的 15.无序树: 若任一结点的各棵子树，规定从左至右是无次序的,即能互换位置,则称该树为无序树。普通的树一般是无序的 16.森林: m(m≥0)棵互不相交的树的集合。

2.其他表现形式 1.广义表表现形式

广义表其实就是一种树,一环套一环

2.Venn图嵌套集合 3.书目表

2.二叉树

1.二叉树的递归定义二叉树是有限个结点的集合，它或者为空集；或者是由一个根结点和两棵互不相交的，且分别称为根的左子树和右子树的二叉树所组成。

二叉树的五种功能,T4和T5

2、二叉树的一些性质 (1)二叉树的第

层最多有

个结点, (2)深度为k的二叉树最多有

个结点 //这个性质可以由等比数列的前n项和推出来 (3)叶子的数目=度为2的结点数目 1 (4)满二叉树:深度为k,且结点数目为

的二叉树,这个时候满二叉树的深度为

对于满二叉树的每一个结点,有以下性质

堆排序里会用到这个性质,堆就是个完全二叉树

5.完全二叉树（full binary tree): 深度为k的有n个结点的二叉树,当且仅当每一个结点都与同深度的满二叉树中编号从1至n的结点一一对应,称之为完全二叉树

深度就是

6.二叉树的存储结构 (1)、对于完全二叉树,我们会使用数组来处理 //不是完全二叉树的话,内存就不能充分的利用,尽量不要选择,如果不得不选择就在缺失的位置补上不存在的标志

跟上面是一样的

(2)、链表(二叉和三叉的)

二叉链表就是有两个指针域

三叉链表:多了一个指向父亲结点的指针

(3)、静态链表就是用一个结构体数组,存入数据,左边的结构序号和右边的结构序号

3.二叉树的遍历

1.遍历顺序前序:根结点-左-右中序:左-根结点-右后序:左-右-根结点层序遍历:一层一层地遍历

2.递归算法实现

代码语言：javascript复制

void InorderTraversal( BinTree BT )
{
    if( BT ) {
        InorderTraversal( BT->Left );
        /* 此处假设对BT结点的访问就是打印数据 */
        printf("%d ", BT->Data); /* 假设数据为整型 */
        InorderTraversal( BT->Right );
    }
}

void PreorderTraversal( BinTree BT )
{
    if( BT ) {
        printf("%d ", BT->Data );
        PreorderTraversal( BT->Left );
        PreorderTraversal( BT->Right );
    }
}

void PostorderTraversal( BinTree BT )
{
    if( BT ) {
        PostorderTraversal( BT->Left );
        PostorderTraversal( BT->Right );
        printf("%d ", BT->Data);
    }
}

void LevelorderTraversal ( BinTree BT )
{ 
    Queue Q; 
    BinTree T;

    if ( !BT ) return; /* 若是空树则直接返回 */
    
    Q = CreatQueue(); /* 创建空队列Q */
    AddQ( Q, BT );
    while ( !IsEmpty(Q) ) {
        T = DeleteQ( Q );
        printf("%d ", T->Data); /* 访问取出队列的结点 */
        if ( T->Left )   AddQ( Q, T->Left );
        if ( T->Right )  AddQ( Q, T->Right );
    }
}
//source:ZJU

3.中序遍历的非递归实现

代码语言：javascript复制

void Midorder(struct BiTNode *t)      //t为根指针 
{ struct BiTNode *st[maxleng];//定义指针栈
  int top=0；                  //置空栈
  
do{            
    
    while(t)               //根指针t表示的为非空二叉树 
    
       { if (top==maxleng) exit(OVERFLOW)；//栈已满,退出
                     
         st[top  ]=t；             //根指针进栈
      
         t=t->lchild；             //t移向左子树
     
       }   //循环结束表示以栈顶元素的指向为
         
           //根结点的二叉树的左子树遍历结束
    
    if (top)                    //为非空栈   
    
       { t=st[--top]；             //弹出根指针
                                printf("%c",t->data)；    //访问根结点
      
         t=t->rchild；             //遍历右子树
     
       }
   
   } while(top||t)； //父结点未访问，或右子树未遍历
 }
source:HUST

思路就是先找到最左的结点,把经过的根结点都保存了,后来左子树遍历完了就找上面根结点的右子树,再把右子树看成个树遍历,遍历完了就返回上一级(退栈),相当于更大的左子树访问完了

后面就不截图了

4.先序遍历的非递归实现

一样的,只不过不同的是,这里入栈就输出

5.后序遍历的非递归实现

注意,由于后序遍历需要遍历一遍左子树,在遍历一遍右子树,所以说保存根结点是十分必要的,所以说这里退栈就不会真退,仅仅是访问而已,如果右子树能能和之前访问过的结点匹配的话,就说明已经回到了根结点了!

代码语言：javascript复制

核心：一个结点需要弹出两次,第一次弹出的时候还需要放回原位（左子树遍历完毕）,第二次弹出的时候才输出其值（右子树遍历完毕）；
Status PostOrder2(BTree *BT) {
     Stack s,s2;
     BTree *T;
     int flag[MaxSize]; 
     s.top=0;
     T=BT;
     while(s.top!=0||T){
         while(T)
         {
             s.data[s.top  ]=T;
             flag[s.top-1]=0;
             T=T->lchild;
          } 
          while(s.top!=0&&flag[s.top-1]==1){
              T=s.data[--s.top];
              printf("=",T->data);
          }
          if(s.top!=0){
              flag[s.top-1]=1;
              T=s.data[s.top-1];
              T=T->rchild;
          }
          else   break;
     }
     return OK;
source:博客园

代码语言：javascript复制

     这里规定了访问次数这个量,被访问了两次就是要输出了
while (p != nullptr || !s.empty()) {
         // 入栈
         if (p != nullptr) {
             s.push(p);
             p = p->left;
         }
 
         // 出栈
         if (p == nullptr) {
             p = s.top();
             s.pop();
 
             p->times  ;
 
             //遍历右子树
             if (p->times == 1) {
                 s.push(p);
                 p = p->right;
             }
 
             //p.times==2; 继续弹栈
             else {
                 cout << p->data;
                 p = nullptr;   // 回溯的关键步骤
             }
         }
     }

6.输入一组先序序列,构建二叉树

代码语言：javascript复制

BiTree CreatBiTree2()
 
{ char ch;  BiTree root;  //二叉链表根结点指针
              scanf(“%c”,&ch);      //输入一个结点
   
if (ch =='  ')
     root=NULL;
   
else {
     
root=(BiTree) malloc(leng);  //生成根结点          
     
root->data=ch;
     
root->lchild=CreatBiTree2(); //递归构造左子树 
     
root->rchild=CreatBiTree2(); //递归构造右子树
       
}
  return root;
 
}

当然,传指针传引用都是可以的

7.线索二叉树二叉树一共有2n个指针域,占用了n-1和,剩下n 1个就会被利用