theme: healer-readable highlight: atom-one-dark

前言

Hi, 我是Rike，欢迎来到我的频道～

本篇为大家带来的是，C语言版数据结构笔记第六章-树。树结构可谓高深奥妙，是线性结构的延伸，又扩展排序、搜索、遍历、哈夫曼编码、动态规划多个方面，本文将就此展开

希望各位多多支持～

一、基本概念

（一）定义

树是若干结点的集合，是由唯一的根和若干棵互不相交的子树组成。空树的结点数为 0。存储的是具有“一对多”关系的数据元素的集合。

​​

（二）基本术语

1、树的结点

• 结点：使用树结构存储的每一个数据元素都被称为“结点”，包含数据元素、子树的分支。
• 叶子结点：又称终端结点，指度为 0 的结点。
• 非终端结点：又称分支结点 ，指度不为 0 的结点。
• 孩子：本结点的分支结点。
• 双亲：本结点的高层结点。
• 兄弟：同一个双亲的孩子互为兄弟。
• 堂兄弟：双亲在同一层的结点互为堂兄弟。
• 祖先：从根到某结点的路径上的所有结点，都是其祖先。
• 子孙：以某结点为根的子树上的所有结点，都是其子孙。

2、子树和空树

• 子树：本结点的分支所构成的树。
• 空树：如果集合本身为空，那么构成的树就被称为空树。空树中没有结点。

3、度和层次

• 结点的度：结点拥有的子树个数。

• 树的度：树各结点度中的最大值。

• 树的高度（深度）：树中结点的最大层次。

• 结点的深度和高度：

  • 深度：从根结点到该结点路径上的结点个数。
  • 高度：从某结点往下走到达叶子结点路径最长的结点个数。

4、有序树和无序树

• 若树的子树有左右先后顺序之分，这棵树称为有序树；反之称为无序树。

5、森林

• 森林：若干棵互不相交的树的集合。
  即，由 m（m >= 0）个互不相交的树组成的集合被称为森林。

6、树的表示方法

​​

7、分支与结点的关系

• 分支数比结点数少 1。

（三）存储结构

1、顺序存储结构

双亲表示法采用顺序表（也就是数组）存储普通树，其实现的核心思想是：顺序存储各个节点的同时，给各节点附加一个记录其父节点位置的变量。

即，双亲表示法。实质上是图的邻接表存储结构。

适用于查找某结点的父结点。

​​

结构体

​​

数组

（1）结构体版

 typedef struct
 {
     int data;
     int pIdx;
 }TNode;
 ​
 TNode tree[maxsize];
 ​
 tree[0].data = A1;
 tree[0].pIdx = -1;
 tree[1].data = A2;
 tree[1].pIdx = 0;
 tree[2].data = A3;
 tree[2].pIdx = 0;
 tree[3].data = A4;
 tree[3].pIdx = 0;
 tree[4].data = A5;
 tree[4].pIdx = 1;
 tree[5].data = A6;
 tree[5].pIdx = 1;

（2）数组型

 int tree[maxSize];
 tree[0] = -1;
 tree[1] = 0;
 tree[2] = 0;
 tree[3] = 0;
 tree[4] = 1;
 tree[5] = 1;

2、链式存储结构

（1）孩子存储结构

即，孩子表示法。

存储普通树采用的是 " 顺序表 + 链表 " 的组合结构，其存储过程是：从树的根结点开始，使用顺序表依次存储树中各个结点，需要注意的是，与双亲表示法不同，孩子表示法会给各个结点配备一个链表，用于存储各结点的孩子结点位于顺序表中的位置。

适用于查找某结点的孩子结点，不适用于查找其父结点。

如果结点没有孩子结点（叶子结点），则该结点的链表为空链表。

​​

/*以上图为例*/
#include<stdio.h>
#include<stdlib.h>
#define MAX_SIZE 20
#define TElemType char
//孩子表示法
typedef struct CTNode{
    int child;//链表中每个结点存储的不是数据本身，而是数据在数组中存储的位置下标
    struct CTNode * next;
}ChildPtr;
typedef struct {
    TElemType data;//结点的数据类型
    ChildPtr* firstchild;//孩子链表的头指针
}CTBox;
typedef struct{
    CTBox nodes[MAX_SIZE];//存储结点的数组
    int n,r;//结点数量和树根的位置
}CTree;
//孩子表示法存储普通树
CTree initTree(CTree tree){
    printf("输入结点数量：\n");
    scanf("%d",&(tree.n));
    for(int i=0;i<tree.n;i++){
        printf("输入第 %d 个结点的值：\n",i+1);
        fflush(stdin);
        scanf("%c",&(tree.nodes[i].data));
        tree.nodes[i].firstchild=(ChildPtr*)malloc(sizeof(ChildPtr));
        tree.nodes[i].firstchild->next=NULL;

        printf("输入结点 %c 的孩子结点数量：\n",tree.nodes[i].data);
        int Num;
        scanf("%d",&Num);
        if(Num!=0){
            ChildPtr * p = tree.nodes[i].firstchild;
            for(int j = 0 ;j<Num;j++){
                ChildPtr * newEle=(ChildPtr*)malloc(sizeof(ChildPtr));
                newEle->next=NULL;
                printf("输入第 %d 个孩子结点在顺序表中的位置",j+1);
                scanf("%d",&(newEle->child));
                p->next= newEle;
                p=p->next;
            }
        }
    }
    return tree;
}

void findKids(CTree tree,char a){
    int hasKids=0;
    for(int i=0;i<tree.n;i++){
        if(tree.nodes[i].data==a){
            ChildPtr * p=tree.nodes[i].firstchild->next;
            while(p){
                hasKids = 1;
                printf("%c ",tree.nodes[p->child].data);
                p=p->next;
            }
            break;
        }
    }
    if(hasKids==0){
        printf("此结点为叶子结点");
    }
}

int main()
{
    CTree tree;
    tree = initTree(tree);
    //默认数根结点位于数组notes[0]处
    tree.r=0;
    printf("找出结点 F 的所有孩子结点：");
    findKids(tree,'F');
    return 0;
}

（2）孩子兄弟存储结构

即，孩子兄弟表示法。

采用的是链式存储结构，其存储树的实现思想是：从树的根结点开始，依次用链表存储各个结点的孩子结点和兄弟结点。

结点包含内容：

• 结点的值。
• 指向孩子结点的指针。
• 指向兄弟结点的指针。

​​

/*结点结构*/
#define ElemType char
typedef struct CSNode{
    ElemType data;
    struct CSNode * firstchild,*nextsibling;
}CSNode,*CSTree;

因此，孩子兄弟表示法可以作为将普通树转化为二叉树的最有效方法，通常又被称为"二叉树表示法"或"二叉链表表示法"。

​

​​

二、二叉树

（一）定义

1、二叉树

每个结点最多只有两个子树，且左右顺序不能颠倒。

​​

五种形态：

​​

2、满二叉树

如果二叉树中除了叶子结点，每个结点的度都为 2，则此二叉树称为满二叉树。

​​

3、完全二叉树

如果二叉树中除去最后一层节点为满二叉树，且最后一层的结点依次从左到右分布，则此二叉树被称为完全二叉树。

特有性质：n 个结点的完全二叉树的深度为 ⌊log2n⌋ + 1。

​​

（二）主要性质

1、二叉树性质

（1）非空二叉树上叶子结点数等于双分支结点数加 1。

即，叶子结点数为 n0 ，度为 2 的结点数为 n2，则 n0 = n2 +1。

设二叉树上叶子结点数为 n0 ，单分支结点为 n1，双分支结点 n2

• 总结点数： n0 + n1 + n2
• 总分支数： n1 + 2n2
• 总分支数 = 总结点数 - 1
• 空指针个数：n + 1

扩展：

在一课度为 m 的树中，度为 1 的结点树为 n1 ，度为 2 的结点树为 n2，……，度为 m 的结点树为 nm，则叶子结点数 n0 = 1 + n2 + 2n3 + …… + ( m - 1 ) nm。

• 总结点数 = n0 + n1 + n2 + …… + nm ①
• 总分支数 = 1* n1 + 2 * n2 + …… + m * nm ②
• 总分支数 = 总结点数 - 1 ③
• 三式联立化简得：n0 = 1 + n2 + 2n3 + …… + ( m - 1 ) nm

（2）二叉树第 i 层上最多有 2i-1 ( i >= 1 ) 个结点。

（3）高度（深度）为 k 的二叉树最多有 2k-1 ( k >= 1 ) 个结点。

（4）若有 n 个结点的完全二叉树， 若结点 a 的编号为 i ，则：

• ① 编号从 1 ~ n

  • a 的双亲结点编号：⌊ i / 2 ⌋
  • a 的左孩子结点编号：2i
  • a 的左孩子结点编号：2i+1

• ② 编号从 0 ~ n

  • a 的双亲结点编号：⌈ i / 2 ⌉ - 1
  • a 的左孩子结点编号：2i+1
  • a 的左孩子结点编号：2i+2

（5）具有 n ( n > = 1 ) 个结点的完全二叉树的高度（深度）为⌊ log2n ⌋ + 1。

2、完全二叉树

（1）总结点树为 m，叶子结点树为 n：

• 当 m 为奇数时，m = 2n0 - 1。
• 当 m 为偶数时，m = 2n0 。

（2）至少有 2k-1 个结点，至多有 2k - 1 个结点（k 为层次）。

3、满二叉树

满二叉树是一颗完全二叉树，必有 2k -1 个节点 ，叶子数为 2 k-1 。

满二叉树中不存在度为 1 的节点，每一个分支点中都两棵深度相同的子树，且叶子节点都在最底层。

具有 n 个节点的满二叉树的深度为 log2(n+1)。

（三）存储结构

1、顺序存储结构

二叉树的顺序存储，指的是使用顺序表（数组）存储二叉树。

需要注意的是，顺序存储只适用于完全二叉树。

换句话说，只有完全二叉树才可以使用顺序表存储。因此，如果我们想顺序存储普通二叉树，需要提前将普通二叉树转化为完全二叉树。

用于存储一般二叉树会浪费大量的存储空间，且考研不涉及。

具体代码看 一（三）1

2、链式存储结构（二叉链表）

二叉树结点结构：数据域（data）、左指针域（lchild）、右指针域（rchild）。

​​

​​

（1）结点结构定义

 typedef struct BTNode
 {
     int data;//可修改数据类型
     struct BTNode* lChild;
     struct BTNode* rChild;
 }BTNode;

（2）操作

 A1->lChild = A2;
 A1->rChild = A3;
 A2->lChild = A4;
 A2->rChild = NULL;
 A3->lChild = A5;
 A3->rChild = NULL;

（四）遍历算法（递归实现）

1、深度优先遍历（先序、中序、后序）

沿着下图路径行走：

• 先序遍历：第 1 次来到某个结点时访问，即得先序遍历序列。
• 中序遍历：第 2 次来到某个结点时访问，即得中序遍历序列。
• 后序遍历：第 3 次来到某个结点时访问，即得后序遍历序列。

二叉树的递归遍历要用到系统栈。因此，

• 先序遍历序列，即，各结点在入栈时进行打印所得的序列。
• 中序遍历序列，即，各结点在出栈时进行打印所得的序列。

​​

void r(BTNode* p)
{
    if (p != NULL)
    {
        //将“visit(p);”（或提前定义好的访问等操作函数）放在注释处，就可得到不同的遍历代码
        //(1)先序
        r(p->lChild);
        //(2)中序
        r(p->rChild);
        //(3)后序
    }
}

二叉树包括：根结点（N）、左子树（L）、右子树（R）

遍历共有 6 种方案：NLR（先序）、LNR（中序）、LRN（后序）、NRL、RLN、RNL

2、广度优先遍历（层次遍历）

一般情况，层次间从上至下，层内从左至右，先层内后层次。

• 要进行层次遍历，需建立一个循环队列。
• 先将二叉树头结点入队列，然后出队列，访问该结点。
• 若有左子树，则将左子树的根结点入队；若有右子树，则右子树的根结点入队。
• 然后出队，对出队结点访问。
• 如此反复，直到队列为空为止。

 void level(BTNode *bt)
 {
     if(bt != NULL)
     {
         int front, rear;
         BTNode *que[maxSize];
         front = rear = 0;
         BTNode *p;
         rear = (rear + 1) % maxSize;
         que[rear] = bt;
         while(front != rear)
         {
             front = (front + 1) % maxSize;
             p = que[front];
             Visit(p);
             if(p->lChild != NULL)
             {
                 rear = (rear + 1) % maxSize;
                 que[rear] = p->lChild;
             }
             if(p->rChild != NULL)
             {
                 rear = (rear + 1) % maxSize;
                 que[rear] = p->rChild;
             }
         }
     }
 }

3、双序遍历

二叉树的双序遍历：指对于二叉树的每一个结点来说，先访问这个结点，再按双序遍历它的左子树，然后再一次访问这个结点，接下来按双序遍历它的右子树。

 void Double_order (BTNode *t)
 {
     if(t!-NULL)
     {
         Visit(t);//Visit()是已经定义的访问t的函数
         Double order(t->1child);
         Visit(t);
         Doubleorder (t->rchild);
     }
 }

（五）非递归实现深度优先遍历算法

递归实现用系统栈，非递归实现用用户自己所定义的栈。但自定义用户栈比系统栈执行更高效。

解释：

• 递归函数所申请的系统栈，是一个所有递归函数都通用的栈。对于遍历算法，系统栈除了记录访问过的结点信息外，还有其他信息需记录，以实现函数的递归调用。
• 自定义用户栈仅保存了遍历所需的结点信息，是对遍历算法的一个针对性的设计，比系统栈更高效、专业。

1、先序遍历

算法过程：

• 初态栈空。

  • 1、结点元素入栈。
  • 2、结点出栈并访问。
  • 3、若结点左右孩子存在，则入栈（右孩子先入栈，左孩子后入栈）；若结点无左右孩子，则本不无孩子入栈。

• 循环执行 2、3 两步，直至栈空，所得序列即为先序遍历序列。

 void preorderNonrecursion(BTNode *bt)
 {
     if(bt != NULL)
     {
         BTNode *Stack[maxSize];//定义一个顺序栈
         int top = -1;//初始化栈
         BTNode *p = NULL;//定义临时指针
         Stack[++top] = bt;//根结点入栈
         while(top! = -1)//栈空循环退出，遍历结束
         {
             p = Stack[top--];//出栈并输出栈顶结点
             Visit(p);//访问p的函数
             if(p->rChild! = NULL)//栈顶结点的右孩子存在，则右孩子入栈
                 Stack[++top] = p->rChild;
             if(p->lChild! = NULL)//栈顶结点的左孩子存在，则左孩子入栈
                 Stack[++top] = p->lChild;
         }
     }
 }

2、中序遍历

算法过程：

• 开始根结点入栈。

• 循环执行如下操作：

  • 1、若栈顶结点左孩子存在，则左孩子入栈。
  • 2、若栈顶结点左孩子不存在，则出栈并输出栈顶结点。
  • 3、检查右孩子是否存在，若存在入栈。

• 当栈空时算法结束。

 void inorderNonrecursion(BTNode *bt)
 {
     if(bt != NULL)
     {
         BTNode *Stack[maxSize]; int top = -1;//定义顺序栈
         BTNode *p = NULL;//临时指针
         p = bt;
         /*以下循环完成中序遍历*/
         while(top != -1 || p != NULL)
         {
             while(p != NULL)//左孩子存在，则左孩子入栈
             {
                 Stack[++top]=p;
                 p = p->lChild;
             }
             if(top != -1)//在栈不空的情况下出栈并输出出栈结点
             {
                 p = Stack[top--];
                 Visit(p);
                 p = p->rChild;
             }
         }
     }
 }

3、后序遍历

算法过程：

• 初态栈空

  • 1、结点入栈 ①。
  • 2、结点出栈 ①，并入栈 ②。
  • 3、若结点左右孩子存在，则入栈 ①（入栈顺序：先左后右）；若结点无孩子，则本步无操作。
  • 4、循环执行 2、3 两步，直至栈 ① 为空。
  • 5、将栈 ② 元素输出，出栈序列即为后序遍历序列。

 void postorderNonrecursion(BTNode *bt)
 {
     if (bt!=NULL)
     {
         /*定义两个栈*/
         BTNode *Stack1[maxSize]; int top1=-1;
         BTNode *Stack2[maxSize]; int top2=-1;
         BTNode *p = NULL;
         Stack1[++top1] = bt;
         while (top1 != -1)
         {
             p = Stack1[top1--];
             Stack2[++top2] = p;//与先序有区别，输出改为入stack2
             /*以下两个if和先序区别：左右孩子入栈的顺序相反*/
             if (p->lChild != NULL)
                 Stack1[++top1] = p->lChild;
             if (p->rChild != NULL)
                 Stack1[++top1] = p->rChild;
         }
         while (top2 != -1)
         {
             /**出栈序列即为后序遍历序列/
             p = Stack2[top2--];
             Visit(p);
         }
     }
 }

（六）线索二叉树

线索化二叉树将空链域利用起来，通过线索的辅助寻找当前结点的前驱或后继，遍历过程线索化，提高效率。

常考中序线索二叉树

1、线索化概念

（1）含义

二叉树以某种次序遍历并修改空指针使其变成线索二叉树的过程称为线索化。

（2）实质

线索二叉树实际上就是使用这些空指针域来存储结点之间前趋和后继关系的一种特殊的二叉树。

即，将二叉链表中的空指针改成指向前驱或后继的线索。

线索化的过程，即，在遍历的过程中修改空指针的过程。

（3）分类

• 前序线索二叉树：找后继结点、带线索的前驱结点容易，未带线索的前驱结点寻找困难。
• 中序线索二叉树：找前驱、后继结点都容易。
• 后序线索二叉树：找前驱、后继结点都困难。

2、线索化规则

设结点 A ，

• 若 A 有左空指针，则遍历序列的前一个结点为前驱结点。
• 若 A 有右空指针，则遍历序列的后一个结点为后继结点。
• 若 A 左右指针不空，则不进行线索化。
• 线索化指针用虚线标出。

​​

3、线索化二叉树的构造

结点结构如下：

​​

• 若 ltag = 0 ，则表示 lchild 为指针，指向结点的左孩子；若 ltag = 1 ，则表示 lchild 为线索，指向结点的直接前驱。
• 若 rtag = 0 ，则表示 rchild 为指针，指向结点的右孩子；若 rtag = 1 ，则表示 rchild 为线索，指向结点的直接后继。

 typedef struct TBTNode
 {
     char data;
     int ltag,rtag;//线索标记
     struct TBTNode *lchild;
     struct TBTNode *rchild;
 }TBTNode;

4、中序线索二叉树

在中序线索二叉树中，结点 X 的前驱即为中序遍历序列中 X 的前驱。

对于中序遍历，要访问结点 X，必须把 X 左子树中的结点都访问完才可以，因此 X 左子树中最后一个被访问的结点即为 X 的前驱结点；而 X 左子树中的最右边的结点即为左子树中最后一个被访问的结点。

（1）中序线索化二叉树

 void inThread(TBTNode *p, TBTNode *&pre)
 {
     if(p != NULL)
     {
         inThread(p->lChild, pre);//递归，左子树线索化
         if(p->lChild == NULL)
         {//建立当前结点的前驱线索
             p->lChild = pre;
             p->lTag = 1;
         }
         if(pre != NULL && pre->rChild == NULL)
         {//建立当前结点的后继结点
             pre->rChild = p;
             pre->rTag = 1;
         }
         pre = p;
         /*pre指向当前的p，作为p将要指向的下一个结点的前驱结点指示指针p指向一个新结点，此时pre和p分别指向的结点形成了一个前驱后继对为下次线索的连接做准备*/
         inThread(p->rChild, pre);//递归，右子树线索化
         /*以上两步可拆分成以下三步：
 pre = p;
 p=p->rchild;
 inThread(p, pre);
         */
     }
 }

（2）通过中序遍历建立中序线索化二叉树主程序

 void createInThread(TBTNode *root)
 {
     TBTNode *pre=NULL;
     if(root!=NULL)
     {
         inThread(root,pre);
         pre->rchild=NULL;//非空二叉树，线索化后
         pre->rtage=1;//处理中序最后一个结点
     }
 }

（3）遍历中序线索二叉树

① 查找，以 p 为根，中序序列的第一个结点

 TBTNode *First(TBBTNode *p)
 {
     while(p->ltag==0)
         p=p->lchilde;//最左下结点（不一定是叶子结点）
     return p;
 }

② 查找，结点 p 在中序下的后继结点

 TBTNode *Next(TBTNode *p)
 {
     if(p->rtae==0)
         return First(p->rchild);
     else
         return p->rchild;//rtag==1，直接返回后继线索
 }

③ 中序遍历算法

 void inOrder(TBTNode *root)
 {
     for(TBTNode *p=First(root);p!=NULL;p=Next(p))
         visit(p);
 }

5、前序线索二叉树

（1）前序线索二叉树

 void preThread(TBTNode *p,TBTNode *&pre)
 {
     if(p != NULL)
     {
         if(p->lChild == NULL)
         {
             p->lChild = pre;
             p->lTag = 1;
         }
         if(pre != NULL &&pre->rChild == NULL)
         {
             pre->rChild = p;
             pre->rTag = 1;
         }
         pre = p;
         /*注意，这里再递归入口处有限制条件，左、右指针不是线索化才能继续递归*/
         if(p->lTag == 0)
             preThread(p->lChild, pre);
         if(p->rTag == 0)
             preThread(p->rChild, pre);
     }
 }

（2）遍历前序线索二叉树

 void preOrder(TBTNode *tbt)
 {
     if(tbt != NULL)
     {
         TBTNode *p = tbt;
         while(p != NULL)
         {
             while(p->lTag == 0)//左指针不是线索，则边访问边左移
             {
                 Visit(p);
                 p = p->lChild;
             }
             Visit(p);//此时p左指针必为线索，但还没被访问，则访问
             p = p->rChild;//此时p左孩子不存在，则右指针若非空，则不论是否为线索都   指向其后继。
         }
     }
 }

6、后序线索二叉树

（1）后序线索二叉树

 void postThread(TBTNode *p,TBTNode *&pre)
 {
     if(p != NULL)
     {
         postThread(p->lChild, pre);//递归，左子树线索化
         postThread(p->rChild, pre);//递归，右子树线索化
         if(p->lChild == NULL)
         {//建立当前结点的前驱线索
             p->lChild = pre;
             p->lTag = 1;
         }
         if(pre != NULL&&pre->rChild == NULL)
         {//建立前驱结点的后继线索
             pre->rChild = p;
             pre->rTag = 1;
         }
         pre = p;
     }
 }

（2）遍历后序线索二叉树

对于后序线索二叉树，出现的题目最多是手工找出当前结点的后继，因此只需记住三点：

• 若结点 x 是二叉树的根，则其后继为空。
• 若结点 x 是其双亲的右孩子，或是其双亲的左孩子且双亲没有右子树，则其后继即为双亲结点。
• 若结点 x 是其双亲的左孩子，且其双亲有右子树，则其后继为双亲右子树上按后序遍历列出的第一个结点。

7、三种线索二叉树对比

​​

​​

三、根据遍历序列确定二叉树

（一）先序 + 中序

步骤：

1. 先序中，第一个结点为根结点。
2. 中序中，根结点将中序分为两个子序列，前一个为左子树中序序列，后一个为右子树中序序列。
3. 根据这两个子序列，在先序中找到对应左右子序列，并找到新的根结点。
4. 递归处理，直至序列分配完毕，画出二叉树。

 BTNode *CreateBT(char pre[], char in[], int L1, int R1, int L2, int R2)
 {
     if(L1 > R1)
         return NULL;
   
     BTNode *s = (BTNode *)malloc(sizeof(BTNode));
     s->lChild = s->rChild = NULL;
     s->data = pre[L1];
   
     int i;
     for(i = L2;i <= R2; ++i)
         if(in[i] == pre[L1])
             break;
   
     s->lChild = CreateBT(pre, in, L1+1, L1+i-L2, L2,i-1);
     s->rChild = CreateBT(pre, in, L1+i-L2+1, R1, i+1, R2);
   
     return s;
 }

（二）后序 + 中序

步骤：

1. 后序中，根结点在序列尾部（最后一个）。
2. 中序中，根据根结点找到左右子树及子序列。
3. 根据左、右子序列在后序中找到对应序列，并找到新的根结点。
4. 递归处理，直至序列分配完毕，画出二叉树。

 BTNode *CreateBT2(char post[], char in[], int L1, int R1, int L2, int R2)
 {
     if(L1 > R1)
         return NULL;
     BTNode *s = (BTNode *)malloc(sizeof(BTNode));
     s->lChild = s->rChild = NULL;
     s->data = post[R1];
   
     int i;
     for(i = L2;i <= R2; ++i)
         if(in[i] == post[R1])
             break;
   
     s->lChild = CreateBT2(post, in, L1, L1+i-L2-1, L2, i-1);
     s->rChild = CreateBT2(post, in, L1+i-L2, R1-1, i+1, R2);
   
     return s;
 }

（三）层次 + 中序

步骤：

1. 层次中，第一个结点为根结点。
2. 中序中，根据根结点找到左右子树及子序列。
3. 根据上两步，在层次中找到相对应的散乱的左右子序列。
4. 递归处理，直至序列分配完毕，画出二叉树。

 BTNode *CreateBT3(char level[], char in[], int n, int L, int R)
 {
     if(L > R)
         return NULL;
     BTNode *s = (BTNode *)malloc(sizeof(BTNode));
     s->lChild = s->rChild = NULL;
     s->data = level[0];
   
     int i = search(in, level[0], L, R);
     int LN = i-L; char LLevel[LN];
     int RN = R-i; char RLevel[RN];
   
     getSubLevel(LLevel, level, in, n, L, i-1);
     getSubLevel(RLevel, level, in, n, i+1, R);
   
     s->lChild = CreateBT3(LLevel, in, LN, L, i-1);
     s->rChild = CreateBT3(RLevel, in, RN, i+1, R);
   
     return s;
 }
 ​
 int search(char arr[], char key, int L, int R)
 {
     int idx;
     for(idx = L; idx <= R; ++idx)
         if(arr[idx] == key)
             return idx;
     return -1;
 }
 ​
 void getSubLevel(char subLevel[],char level[],char in[],int n,int L,int R)
 {
     int k = 0;
     for(int i = 0; i < n; ++i)
         if (search(in, level[i], L, R) != -1)
             subLevel[k++] = level[i];
 }

​

​

​​

四、二叉树的估计

设 T 为根结点，L 为所有左子树，R 为所有右子树。

根据题意中所要求的二叉树形状，通过局部删减左（右）子树，得出相应序列并画图。

二叉树形状及其条件：

1. 前序、后序结果相同： T L R ，L R T
2. 前序、中序结果相同： T L R ，L T R
3. 中序、后序结果相同： L T R ，L R T
4. 前序、后序结果相反： T L R ，L R T ；T L R ，L R T
5. 前序、中序结果相反： T L R ，L T R
6. 中序、后序结果相反： L T R ，L R T

删除线为要去除的子树

​​

五、树、森林、二叉树的互相转换

（一）树与二叉树间的转化

1、树 -> 二叉树

• 将同一结点的各孩子用线串起来。
• 将每个结点的分支从左往右除了第一个外，其余都去掉。
• 调整结点使其符合二叉树的层次结构。

2、二叉树-> 树

• 先把二叉树从左上到右下分为若干层，并调整成水平方向。
• 找到每一层的结点在其上一层的父结点。
• 将每一层的结点和其父结点相连，然后删除每一层结点间的连接，最后得到的树。

（二）森林与二叉树间的转化

​​

1、森林 -> 二叉树

• 将森林中所有的树转换成二叉树。
• 除第一棵转换后的二叉树外，剩余所有的转换后的二叉树都连接到上一个二叉树根结点的右孩子位置，充当起树根的右子树。
• 将得到的大树调整位置，即得到一棵森林转化后的二叉树。

森林中若有像二叉树形态的树也需要进行转化

2、二叉树-> 森林

只断开跟与右子树的链接。

• 需不停地将根结点有右孩子的二叉树的右孩子链接断开，直到不存在的根结点有右孩子的二叉树为止。
• 将得到的多颗二叉树按照二叉树转化为树的规则依次转化即可。

3、结点间关系

若在转换后的二叉树中，结点 u 是结点 v 的父结点的父结点，则在原来的森林中 u 与 v 的可能是父子关系或兄弟关系。

根据左孩子右兄弟原则，

• v 跟自己的父结点是兄弟关系，都是 u 的孩子。
• v 跟自己的父结点以及 u 是兄弟关系，都是 u 的父结点的孩子。

（三）遍历

1、树的遍历

树的遍历有两种方式：先序遍历、后序遍历

• 先序遍历：先访问根结点，然后先序遍其所有子树。
  对应二叉树的先序遍历。
• 后序遍历：先后序遍所有子树，最后访问根结点。
  对应二叉树的中序遍历。​

（1）深度优先遍历

 void postOrder(TNode* p, TNode tree[])
 {
     if (p != NULL)
     {
         //先序遍历结点访问Code所在行
         Branch* q;
         q = p->first;
         while (q != NULL)
         {
             postOrder(&tree[q->cIdx], tree);
             q = q->next;
         }
         //后序遍历结点访问Code所在行
     }
 }

（2）层次遍历

 void level(TNode *tn, TNode tree[])
 {
     int front, rear;
     TNode *que[maxSize];
     front = rear = 0;
     TNode *p;
     if(tn != NULL)
     {
         rear = (rear + 1) % maxSize;
         que[rear] = tn;
         while(front != rear)
         {
             front = (front + 1) % maxSize;
             p = que[front];
             visit(p);
             Branch* q = p->first;
             while (q != NULL)
             {
                 rear = (rear + 1) % maxSize;
                 que[rear] = &tree[q->cIdx];
                 q = q->next;
             }
         }
     }
 }

2、森林的遍历

• 先序遍历：先序遍历森林中每一棵树。
• 后序遍历：后序遍历森林中每一棵树。

​

​

​​

六、哈夫曼树（赫夫曼树）及哈夫曼编码

（一）相关概念

1、哈夫曼树

又称最优二叉树、赫夫曼树。

当用 n 个结点（都做叶子结点且都有各自的权值）试图构建一棵树时，如果构建的这棵树的带权路径长度最小，称这棵树为哈夫曼树。

特点：

• 1、树的带权路径最短。
• 2、权值（权重）越大的结点离树根越近。
• 3、树中没有度为 1 的结点，此类树又叫正则（严格）二叉树。
• 4、不含单分支结点。

2、相关概念

• 路径：指从树中一个结点到另一个结点的分支所构成的路线。

• 路径长度：指路径上的分支数目。

  在一条路径中，每经过一个结点，路径长度都要加 1。

• 结点的权：给每一个结点赋予一个新的数值，被称为这个结点的权。

• 树的路径长度：指从根到每个结点的路径长度之和。

• 带权路径长度 = 结点到根的路径长度 * 结点的权值。

• 树的带权路径长度（WPL）：指树中所有叶子结点的带权路径长度之和。

  WPL = 7 * 1 + 5 * 2 + 2 * 3 + 4 * 3 = 35

​​

3、性质

（1）度为 m 的哈夫曼树中，叶子结点数为 n，则非叶子结点数为⌈ (n-1) / (m-1) ⌉。

在构造度为 m 的赫夫曼树的过程中，每次把 m 个叶子结点合并为一个父结点（第一次合并可能少于 m 个子结点)，每次合并减少 m-1 个结点，从 n 个叶子结点减少到最后只剩一个父结点共需要⌈ (n-1) / (m-1) ⌉次合并，每次合并增加一个非叶子结点。

（二）哈夫曼二叉树的构造方法

给定 n 个权值：

1. 将这 n 个权值分别看作只有根结点的 n 棵二叉树，所构成的集合记为 F。
2. 从 F 中选出两棵结点的权值最小的数（假设为 a、b）作为左、右子树，构造一颗新的二叉树（假设为 c），新的二叉树的根结点的权值为左、右子树根结点权值之和。
3. 从 F 中删除 a、b，加入新构造的树 c。
4. 循环 2、3 两步，直到 F 中只剩下一棵树为止，此树为哈夫曼树。

​​

（A）给定了四个结点 a，b，c，d，权值分别为 7，5，2，4；第一步如（B）所示，找出现有权值中最小的两个，2 和 4 ，相应的结点 c 和 d 构建一个新的二叉树，树根的权值为 2 + 4 = 6，同时将原有权值中的 2 和 4 删掉，将新的权值 6 加入；进入（C），重复之前的步骤。直到（D）中，所有的结点构建成了一个全新的二叉树，这就是哈夫曼树。

在构造哈夫曼二叉树时，每次选取权值最小的两个结点来生成新的结点，所构成的树不一定是往某个分支一直走，也有可能是普通二叉树的模样（如下图）。若有 3 个以上的结点值相同，则任选两个。虽然得到的二叉树的外表不同，但是其带权路径长度总是相同的。

​​

（三）哈夫曼编码

哈夫曼编码就是在哈夫曼树的基础上构建的，这种编码方式最大的优点就是用最少的字符包含最多的信息内容。

• 根据发送信息的内容，通过统计文本中相同字符的个数作为每个字符的权值，建立哈夫曼树。
• 对于树中的每一个子树，统一规定其左孩子标记为 0 ，右孩子标记为 1 。
• 从根结点到每个结点的路径上的数字序列，即为该字符的哈夫曼编码。

哈夫曼编码为前缀码，即编码中任何一个序列都不是另一个序列的前缀。

​​

注：​

文本中字符出现的次数越多，在哈夫曼树中的体现就是越接近树根。编码的长度越短。

对于同一组结点，构造出的哈夫曼树可能不是唯一。

（四）哈夫曼 n 叉树

对于结点数目大于等于 2 的待处理序列，都可构造哈夫曼二叉树，，但不一定能构造哈夫曼 n 叉树。

当发现无法构造时，需补上权值为 0 的结点让整个序列凑成可构造哈夫曼 n 叉树的序列。

​

​

​​

七、满二叉树先序、中序、后序的相互转化

满二叉树先序、中序、层序遍历方式的相互转化，知一求二。

下面这道满二叉树三种遍历方式的相互转化，代码来自满二叉树先序、中序和后序之间的转换。为了便于实现，全部采用了树的顺序存储结构。

其实思想都是一样的，确定左右子树的下标位置，依次递归遍历每个子树，每次都选定根节点进行赋值。

（一）先序转后序/后序转先序

• tmp：满二叉树先序遍历首尾节点的差的平均数，可知即为先序遍历时左子树的最后一个节点。
• 后序转先序，看的出逻辑差不多，只是把已知和未知换了个位置，post 变成了已知，pre 变成了未知。

 //先序序列转换为后序序列
 //参数说明：  (in)   pre       ————  先序数组
 //           (out)  post      ————  后序数组
 //           (in)   preLow    ————  先序的第一个结点的下标
 //           (in)   preHigh   ————  先序的最后一个结点的下标
 //           (in)   postLow   ————  后序的第一个结点的下标
 //           (in)   postHigh  ————  后序的最后一个结点的下标
 void PreToPost(int pre[], int post[], int preLow, int preHigh, int postLow, int postHigh)
 {
     if (preHigh >= preLow)
     {
         post[postHigh] = pre[preLow];
         int tmp = (preHigh - preLow) / 2;
         PreToPost(pre, post, preLow + 1, preLow + tmp, postLow, postLow + tmp - 1);
         PreToPost(pre, post, preLow + tmp + 1, preHigh, postLow + tmp, postHigh - 1);
     }
 }
 //后序序列转换为先序序列
 //参数说明：  (out)  pre       ————  先序数组
 //           (in)   post      ————  后序数组
 //           (in)   preLow    ————  先序的第一个结点的下标
 //           (in)   preHigh   ————  先序的最后一个结点的下标
 //           (in)   postLow   ————  后序的第一个结点的下标
 //           (in)   postHigh  ————  后序的最后一个结点的下标
 void PostToPre(int pre[], int post[], int preLow, int preHigh, int postLow, int postHigh)
 {
     if (postHigh >= postLow)
     {
         pre[preLow] = post[postHigh];
         int tmp = (postHigh - postLow) / 2;
         PostToPre(pre, post, preLow + 1, preLow + tmp, postLow, postLow + tmp - 1);
         PostToPre(pre, post, preLow + tmp + 1, preHigh, postLow + tmp, postHigh - 1);
     }
 }
 ​

（二）先序转中序/中序转先序

• 同理

 //先序序列转换为中序序列
 //参数说明：  (in)  pre       ————  先序数组
 //           (out)  mid       ————  中序数组
 //           (in)   preLow    ————  先序的第一个结点的下标
 //           (in)   preHigh   ————  先序的最后一个结点的下标
 //           (in)   midLow    ————  中序的第一个结点的下标
 //           (in)   midHigh   ————  中序的最后一个结点的下标
 void PreToMid(int pre[], int mid[], int preLow, int preHigh, int midLow, int midHigh)
 {
     if (preHigh >= preLow)
     {
         mid[(midHigh + midLow) / 2] = pre[preLow];
         int tmp = (preHigh - preLow) / 2;
         PreToMid(pre, mid, preLow + 1, preLow + tmp, midLow, midLow + tmp - 1);
         PreToMid(pre, mid, preLow + tmp + 1, preHigh, midLow + tmp + 1, midHigh);
     }
 }
 ​
 //中序序列转换为先序序列
 //参数说明：  (out)  pre       ————  先序数组
 //           (in)   mid       ————  后序数组
 //           (in)   preLow    ————  先序的第一个结点的下标
 //           (in)   preHigh   ————  先序的最后一个结点的下标
 //           (in)   midLow    ————  中序的第一个结点的下标
 //           (in)   midHigh   ————  中序的最后一个结点的下标
 void MidToPre(int pre[], int mid[], int preLow, int preHigh, int midLow, int midHigh)
 {
     if (midHigh >= midLow)
     {
         int tmp = (midHigh - midLow) / 2;
         pre[preLow] = mid[(midHigh + midLow) / 2];
         MidToPre(pre, mid, preLow + 1, preLow + tmp, midLow, midLow + tmp - 1);
         MidToPre(pre, mid, preLow + tmp + 1, preHigh, midLow + tmp + 1, midHigh);
     }
 }
 ​

（三）后序转中序/中序转后序

 //后序序列转换为中序序列
 //参数说明：  (in)  post       ————  后序数组
 //           (out)  mid       ————  中序数组
 //           (in)   postLow   ————  后序的第一个结点的下标
 //           (in)   postHigh  ————  后序的最后一个结点的下标
 //           (in)   midLow    ————  中序的第一个结点的下标
 //           (in)   midHigh   ————  中序的最后一个结点的下标
 void PostToMid(int post[], int mid[], int midLow, int midHigh, int postLow, int postHigh)
 {
     if (postHigh >= postLow)
     {
         mid[(midHigh + midLow) / 2] = post[postHigh];
         int tmp = (postHigh - postLow) / 2;
         PostToMid(post, mid, midLow, midLow + tmp - 1, postLow, postLow + tmp - 1);
         PostToMid(post, mid, midLow + tmp + 1, midHigh, postLow + tmp, postHigh - 1);
     }
 }
 ​
 //中序序列转换为后序序列
 //参数说明：  (out)  post      ————  后序数组
 //           (in)   mid       ————  中序数组
 //           (in)   postLow   ————  后序的第一个结点的下标
 //           (in)   postHigh  ————  后序的最后一个结点的下标
 //           (in)   midLow    ————  中序的第一个结点的下标
 //           (in)   midHigh   ————  中序的最后一个结点的下标
 void MidToPost(int post[], int mid[], int midLow, int midHigh, int postLow, int postHigh)
 {
     if (midHigh >= midLow)
     {
         post[postHigh] = mid[(midHigh + midLow) / 2];
         int tmp = (midHigh - midLow) / 2;
         MidToPost(post, mid, midLow, midLow + tmp - 1, postLow, postLow + tmp - 1);
         MidToPost(post, mid, midLow + tmp + 1, midHigh, postLow + tmp, postHigh - 1);
     }
 }
 ​

（四）整体 Code

 #include <bits/stdc++.h>
 using namespace std;
 ​
 //*****************************满二叉树先序、中序和后序之间的转换*****************************begin
 ​
 //先序序列转换为后序序列
 //参数说明：  (in)   pre       ————  先序数组
 //           (out)  post      ————  后序数组
 //           (in)   preLow    ————  先序的第一个结点的下标
 //           (in)   preHigh   ————  先序的最后一个结点的下标
 //           (in)   postLow   ————  后序的第一个结点的下标
 //           (in)   postHigh  ————  后序的最后一个结点的下标
 void PreToPost(int pre[], int post[], int preLow, int preHigh, int postLow, int postHigh)
 {
     if (preHigh >= preLow)
     {
         post[postHigh] = pre[preLow];
         int tmp = (preHigh - preLow) / 2;
         PreToPost(pre, post, preLow + 1, preLow + tmp, postLow, postLow + tmp - 1);
         PreToPost(pre, post, preLow + tmp + 1, preHigh, postLow + tmp, postHigh - 1);
     }
 }
 ​
 //后序序列转换为先序序列
 //参数说明：  (out)  pre       ————  先序数组
 //           (in)   post      ————  后序数组
 //           (in)   preLow    ————  先序的第一个结点的下标
 //           (in)   preHigh   ————  先序的最后一个结点的下标
 //           (in)   postLow   ————  后序的第一个结点的下标
 //           (in)   postHigh  ————  后序的最后一个结点的下标
 void PostToPre(int pre[], int post[], int preLow, int preHigh, int postLow, int postHigh)
 {
     if (postHigh >= postLow)
     {
         pre[preLow] = post[postHigh];
         int tmp = (postHigh - postLow) / 2;
         PostToPre(pre, post, preLow + 1, preLow + tmp, postLow, postLow + tmp - 1);
         PostToPre(pre, post, preLow + tmp + 1, preHigh, postLow + tmp, postHigh - 1);
     }
 }
 ​
 //先序序列转换为中序序列
 //参数说明：  (in)  pre       ————  先序数组
 //           (out)  mid       ————  中序数组
 //           (in)   preLow    ————  先序的第一个结点的下标
 //           (in)   preHigh   ————  先序的最后一个结点的下标
 //           (in)   midLow    ————  中序的第一个结点的下标
 //           (in)   midHigh   ————  中序的最后一个结点的下标
 void PreToMid(int pre[], int mid[], int preLow, int preHigh, int midLow, int midHigh)
 {
     if (preHigh >= preLow)
     {
         mid[(midHigh + midLow) / 2] = pre[preLow];
         int tmp = (preHigh - preLow) / 2;
         PreToMid(pre, mid, preLow + 1, preLow + tmp, midLow, midLow + tmp - 1);
         PreToMid(pre, mid, preLow + tmp + 1, preHigh, midLow + tmp + 1, midHigh);
     }
 }
 ​
 //中序序列转换为先序序列
 //参数说明：  (out)  pre       ————  先序数组
 //           (in)   mid       ————  后序数组
 //           (in)   preLow    ————  先序的第一个结点的下标
 //           (in)   preHigh   ————  先序的最后一个结点的下标
 //           (in)   midLow    ————  中序的第一个结点的下标
 //           (in)   midHigh   ————  中序的最后一个结点的下标
 void MidToPre(int pre[], int mid[], int preLow, int preHigh, int midLow, int midHigh)
 {
     if (midHigh >= midLow)
     {
         int tmp = (midHigh - midLow) / 2;
         pre[preLow] = mid[(midHigh + midLow) / 2];
         MidToPre(pre, mid, preLow + 1, preLow + tmp, midLow, midLow + tmp - 1);
         MidToPre(pre, mid, preLow + tmp + 1, preHigh, midLow + tmp + 1, midHigh);
     }
 }
 ​
 //后序序列转换为中序序列
 //参数说明：  (in)  post       ————  后序数组
 //           (out)  mid       ————  中序数组
 //           (in)   postLow   ————  后序的第一个结点的下标
 //           (in)   postHigh  ————  后序的最后一个结点的下标
 //           (in)   midLow    ————  中序的第一个结点的下标
 //           (in)   midHigh   ————  中序的最后一个结点的下标
 void PostToMid(int post[], int mid[], int midLow, int midHigh, int postLow, int postHigh)
 {
     if (postHigh >= postLow)
     {
         mid[(midHigh + midLow) / 2] = post[postHigh];
         int tmp = (postHigh - postLow) / 2;
         PostToMid(post, mid, midLow, midLow + tmp - 1, postLow, postLow + tmp - 1);
         PostToMid(post, mid, midLow + tmp + 1, midHigh, postLow + tmp, postHigh - 1);
     }
 }
 ​
 //中序序列转换为后序序列
 //参数说明：  (out)  post      ————  后序数组
 //           (in)   mid       ————  中序数组
 //           (in)   postLow   ————  后序的第一个结点的下标
 //           (in)   postHigh  ————  后序的最后一个结点的下标
 //           (in)   midLow    ————  中序的第一个结点的下标
 //           (in)   midHigh   ————  中序的最后一个结点的下标
 void MidToPost(int post[], int mid[], int midLow, int midHigh, int postLow, int postHigh)
 {
     if (midHigh >= midLow)
     {
         post[postHigh] = mid[(midHigh + midLow) / 2];
         int tmp = (midHigh - midLow) / 2;
         MidToPost(post, mid, midLow, midLow + tmp - 1, postLow, postLow + tmp - 1);
         MidToPost(post, mid, midLow + tmp + 1, midHigh, postLow + tmp, postHigh - 1);
     }
 }
 ​
 //*****************************满二叉树先序、中序和后序之间的转换*****************************end
 ​
 int main()
 {
     int Pre[15] = {1, 2, 4, 8, 9, 5, 10, 11, 3, 6, 12, 13, 7, 14, 15};
     int PreChangeToMid[15] = {0};
     int PreChangeToPost[15] = {0};
     cout<<"**************************前序转换为中序**************************"<<endl<<endl;
     PreToMid(Pre, PreChangeToMid, 0, 14, 0, 14);
     for (int i = 0; i < 15; i++)
     {
         cout<<PreChangeToMid[i]<<"    ";
     }
     cout<<endl;
     cout<<endl<<"**************************前序转换为后序**************************"<<endl<<endl;
     PreToPost(Pre, PreChangeToPost, 0, 14, 0, 14);
     for (int i = 0; i < 15; i++)
     {
         cout<<PreChangeToPost[i]<<"    ";
     }
 ​
     int Mid[15] = {8, 4, 9, 2, 10, 5, 11, 1, 12, 6, 13, 3, 14, 7, 15};
     int MidChangeToPre[15] = {0};
     int MidChangeToPost[15] = {0};
     cout<<endl;
     cout<<endl<<"**************************中序转换为前序**************************"<<endl<<endl;
     MidToPre(MidChangeToPre, Mid, 0, 14, 0, 14);
     for (int i = 0; i < 15; i++)
     {
         cout<<MidChangeToPre[i]<<"    ";
     }
     cout<<endl;
     cout<<endl<<"**************************中序转换为后序**************************"<<endl<<endl;
     MidToPost(MidChangeToPost, Mid, 0, 14, 0, 14);
     for (int i = 0; i < 15; i++)
     {
         cout<<MidChangeToPost[i]<<"    ";
     }
 ​
     int Post[15] = {8, 9, 4, 10, 11, 5, 2, 12, 13, 6, 14, 15, 7, 3, 1};
     int PostChangeToPre[15] = {0};
     int PostChangeToMid[15] = {0};
     cout<<endl;
     cout<<endl<<"**************************后序转换为前序**************************"<<endl<<endl;
     PostToPre(PostChangeToPre, Post, 0, 14, 0, 14);
     for (int i = 0; i < 15; i++)
     {
         cout<<PostChangeToPre[i]<<"    ";
     }
     cout<<endl;
     cout<<endl<<"**************************后序转换为中序**************************"<<endl<<endl;
     PostToMid(Post, PostChangeToMid, 0, 14, 0, 14);
     for (int i = 0; i < 15; i++)
     {
         cout<<PostChangeToMid[i]<<"    ";
     }
 ​
     cout<<endl;
     return 0;
 }
 ​
 ​

​

​

​​

八、扩展

1、若二叉树采用二叉链表存储结构，要交换所有分支结点左、右子树的位置，利用后序遍历最合适。

使用递归进行以下操作：先递归交换左子树中的所有分支结点，再递归交换右子树中的所有分支结点，最后对根结点交换其所有子树位置。（对应后序遍历）

2、满二叉树前序遍历序列转化为后序遍历序列。

序列中第一个元素即为根结点。将除去第一个元素之外的元素序列分成前后相等长度的两半，前一半为左子树上的结点，后一半为右子树上的结点。只需将根结点移动到整个序列的末尾，然后分别递归地去处理序列的前一半和后一半即可。

“前转中”、“中转后”、“后转前”、“中转前”的思想与这个相同。

3、设中序线索二叉树的类型为 TBTNode InThTree。

1. 设计算法，在一棵中序线索二叉树中寻找结点 t 的子树上中序下的最后一个结点。
   算法的思路：沿结点 t 的右子树链一直走下去，直到遇到其右指针为右线索的结点为止，该结点即为所求。

    TBTNode* inLast (TBTNode *t)
    {
        TBTNode *p=t;
        while(p && !p->rtag)
           p=p->rchild; 
        return p;
    }
   

2. 设计算法，在一棵中序线索二叉树中寻找结点 t 的中序下的前驱。
   算法的思路：若结点 t 有左线索，则其左线索所指结点即为其中序前驱；若无左线索，则其左子树中中序的最后一个结点即为它的中序前驱。

    TBTNode* inPrior (TBTNode *t)
    {
        TBTNode *p=->lchild;
        if(p && !t->ltag)
            p=inLast(p);
        return P;
    }
   

4、满 K 叉树的扩展

一个高度为 L 的满 K 叉树有以下性质：第 L 层上的结点都是叶子结点，其余各层上每个结点都有 K 棵非空子树，如果从上到下、自左至右，对 K 叉树中全部结点进行编号〈根结点编号为 1)，求:

1. 各层的结点的数目是多少?

   满 K 叉树各层的结点数构成一个首项为 1、公比为 K 的等比数列，则各层结点数为 Kh-1 ，其中 h 为层号。

2. 编号为 n 的结点的双亲结点〔若存在)的编号是多少?

   因为该树每层上均有 Kh-1个结点，从根开始编号为 1，则结点 i 从右向左数第 2 个孩子的结点编号为 K*i。

   设 n 为结点 i 的子女，则关系式(i-1) * K+2 <= n <= i * K+1 成立。因 i 是整数，故结点 n 的双亲 i 的编号为 ⌊(n-2)/k⌋+1

3. 编号为 n 的结点的第 i 个孩子结点（若存在)的编号是多少?

   结点 n 的前一结点编号为 n-1，其最右边子女编号是(n-1) * K+1，故结点 n 的第 i 个孩子的编号是 (n-1) * K+1+i。

4. 编号为 n 的结点有右兄弟的条件是什么?如果有。其右兄弟的编号是多少?

   结点 n 有右兄弟的条件是，它不是双亲的从右数的第一个子女，即(n-1) mod K≠0，其右兄弟编号是 n+1。

​​

参考资料

个人学习记录，若有侵权，请留言联系

• 2022 天勤计算机考研高分笔记-数据结构
• 2022 王道计算机考研复习指导-数据结构
• 解学武数据结构与算法教程（C 语言版）：http://data.biancheng.net/