数据结构——树与二叉树

树

介绍

• n个节点的有效集，它可为空树或非空树；
• 树是一种递归的结构。
• 对于非空树：1. 有且仅有一个称为根的节点。2. 除根节点以外其余节点可分为m个互不相交的有限集，且这些有限集本身也是一棵树，称为根的子树。
• 分等级的分类方案都可用树表示。

基本术语

二叉树

介绍

• 由n个节点所构成的集合，它或为空树，或为非空树。
• 对于非空树： 1. 有且仅有一个根节点。2. 除根节点外的其余节点分为两个互不相交的子集T1（T的左子树）、T2（T的右子树），且T1、T2本身也是二叉树。
• 与树的区别： 1. 每个节点至多有两个子树（不存在度大于2的节点）。2. 子树有左右之分，次序不能颠倒。

性质

• 在二叉树的第i层上至多有 2 ^ (i - 1) 个节点，i >= 1。
• 深度为k的二叉树至多有 2 ^ k - 1 个节点，k >= 1。
• 对任何一颗二叉树T，如果其终端节点数为n0，度为2的节点数为n2，则 n0 = n2 + 1。
• 具有n个节点的完全二叉树的深度为（不大于log 2 n的最大整数）+ 1。
• 如果对一颗有n个节点的完全二叉树的节点按层序编号（由第一层到最后一层，从左到右），则对于任意一个节点i（1 <= i <= n），有以下结论： 1. 如果 i = 1，则节点i是根节点，无双亲**；如果 i > 1，则其双亲是节点（不大于i/2的最大整数）**。2. 如果2i > n，则节点 i 无左孩子（节点i为叶节点）；否则节点i的左孩子为 2i。3. 如果2i + 1 > n，则节点 i 无右孩子；否则节点i的右孩子为 2i + 1。

特殊形态的二叉树

• 满二叉树：1. 深度为k且含有2 ^ k - 1 个节点的二叉树。2. 每一层上的节点数都是最大节点数，即每一层i的节点数都具有最大值 2 ^ (i - 1) 。
• 完全二叉树：1. 深度为k、有n个节点的二叉树，当且仅当其每一个节点都与深度为k的满二叉树中编号1~n的节点位置一一对应。2. 叶子节点只可能在层次最大的两层出现。3. 对任一节点，若其右分支下的子孙的最大层次为l，则左分支下的子孙最大层次必为l或l+1。

存储结构

• 顺序存储（浪费空间，不常用）#defineMAXTSIZE100typedef TElemType SqBiTree[MAXTSIZE];SqBiTree bt;//创造了一个二叉树对象，数据在数组的排列要严格按照由第一层到最后一层，从左到右的规则来写入/* 若遇到不存在这个节点，则用‘0’代替 如上图（c）应该写入为 1 2 3 4 5 0 0 0 0 6 7 第一个0和第二个0为节点3不存在的节点，但是由于规则，必须把它表示出来 第三个0和第四个0也是这样 因为到6、7后面就没了，所以也就不用再加0了*/
• 链式存储（常用）含有n个节点的二叉链表中有 n+1 个空链域- 左空链域的条件：处于序列最左端，且原来左指针就是空的。- 右空链域的条件：处于序列最右端，且原来右指针就是空的。typedefstructBiTNode{ TElemType data;//节点数据域structBiTNode*lchild,*rchild;//左右孩子指针}BiTNode,*BiTree;

遍历

算法

• 递归

//中序遍历二叉树的递归算法，改变语句顺序即可实现先序和后序voidInOrderTraverse(BiTree T){if(T)//若二叉树非空{InOrderTraverse(T -> lchild);//访问遍历左子树
        cout << T->data;//访问根InOrderTraverse(T -> rchild);//访问遍历右子树}}

• 非递归

/*
    中序遍历二叉树的非递归算法
    1. 初始化一个空栈S，指针p指向根节点
    2. 申请一个节点空间q，用来存放栈顶弹出的元素
    3. 当p非空或者栈S非空时，循环以下操作：
        如果p非空，则p进栈，p指向改节点的左孩子
        如果p为空，则弹出栈顶元素并访问根节点，将p指向该节点的右孩子
*/voidInOrderTraverse(BiTree T){InitStack(S);
    p = T;
    q = new BiTNode;while(p ||!StackEmpty(S)){if(p)//如果一直有就一直遍历左子树，把节点压到栈内，直到最后{Push(S, p);
            p = p -> lchild;}else//如果到底了就输出，然后遍历右子树{Pop(S, q);
            cout << q -> data;
            p = q -> rchild;}}}

注：根据一个先序序列和中序序列可以唯一确定一个二叉树，根据一个后序序列和中序序列可以唯一确定一个二叉树，方法看B站

层次遍历

/*
层次遍历：从上到下，从左到右遍历二叉树
    算法：
    1. 创建一个空队列，先保存根节点
    2. 进入循环，令指针p（指示当前的节点）对于队列第一个，将第一个出队
    3. 输出数据
    4. 如果有左右节点，保存到队列，便于后续遍历
    5. 队列不为空时重复234
*/voidLevelTraverse(BiTree T){
    queue<BiTree>tq;
    tq.push(T);//从第一个根节点开始，从上到下while(!tq.empty()){
        BiTree q = tq.front();
        tq.pop();
        cout << q->data;//访问该节点，并且把它的孩子保存进队列，顺序也刚刚好是从左到右if(q->lchild !=NULL) tq.push(q->lchild);if(q->rchild !=NULL) tq.push(q->rchild);}}

应用

创建二叉树的存储结构

/*
    为简化问题，设节点元素为字符。假设按先序遍历的顺序建立二叉链表，T为指向二叉树根节点的指针，对于一个特定的字符序列，依次读入字符，从根节点开始，递归创建二叉树。
    算法步骤：
    1. 查找字符序列，读入字符ch
    2. 如果ch是一个‘#’（相当于前面顺序存储结构的‘0’，代表次节点是空的），则代表二叉树为空；否则执行以下操作：
        。申请一个节点空间T
        。将ch赋给T->data
        。递归创建T的左子树
        。递归创建T的右子树
*/voidCreateBiTree(BiTree &T){
    cin >> ch;if(ch =='#') T =NULL;//递归结束，建空树else{
        T = new BiTNode;//生成根节点
        T -> data = ch;//写入数据CreateBiTree(T -> lchild);//递归创建左子树CreateBiTree(T -> rchild);//递归创建右子树}}

复制二叉树

/*
    按先序遍历去复制。
    算法步骤：
    二叉树若为空，递归结束；否则执行以下操作：
        。申请一个新节点空间，复制根节点
        。递归复制T的左子树
        。递归复制T的右子树
*/voidCopy(BiTree T, BiTree &NewT){if(T =NULL){
        NewT =NULL;//空树，递归结束return;}else{
        NewT = new BiTNode;//创建新节点
        NewT -> data = T -> data;//复制根节点Copy(T -> lchild, NewT -> lchild);//递归复制左节点Copy(T -> rchild, NewT -> rchild);//递归复制右节点}}

计算二叉树的深度

/*
    按先序遍历去计算。
    算法步骤：
    二叉树若为空，递归结束；否则执行以下操作：
        。递归计算左子树的深度m
        。递归计算右子树的深度n
        。如果m > n，二叉树的深度为m + 1，否则为n + 1（从第二层开始，所以最后要加上根节点）
*/intDepth(BiTree T){if(T ==NULL)return0;//如果树是空的，直接返回0else{
        m =Depth(T->lchild);//递归计算左子树深度m
        n =Depth(T->rchild);//递归计算右子树nif(m > n)return(m +1);elsereturn n +1;}}

统计二叉树中节点的个数

/*
    按先序遍历去计算。
    算法步骤：
    二叉树若为空，递归结束；否则节点个数等于 左子树节点个数 + 右子树节点个数 + 1
*/intNodeCount(BiTree T){if(T =NULL)return0;elseNodeCount(T->lchild)+NodeCount(T->rchild)+1;}

线索二叉树

介绍

上面的遍历实际上就是把非线性结构变成线性结构，使之能够找到前驱和后继，但是不能找到任何序列的前驱和后继。故而引进线索二叉树来保存这些东西。

规定如下：

-若节点有左子树，则其lchild域指示其左孩子，否则令lchild域指示其前驱。

-若节点有右子树，则其rchild域指示其右孩子，否则令rchild域指示其前驱。

为了避免混淆，直接在节点添加两个标志域，如下图：

二叉树的二叉线索存储表示

以这种节点结构构成的二叉链表作为二叉树的存储结构，叫做线索链表。

其中指向前驱和后继的指针叫做线索。

加上线索的二叉树叫做线索二叉树。

对二叉树以某种次序遍历使其变为线索二叉树的过程叫做线索化。

typedefstructBiThrNode{
    TElemType data;structBiThrNode*lchild,*rchild;int LTag, RTga;}BiThNode,*BiThrTree;

构造

已经有一个二叉树了，只不过将他线索化，构造出线索二叉树，需要在遍历中依次更改节点的空指针域。

以节点p为根的子树中序线索化（图a）

/*
    按中序遍历线索化，定义一个pre始终指向刚刚访问过的节点，p始终指向当前访问节点。
    算法步骤：
    。如果p非空，左子树递归线索化
    。如果p的左孩子为空，则给p加上左线索，将其LTag置为1，让p的左孩子指针指向pre（前驱）；否则把p的LTag置0
    。如果p的右孩子为空，则给p加上右线索，将其RTag置为1，让p的右孩子指针指向pre（后继）；否则把p的RTag置0
    。将pre指向刚刚访问过的节点p，即 pre = p
    。右子树递归线索化
*/

BiThrTree pre =NULL;//全局变量，初始化为空，方便其右孩子从最左节点进入voidInThreading(BiThrTree p){if(p)//树p不为空{InThreading(p->lchild);//因为中序遍历为左根右，故而当前节点进来应该先处理左边，故将左边线索化if(!p->lchild)//如果当前节点左孩子为空{
            p->LTag =1;
            p->lchild = pre;//当前节点的左孩子指针域指示前驱，线性化时的前一个点}else p->LTag =0;//当前点的左孩子不为空，则当前点的左孩子标志则置0if(!pre->rchild)//前驱的右孩子为空，设置前驱节点的后继，线性化的后一个点{
            pre->RTag =1;
            pre->rchild  = p;//前驱的右孩子为空，则接当前节点的地址}else pre->RTag =0;//前驱的右孩子不为空，则前驱的右孩子标志则置0
        pre = p;//继续遍历InThreading(p->rchild);//往右遍历}}

带头节点的二叉树中序线索化（图b）

为了方便操作，添加一个头节点，让第一种图中的最左节点左孩子指向头节点，最右节点的右孩子指向头节点的右孩子，头节点左孩子指向根节点，右孩子指向最右节点的右孩子（最后一个节点），以下的代码就是在上面加上这些定义即可。

BiThrTree pre =NULL;//全局变量，初始化为空，方便其右孩子从最左节点进入voidInOrderThreading(BiThrTree &Thrt, BiThrTree T){//Thrt指向头节点//构造一个头节点
    Thrt = new BiThrNode;
    Thrt->LTag =0;//因为左孩子要指向根节点，故标志初始化为0
    Thrt->RTag =1;//右孩子要指向最右节点
    Thrt->rchild = Thrt;//初始化时指向它自己if(!T) Thrt->lchild = Thrt;else{//头节点的左孩子指向根节点
        Thrt->lchild = T;
        pre = Thrt;//将全局变量初始化为头节点，在下面的函数内递归时就会发生最左节点的左孩子指向头节点InThreading(T);//返回的pre为最右节点
  
        pre->rchild = Thrt;//令最右节点指向头节点
        pre->RTag =1;//最右没有内容，故置1
        
        Thrt->Rchild = pre;//令头节点右孩子指向最右节点}}

遍历

中序

/*
    按中序遍历线索化
    算法步骤：
    1. 指针p指向根节点
    2. p为非空或遍历未结束，循环执行以下操作：
        。沿左孩子往下，到达最左下节点，它是中序的第一个节点
        。访问该节点进行输出
        。沿右线索反复查找当前节点的后继节点并访问后继节点，直到右线索为0或者遍历结束
        。转向p的右子树
*/voidInOrderTraverse_Thr(BiThrTree T){
    p = T->lchild;//头节点的左孩子为根节点while(p != T)//不为空树{while(p->LTag ==0) p = p->lchild;//遍历到最左边的第一个节点，下面输出
        cout << p->data;while(p->RTag ==1&& p->rchild != T)//若标志为0则指已经返回到了上一个中间节点 / 遍历结束（最后一个节点的右孩子指向头节点）{
            p = p->rchild;//刚刚进来还是上一个节点，要先换到下一个
            cout << p->data;//输出}
        p = p->rchild;//继续遍历中间节点的右子树}}

树和森林

存储结构

• 双亲表示法：节点内有两个域，一个是数据域（data），一个是指示其父母亲（parent）
• 孩子表示法
• 孩子兄弟表示法//节点结构有第一个孩子节点，数据，下一个孩子节点typedefstructCSNode{ ElemType data;structCSNode*firstchild,*nextsibling;}CSNode,*CSTree;

注：剩下的可以看课本

哈夫曼树

介绍

又称最优树，是一类带权路径长度最短的树，在实际生活有着广泛的应用。

构造

• 构造过程1. 给定n个权值{w1,w2,…,wn}，构造n棵只有根节点的二叉树，这n棵二叉树构成森林F。2. 在森林F中选取两棵根节点的权值最小的树（构造的新树也算，若权值最小是新树之外的两颗，那就重新再组有课树）作为左右子树构造新的二叉树，且其根节点权值为左右孩子权值和。3. 在森林F中删去这两棵树，同时加入新的树。4. 重复2、3直到F只含一棵树为止。
• 构造算法#include<iostream>using namespace std;/* 树节点结构：权值weight+父母parent+左孩子lchild+右孩子rchild 存储在大小为2n-1(n个节点构成的哈夫曼树有2n-1个节点)的数组内，但是为了方便，0不使用，从1开始，所以数组大小要定义为2n，通过下标去调用*/typedefstruct{int weight;//权值int parent, lchild, rchild;//对应下标}HTNode,* HuffmanTree;//HT数组中存放的哈夫曼树，end表示HT数组中存放结点的最终位置，s1和s2传递的是HT数组中权重值最小的两个结点在数组中的位置voidSelect(HuffmanTree HT,int end,int& s1,int& s2){int min1, min2;//遍历数组初始下标为 1int i =1;//找到还没构建树的结点while(HT[i].parent !=0&& i <= end){ i++;} min1 = HT[i].weight; s1 = i; i++;while(HT[i].parent !=0&& i <= end){ i++;}//对找到的两个结点比较大小，min2为大的，min1为小的if(HT[i].weight < min1){ min2 = min1; s2 = s1; min1 = HT[i].weight; s1 = i;}else{ min2 = HT[i].weight; s2 = i;}//两个结点和后续的所有未构建成树的结点做比较for(int j = i +1; j <= end; j++){//如果有父结点，直接跳过，进行下一个if(HT[j].parent !=0){continue;}//如果比最小的还小，将min2=min1，min1赋值新的结点的下标if(HT[j].weight < min1){ min2 = min1; min1 = HT[j].weight; s2 = s1; s1 = j;}//如果介于两者之间，min2赋值为新的结点的位置下标elseif(HT[j].weight >= min1 && HT[j].weight < min2){ min2 = HT[j].weight; s2 = j;}}}/* 算法步骤 1.初始化 ·申请大小2n的动态数组，从1开始循环到2n-1，把所有节点的父母、孩子都设为0 ·循环n次（1-n），输入n个叶子节点的权值 2.创建树 ·循环n-1次（n+1~2n）的选择、删除与合并来创建哈夫曼树 ·选择：从当前森林选出双亲为0且权值最小的节点的下标s1和s2 ·删除：把s1和s2的父母改为非0，即当前的下标 ·合并：把s1和s2的权值相加，成为当前节点的权值，同时记录左右孩子下标，即s1和s2*/voidCreateHuffmanTree(HuffmanTree& HT,int n){if(n <=1)return;//检测输入是否正确/*--------------------------------------------初始化--------------------------------------------------------*/int m =2* n -1;//n个叶子节点构建的树有2n-1个节点 HT = new HTNode[m +1];//从1开始，故加一for(int i =1; i <= m; i++){//全部置0 HT[i].parent =0; HT[i].lchild =0; HT[i].rchild =0;}for(int i =1; i < n; i++){//输入权值 cin >> HT[i].weight;}/*-------------------------------------------构造哈夫曼树----------------------------------------------------*/for(int i = n +1; i <= m; i++){int s1, s2;Select(HT, i -1, s1, s2);//选择函数 HT[i].lchild = s1;//当前节点左孩子设置为s1 HT[i].rchild = s2;//当前节点右孩子设置为s2 HT[s1].parent = HT[s2].parent = i;//s1、s2父母设置为当前节点下标 HT[i].weight = HT[s1].weight + HT[s2].weight;//当前节点权值为s1和s2总和}}

编码

进行数据压缩时，为了使压缩后的数据文件尽可能短，可采用不定长编码。为了正确编码，用哈夫曼树来实现。

关于编码，有两个概念：

1. 前缀编码：在一个编码方案里，任一个编码都不是其他任何编码的前缀（最左子串），则为前缀编码。（不懂百度一下）
2. 哈夫曼编码：约定左支为0，右支为1，则根节点到每个叶子节点路径上的0、1序列就是对应编码。以下是哈夫曼编码的性质 - 哈夫曼编码是前缀编码- 哈夫曼编码是最优前缀编码

/*
    哈夫曼编码表存储结构
    因为每个编码不等长，所以定义一个二维字符数组来存储
    为了方便，数组下标从1开始使用，故为n+1行
    因为事先不能确定编码长度，为了不浪费内存空间，定义一个一维字符数组（长度为n，编码一定不会大于n）来存储后再移入编码表里。值得注意的是，因为哈夫曼编码是从根到叶，而记入cd时是从叶到根，所以需要我们记入cd时要反过来记入
*/typedefchar**HuffmanCode;//动态分配数组存储哈夫曼编码表/*
    算法步骤
    1.分配存储n个字符编码的编码表空间HC，长度为n+1
    2.分配临时编码存储数组cd，长度为n，cd[n-1]置为‘\0’
    3.逐个字符求编码，循环n次，执行以下操作
        ·设置start用于记录编码在cd中存放的位置，初始化指向最后
        ·设置变量c用于记录从叶子向上回溯到根节点所经过的节点下标，c初始化为等待编码字符的下标i
        ·设置变量f用于记录i双亲节点的下标
    4.从叶子向上回溯到根节点，当没有回溯到根节点，循环执行以下操作
        ·回溯一次start向前指一个位置，即--start
        ·若节点c是f的左孩子，生成0；否则生成1，保存在cd中
        ·继续回溯，改变c和f的值
    5.分配HC空间，记入编码
*/voidCreateHuffmanCode(HuffmanTree HT, HuffmanCode& HC,int n){
    HC = new char*[n +1];char* cd = new char[n];
    cd[n -1]='\0';for(int i =1; i <= n; i++){//前期准备int start = n -1;int c = i;int f = HT[i].parent;//开始编码while(f !=0)//没有到根节点，哈夫曼树只有根节点是无双亲的{--start;if(HT[f].lchild = c)cd[start]='0';else cd[start]='1';
            c = f;
            f = HT[f].parent;}//记入HC
        HC[i]= new char[n - start];strcpy(HC[i],&cd[start]);//记得include<string>}
    delete cd;//释放临时空间}