\

1.树的有关定义和术语

1.术语
1.树(tree):
树是n(n≥0)个结点的有限集T,
当n=0时,T为空树;
当n>0时,
(1)有且仅有一个称为T的根的结点,
(2)当n>1时,余下的结点分为m(m>0)个互不相交的有限集T_1,T_2,…,T_m ,每个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)二叉树的第i层最多有2^{i-1}个结点,
(2)深度为k的二叉树最多有2^k-1个结点
//这个性质可以由等比数列的前n项和推出来
(3)叶子的数目=度为2的结点数目+1
(4)满二叉树:深度为k,且结点数目为2^k-1的二叉树,这个时候满二叉树的深度为log_2(n+1)
对于满二叉树的每一个结点,有以下性质

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

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

深度就是upper(log_2(n+1))

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

跟上面是一样的

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

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

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

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

3.二叉树的遍历

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

2.递归算法实现

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.中序遍历的非递归实现

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.后序遍历的非递归实现

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

核心:一个结点需要弹出两次,第一次弹出的时候还需要放回原位(左子树遍历完毕),第二次弹出的时候才输出其值(右子树遍历完毕);
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("%3d",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:博客园
     这里规定了访问次数这个量,被访问了两次就是要输出了
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.输入一组先序序列,构建二叉树

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个就会被利用

中序和后序都是一样的

左子树存进栈里
弹出根结点,如果结点有左孩子话,tag为0,没有的话记为1,注意保存一个pre,保存序列上一个结点的内容,总之很抽象,需要好好研读

当然了,带个头指针在指向二叉树本身的操作也是被允许的

这下非递归的遍历就很方便了

8.表达式二叉树

这样利用构造中序遍历的二叉树,先序遍历输出的结果是波兰式,后序遍历输出的是逆波兰式

9.中序+前序&后序表达式唯一确定二叉树zhon

根据前序表达式确定根结点,中序表达式分割左子树和右子树

3.树和森林

1.数组(双亲表示法) 数组里面存的是结构体,结构体两个元素,存数据和双亲

2.孩子表示法(链表)

固定了内存,有损耗

3.孩子链表表示法
链Hash(bushi)

4.带双亲的孩子链表表示法:每一个结构体加一个双亲

5.树与二叉树的转换

红色的往右走,黑色的往左走
左子树的左儿子的右儿子可以连线,然后右儿子关系断裂
根的右儿子的右儿子与一个虚无链接,构成树林

树的遍历:
前根遍历:根——第一个儿子——……
后跟遍历:第一个儿子——第二个儿子——……——根

4.Huffman树

1.路径长度—-路径上分枝的数目(连线的数目)
2.树T的路径长度—-从树T的根到其余每个结点的路径长度之和,记作PL(T)
当n个结点的二叉树为完全二叉树时,PL(T)具有最小值:

    \[sum=\int_{i=1}^n down(log_2i)\]


当n个结点的二叉树为单枝树时,PL(T)具有最大值:
PL(T) = 1+2+…+(n-1) = n(n-1)/2
树T的带权路径长度—-每个叶子的权与根到该叶子的路径长度的乘积之和,记作WPL(T)=\int^n_{k=1}w_kl_k n:叶子数 w_k叶子k的权 l_k路径长度

构建方式离散数学有讲,注意排序合并中排序不能漏


构建的方式用代码实现:
其实树可以表示成父母孩子表示法,每次合并的时候就找最小的两个数,标记已合并,构建新结点,新结点是没合并过的

Huffman编码的构建:就从自己开始找反序列,在调转即可

最后修改日期:2020年10月24日