树与图c++

1.树

前言

本文主要介绍的数据结构之树型结构的相关知识，树型数据结构是面试官面试的时候非常喜欢考的一种数据结构，树形结构的遍历也是大厂笔试非常喜欢设置的考点，这些内容都会在本篇文章中进行详细的介绍，并且还会介绍一些常用的算法。

一、树的基本概念

层次结构的数据在现实世界中大量存在。例如，一个国家有若干省，一个省有若干市县，一个市县有若干区乡。又如，一本书包含若干章，一章包含若干节，一节包含若干段。例如，下图是数组的层次关系，这种描述树形数据的形式称为倒置的树形表示法。
在这里插入图片描述

线性数据结构一般不适合用来表示层次数据。为了组织层次数据，需要对树形数据的结构进行研究。

1.1树的定义

在上图1中，我们采用倒置树来描述树状结构。一棵倒置树的顶端是根，根有几个分枝，称为子树，每棵子树再分成几个小分枝，小分枝再分成更小的分枝，每个分枝也都是树，一个结点也是树。由此，我们可以给树下一个递归定义。

树（Tree）是包括n个结点的有限非空集合T，其中，一个特定的结点r称为根（Root），其余结点T-{r}划分成m个互不相交的子集T1，T2，Tm其中，每个子集都是树，称为树根r的子树。

根据树的定义，一个结点的树是仅有根结点的树，这时m=0，这棵树没有子树。

1.2基本术语

图1可以抽象成图2，它形象地反映了树的逻辑结构。下面，参照图2，给出树结构讨论中常用的术语。

树中元素称为结点（Node），如A、B等。

如果某结点到另一结点之间存在着连线，则称此连线为一条边（Edge），如<A,B>、<B,E>等。

如果从某个结点沿着树中的边可到达另一个结点，则称这两个结点间存在一条路径（Path），如结点A到结点J，存在路径{<A,C>，<C,J>}。

如果一个结点有子树，则称该结点为子树的双亲（Parent），子树的根称为该结点的孩子（Child），如结点A是结点B、C、D的双亲，而结点B、C、D是结点A的孩子。具有相同双亲的结点称为兄弟（Sibling），如结点B、C、D是兄弟。

结点拥有的子树数目称为结点的度（Degree），如结点A的度为3，结点D的度为0，结点J的度为0。

度为零的结点称为叶子(Leaf)。

规定根结点的层次为1，树中结点的最大层次称为该树的高度(Hight)，如图2所表示的树的高度为3。

如果树中结点的各子树是从左至右有次序的，则称该树为有序树，否则称为无序树。

二、二叉树

树结构和自然界的树一样，具有各种各样的形态，这样就使我们对树结构的研究比较困难。为此，我们首先研究最为常见的二叉树，以及二叉树的性质、存储结构和运算，然后给出二叉树和一般树之间的转换。

2.1二叉树的定义
二叉树（Binary Tree）是由有限个结点组成的集合，它或者为空集合，或者仅含一个根结点，或者由一个根结点和两棵互不相交的左、右子树组成。

上述定义表明，二叉树有如图3所示的五种基本形态。
在这里插入图片描述

必须指出，树定义与二叉树定义稍有区别。首先，树不能是空树，却可以有空二叉树。其次，一般树的子树的不分次序，而二叉树的子树却分左、右子树，即使在仅有一棵子树的情况下也要指明是左子树还是右子树。最后，一般树中结点的度(子树数目)可以大于2，但二叉树中结点的度均不超过2。

2.2二叉树的性质
若二叉树高为h，树的结点总数为2^h-1，称此二叉树为满二叉树。

h=3，那么结点总数7(包含根节点)

【性质1】高度为h的二叉树的结点总数n<=2^h-1。

这个性质很容易理解：

证明：对于高度为h的满二叉树，其结点总数为

它是高度为h的二叉树结点总数的最大值，故。

对于高度为h的二叉树，如果第1~h-1层构成满二叉树，而第h层的叶子结点严格按从左至右依次排列，称此二叉树为完全二叉树（如图5(a)所示）。

图5 完全二叉树与非完全二叉树

在图5(b)中，双亲结点C仅有右孩子G无左孩子，故它不是完全二叉树。

【性质2】对于含n(n>=1)个结点的完全二叉树(区分满二叉树)，其高度 h = ⌈ l o g 2 ( n + 1 ) ⌉ h=\lceil log2(n+1) \rceil h=⌈log2(n+1)⌉ 。

eg：上述图a，n=6，那么

h = [ l o g 2 ( 6 + 1 ) ] = l o g 2 ( 8 ) = 3 h=[log2(6+1)]=log2(8)=3 h=[log2(6+1)]=log2(8)=3

【性质3】对于一棵非空二叉树，如果度为0的结点数为，度为2的结点数为，则

=+1。 （即零度结点数总比2度结点数大1）

证 设二叉树的结点数为n，度为1的结点数为n1，边数为e，则

e = n − 1 e=n-1 e=n−1

e = 2 × n 2 + n 1 e=2×n2+n1 e=2×n2+n1

n = n 0 + n 1 + n 2 n=n0+n1+n2 n=n0+n1+n2

边数等于结点数n-1 ，等于2倍的度为2的结点数+度为1的结点数。

画个树的逻辑结构图就很容易看出来。

于是n0=n2+1。

【性质4】对于含个结点的完全二叉树(区分满二叉树)，按从上到下、从左到右的顺序，从0到n-1编号（如图6所示）。对于树中编号为 i （ 0 = < i < = n − 1 ） i（0=<i<=n-1） i（0=<i<=n−1）的结点，有

（1）如果 i = 0 i=0 i=0，则该结点为二叉树的根；

（2）如果 2 i + 1 < n 2_i+1<n 2i​+1<n，则其左孩子为 2 i + 1 2_i+1 2i​+1，否则不存在左孩子；

（3）结点的双亲为[(i-1)/2]向下取整。(求双亲注意双亲只有一个)

图6 带序号的完全二叉树

2.3二叉树的ADT
ADT BinTree

数据：

0个或有限个结点组成的集合。

运算：

Create()

创建一棵空二叉树或二叉树。

IsEmpty()

若二叉树为空，则返回1，否则返回0。

PreOrder()

前序遍历二叉树。

InOrder()

中序遍历二叉树。

PostOrder()

后序遍历二叉树。

Display():

输出二叉树。

三、二叉树的存储表示

3.1二叉树的数组表示
用一维数组来存储二叉树，首先将二叉树想象成一棵完全二叉树，对于没有左孩子或右孩子的结点，用特殊字符（或数字）替代，再依从上至下、从左至右的次序，依次将结点值存放到一维数组之中。

【例1】：将图7(a)所示的二叉树，用一维字符数组表示。
在这里插入图片描述

解：

首先将图7(a)所示的二叉树，想象成一棵完全二叉树（如图7(b)所示），再用表8-1所示的一维字符型数组存储。

这种表示法的实现程序如下：示法的实现程序如下：

#include <bits/stdc++.h>
using namespace std;
const int MaxSize 64//为了树的显示效果,结点数不超过63,即二叉树高不超过6
//创建二叉树
void Create(char Node[], int& n)
{
    cout << "按完全二叉树输入结点字符,空字符用替代" << endl;
    cin >> Node;
    //计算字符数组含字符个数
    n = 0;
    while (Node[n] != '\0')//当Node[n]不等于结束符时
        n++;
}
//输出二叉树
void Display(char Node[], int n)
{
    int hight, layer, num; //hight树高,layer树层,num结点编号
    hight = ceil(log(n + 1) / log(2));//确定完全二叉树高度
    //求下限接近整数ceil//自然对数 log//求上限接近整数 floor
    cout << hight << endl;
    num = 0;//从结点Node[0]开始输出
    for (layer = 1; layer <= hight; layer++)//输出1层—hight层
    {	//每层前面空格的输出控制
        for (int i = 1; i <= pow(2, hight - layer)-1; i++)
            cout << " ";
        //每层结点的输出控制
        for (int j = 1; j <= pow(2, layer - 1); j++, num++)
        {
            if (Node[num] != '' && Node[num] != '\0')
                cout << Node[num];//遇到结点,输出结点
            else if (Node[num] == '')
                cout << " ";//遇到号,输出空格
            else
                break;//遇到结束符,跳出输出
            //每层结点间空格的输出控制
            for (int k = 1; k <= pow(2, hight - layer + 1) - 1; k++)
                cout << " ";
        }
        cout << endl;//输完一层,换行
    }
}
//主函数
int main()
{
    int n;//完全二叉树所含结点数
    char Node[MaxSize];//定义字符型的结点数组
    Create(Node, n);//创建二叉树结点的一维数组
    cout << "二叉树为" << endl;
    Display(Node, n);//输出二叉树
    return 0;
}

程序运行的结果如图8所示：

创建这棵5结点二叉树，用了6颗星号替代缺失的左、右孩子，这显然是这种表示法的一个缺点。

但当二叉树为完全二叉树时，该表示法具有建树简便，输出直观的优点。

3.2二叉树的链表表示
用一维数组表示的二叉树，不便实现二叉树的一些规定运算。因此，二叉树一般采用链表来创建。

链式二叉树结点的逻辑结构如图9所示，其中，data用来存储结点值，*lChild、*rChild分别用来存储左、右孩子的地址。

图9 树节点的逻辑结构
【例2】创建图7(a)所示的链式二叉树。

用链表表示图7(a)，其逻辑结构如图10所示，其中Λ代表NULL。

具体的创建过程如下：

（1）首先创建第4层结点，并用结点指针Kp指向其根结点，如图11所示。

图11
（2）再创建第3层结点，并用结点指针Ep指向其根结点，如图12所示。

图12
（3）再创建第2层结点，并用结点指针Bp、Cp分别指向其根结点，如图13所示。

图13
（4）最后创建第1层结点，并用结点指针Ap指向其根结点，如图14所示。

图14
如果用程序来描述上述过程，其程序如下：

#include<iostream>
using namespace std;
//二叉树结点定义
struct Node
{	
    char data;//数据域
    Node *lChild,*rChild;//指针域
};
//二叉树定义
struct BinTree
{	
    Node *root;
};
//创建二叉树
void Create(BinTree &T,char x,Node *left,Node *right)
{	
    Node *NewNode;//新结点
    NewNode=new Node;//为新结点申请内存
    NewNode->data=x;//为新结点数据域赋值
    NewNode->lChild=left;//为新结点左指针域赋值
    NewNode->rChild=right;//为新结点右指针域赋值
    T.root=NewNode;//让新结点成为该子树根结点
}
//主函数
int main()
{	
    BinTree K,E,B,C,A;
    Create(K,'K',NULL,NULL);//创建结点K的子树
    Create(E,'E',NULL,K.root);//创建结点E的子树
    Create(B,'B',NULL,E.root);//创建结点B的子树
    Create(C,'C',NULL,NULL);//创建结点C的子树
    Create(A,'A',B.root,C.root);//创建结点A的子树
    return 0;
}

上述链式二叉树的创建过程是，先创建最底层的叶子结点，然后向上逐层创建子树，直至最顶层的根结点。该方法的优点是直观易懂，缺点是无法给出通用程序。一般链式二叉树的创建方法与通用程序如下。

用广义表构建二叉树。

  1. 二叉树的广义表表示法

尽管构建二叉树的方法并不复杂，但对于结点多、结构复杂的二叉树，却不易用程序来实现。因此，有必要寻找更具一般性的二叉树的构建方法。

图1所示的二叉树，可以用以下方式重新表示它。

用A(B)表示A有左孩子B，无右孩子；

用B(C,D)表示B有左孩子C，右孩子D；

用C(,E)表示C无左孩子，但有右孩子E；

用D(F,G)表示D有左孩子F，右孩子G。

将它们复合起来，有A(B(C(,E),D(F,G)))。这是一个字符数组，它是上述二叉树的另一种表示法，称这种二叉树的表示法为广义表法。

用广义表来表示二叉树，其具体规定如下：

树的根结点放在最前面。

每个结点的左子树和右子树用逗号隔开。若仅有左子树没有右子树，逗号可省略；若仅有右子树没有左子树，逗号不能省略。

约定，广义表用字符型数组 GenList[] 来存储。

  1. 广义表构建二叉树的算法

设结点值均用字母来替代，先建一棵空二叉树T，借助一个简易结点顺序栈 stack ，广义表A(B(C(,E),D(F,G)))创建二叉树的具体过程如下：

（1）读A，创建新结点A，T为空，让T.root=A结点。

（2）读（，让新结点A入栈，置k=1，栈stack状态为：

A

（3）读B，创建新结点B，因k=1，让栈顶结点A的左指针指向B，即B←A。

（4）读（，让新结点B入栈，置k=1，栈stack状态为：

A

B

（5）读C，创建新结点C，因k=1，让栈顶结点B的左指针指向C，即C←B。

（6）读（，让新结点C入栈，置k=1，栈stack状态为：A B C

（7）读，号，置k=2。

（8）读E，创建新结点E，因k=2，让栈顶结点C的右指针指向E，即C→E。

（9）读），栈顶结点C出栈，栈stack状态为：A B

（10）读，号，置k=2。

（11）读D，创建新结点D，因k=2，让栈顶结点B的右指针指向D，即B→D。

（12）读（，让新结点D入栈，置k=1，栈stack状态为：A B D

（13）读F，创建新结点F，因k=1，让栈顶结点D的左指针指向F，即F←D。

（14）读，号，置k=2。

（15）读G，创建新结点G，因k=2，让栈顶结点D的右指针指向G，即D→G。

（16）读），栈顶结点D出栈，栈stack状态为：A B

（17）读），栈顶结点B出栈，栈stack状态为：A

（18）读），栈顶结点A出栈，栈stack状态为：

至此，二叉树创建完毕。

由T.root=A，B←A，C←B，C→E，可构建如下图2所示的二叉树。

图2 二叉树的构建过程1
由B→D，F←D，D→G，可构建如图3所示的二叉树。

图3 二叉树的构建过程2
3. 广义表构建二叉树算法的程序实现

#include<iostream>
using namespace std;
const int MaxSize 100//顺序栈的最大容量
//结点定义
struct Node
{	
    char data;//数据域
    Node *lChild,*rChild;//指针域
};
//二叉树定义
struct BinTree
{	
    Node *root;
};
//创建空二叉树
void Create(BinTree &T)
{	
    T.root=NULL;
}
//树判空
int IsEmpty(BinTree T)
{	
    if(T.root==NULL) return 1;
    else return 0;
}
//广义表创建二叉树
void Create(char GenList[],BinTree &T)
{	
    Node *stack[MaxSize],*NewNode,*p;//简易结点顺序栈,新结点,探测指针
    int top=-1;//置栈空
    int k,i=0;//k=1链接左子树,k=2链接右子树,i广义表字符下标
    char ch;
    do
    {	
        ch=GenList[i];//读取广义表第i个字符
        switch(ch)
        {	
            case '('://读到左括号
            stack[++top]=NewNode;//新结点入栈
            k=1;break;
            case ')'://读到右括号
            top--;break;//栈顶结点出栈
            case ','://读到逗号
            k=2;break;
            default://读到字符
            NewNode=new Node;//新结点申请内存
            NewNode->data=ch;//新结点数据域赋值
            NewNode->lChild=NULL;//新结点左指针域赋值
            NewNode->rChild=NULL;//新结点右指针域赋值
            if(IsEmpty(T))//如果树为空
                T.root=NewNode;//新结点作为根结点
                if(k==1)
                {	
                    p=stack[top];//获取栈顶结点
                    p->lChild=NewNode;//让栈顶结点左孩子指向新结点
                }
                else if(k==2)
                {
                    p=stack[top];//获取栈顶结点
                    p->rChild=NewNode;//让栈顶结点左孩子指向新结点
                }
         }
         i++;//i增1
     }
     while(GenList[i]!='\0');//逐一读完整个广义表
}
//非递归前序遍历算法
void PreOrder(Node *p)
{	
    Node *stack[MaxSize];// 简易结点顺序栈
    int top=-1;//置栈空
    while(p||top!=-1)//当p结点所指非空或栈非空时
    {	
        if(p)//如果p所指结点非空
        {	
            cout<<p->data;//输出p的值
            stack[++top]=p;//p所指结点入栈
            p=p->lChild;//p向左下移
        }
        else//如果p结点所指结点为空
        {	
            p=stack[top--];//p指向栈顶结点,栈顶结点出栈
            p=p->rChild;//p向右下移
        }
    }
}
//非递归中序遍历算法
void InOrder(Node *p)
{	
    Node *stack[MaxSize];//简易结点顺序栈
    int top=-1;//置栈空
    while(p||top!=-1)//当p结点所指非空或栈非空时
    {	
        if(p)//如果p所指结点非空
        {	
            stack[++top]=p;//p所指结点入栈
            p=p->lChild;//p向左下移
        }
        else//如果p所指结点为空
        {	
            p=stack[top--];//p指向栈顶结点,栈顶结点出栈
            cout<<p->data;//输出p的值
            p=p->rChild;//p向右下移
        }
    }
}
//主函数
int main()
{	
    char GenList[]="A(B(C(,E),D(F,G)))";//定义广义表
    BinTree T;//定义二叉树
    Create(T);//创建空二叉树
    Create(GenList,T); //创建二叉树
    cout<<"前序遍历为 "; PreOrder(T.root); cout<<endl;
    cout<<"中序遍历为 "; InOrder(T.root); cout<<endl;
    return 0;
}

程序运行的结果如图4所示。

图4
四、二叉树的遍历
欲在屏幕上形象地输出链式二叉树是一件困难的事，一般采用输出它的三个线性序列VLR、LVR和LRV的方式，来解决这一问题。

VLR称为前序（PreOrder）遍历序列，它是按先树根，再左子树，后右子树的次序，输出二叉树的结点值。

LVR称为中序（InOrder）遍历序列，它是按先左子树，再树根，后右子树的次序，输出二叉树的结点值。

LRV称为后序（PostOrder）遍历序列，它是按先左子树，再右子树，后树根的次序，输出二叉树的结点值。

所谓前序、中序和后序遍历，是相对于根结点位置而言的。例如，在中序遍历中，根结点在中间；而前序遍历是根结点在前面，后序遍历是根结点在后面。三种遍历方式一定是先左子树后右子树。

4.1前序遍历
前序遍历的次序为：树根—左子树—右子树，即从根结点开始处理，根结点处理完后往左子树走，直到无法前进再处理右子树。

图10 链式二叉树的逻辑结构
【例2】的前序遍历为ABEKC，前序遍历的递归算法如下：

void PreOrder(Node *p)
{	
    if(p!=NULL)
    {	
        cout<<p->data;//访问树根
        PreOrder(p->lChild);//遍历左子树
        PreOrder(p->rChild); //遍历右子树
    }
}

4.2中序遍历
中序遍历的次序为：左子树—树根—右子树，即沿树的左子树一直往下，直到无法前进时后退到双亲结点，而后再沿右子树一直往下。如果右子树也走完了就退回上层的左结点，重复左、中、右的顺序遍历。

【例2】的中序遍历为BEKAC，中序遍历的递归算法如下：

void InOrder(Node *p)
{	
    if(p!=NULL)
    {	
        InOrder(p->lChild); //遍历左子树
        cout<<p->data; //访问树根
        InOrder(p->rChild);//遍历右子树
    }
}

【例2】的后序遍历为KEBCA，后序遍历的递归算法如下：

void PostOrder(Node *p)
{	
  if(p!=NULL)
    {	
        PostOrder(p->lChild);//遍历左子树
        PostOrder(p->rChild); //遍历右子树
        cout<<p->data; //访问树根
    }
}

#include<iostream>
using namespace std;
//二叉树结点定义
struct Node
{
    char data;//数据域
    Node* lChild, * rChild;//指针域
};
//二叉树定义
struct BinTree
{
    Node* root;
};
//创建二叉树
void Create(BinTree& T, char x, Node* left, Node* right)
{
    Node* NewNode;//新结点
    NewNode = new Node;//新结点申请内存
    NewNode->data = x;//新结点数据域赋值
    NewNode->lChild = left;//新结点左指针域赋值
    NewNode->rChild = right;//新结点右指针域赋值
    T.root = NewNode;//让新结点成为该子树根结点
}
//前序遍历
void PreOrder(Node* p)
{
    if (p != NULL)
    {
        cout << p->data;//访问树根
        PreOrder(p->lChild);//遍历左子树
        PreOrder(p->rChild); //遍历右子树
    }
    if (p == NULL)
    {
        cout << "*";//输出空的节点，更清楚的理解PreOrder的调用过程
    }
}
//中序遍历
void InOrder(Node* p)
{
    if (p != NULL)
    {
        InOrder(p->lChild); //遍历左子树
        cout << p->data; //访问树根
        InOrder(p->rChild);//遍历右子树
    }
    if (p == NULL)
    {
        cout << "*";//输出空的节点，更清楚的理解PreOrder的调用过程
    }
}
//后序遍历
void PostOrder(Node* p)
{
    if (p != NULL)
    {
        PostOrder(p->lChild);//遍历左子树
        PostOrder(p->rChild); //遍历右子树
        cout << p->data; //访问树根
    }
    if (p == NULL)
    {
        cout << "*";//输出空的节点，更清楚的理解PreOrder的调用过程
    }
}
//主函数
int main()
{
    BinTree K, E, B, C, A;
    Create(K, 'K', NULL, NULL);//创建结点K的子树
    Create(E, 'E', NULL, K.root);//创建结点E的子树
    Create(B, 'B', NULL, E.root);//创建结点B的子树
    Create(C, 'C', NULL, NULL);//创建结点C的子树
    Create(A, 'A', B.root, C.root);//创建结点A的子树
    cout << "前序遍历为 "; PreOrder(A.root); cout << endl;
    cout << "中序遍历为 "; InOrder(A.root); cout << endl;
    cout << "后序遍历为 "; PostOrder(A.root); cout << endl;
    return 0;
}

程序运行的结果如图16所示：
在这里插入图片描述

【定理1】任意n(n>0)个不同结点的二叉树，都可由其前序遍历序列和中序遍历序列唯一确定。

【例4】画出前序遍历ABEKC，中序遍历BEKAC所确定的二叉树。

（1）由前序遍历ABEKC，A为根结点；由中序遍历BEKAC，BEK为左子树，C为右子树；其对应的二叉树如图17所示。
在这里插入图片描述

（2）对于左子树，由前序遍历BEK，B为根结点；由中序遍历BEK，EK为右子树，其对应的二叉树如图18所示。
在这里插入图片描述

（3）对于右子树，由前序遍历EK，E为根结点；由中序遍历EK，K为右子树，其对应的二叉树如图19所示。
在这里插入图片描述

五、常用二叉树
5.1排序二叉树
先给出排序二叉树的定义。

设二叉树的所有结点值互异，排序二叉树或者是一棵空树，或者是满足以下条件的树：

（1）若左子树不空，则左子树上所有结点的值均小于根结点的值；（左小于根）

（2）若右子树不空，则右子树上所有结点的值均大于根结点的值；（右大于根）

（3）左、右子树也分别是排序二叉树。(递归定义)

排序二叉树定义是由递归方式给出的，据此定义，可给出排序二叉树的创建方法：

首次输入的数据作为此二叉树的根，其后输入的数据与根进行比较，小于树根的放置到左子树，大于树根的放置到右子树。

【例5】依次输入数据32，25，16，35，27，创建一棵排序二叉树。

排序二叉树的创建过程如图20所示：

图20 排序二叉树的创建过程

创建排序二叉树的程序如下：

#include <bits/stdc++.h>
using namespace std;
//二叉树结点定义
struct Node
{	
	int data;//数据域
	Node *lChild,*rChild;//指针域
};
//二叉树定义
struct BinTree
{	
	Node *root;
};
//创建空二叉树
void Create(BinTree &T)
{	
	T.root=NULL;
}
	//判空
int IsEmpty(BinTree T)
{	
	if(T.root==NULL) return 1;
	else return 0;
}
//创建排序二叉树
void Create(BinTree &T,int x)
{	
	Node *NewNode,*p;
	NewNode=new Node; //新结点申请内存
	NewNode->data=x;//新结点数据域赋值
	NewNode->lChild=NULL;//新结点左指针域赋值
	NewNode->rChild=NULL;//新结点右指针域赋值
	int flag=0;//新结点入树标识,flag=0表示未入树
	if(IsEmpty(T))//如果二叉树为空
	{
		T.root=NewNode;
	}
	else//如果二叉树非空
	{	
		p=T.root;//探测指针指向根结点
		while(!flag)//当新结点未入树时//理解江老师说的兑奖劵问题
		{	
			if(x<p->data)//如果新结点的值小于双亲结点的值
			{ //进入左子树
				if(p->lChild==NULL)//如果左子树为空
				{	
					p->lChild=NewNode;//新结点成为左子树
					flag=1;//新结点入树
				}
				else//如果左子树非空
				{
					p=p->lChild;//探测指针向左下移
				}
			}
			else//如果新结点的值大于双亲结点的值
			{  //进入右子树
				if(p->rChild==NULL)//如果右子树为空
				{	
					p->rChild=NewNode;//新结点成为右子树
					flag=1;//新结点入树
				}
				else
				{
					p=p->rChild;//探测指针向右下移
				}
			}
		}
	}
}
//前序遍历
void PreOrder(Node *p)
{	
	if(p!=NULL)
	{	
		cout<<p->data<<" ";//访问树根
		PreOrder(p->lChild);//遍历左子树
		PreOrder(p->rChild);//遍历右子树
	}
}
//中序遍历
void InOrder(Node *p)
{	
	if(p!=NULL)
	{	
		InOrder(p->lChild);//遍历左子树
		cout<<p->data<<" ";//访问树根
		InOrder(p->rChild);//遍历右子树
	}
}
//主函数
int main()
{	
	BinTree T;//定义二叉树
	Create(T);//创建空二叉树
	char c;
	int x;
	printf("输入二叉树结点值(用空格隔开,回车结束)\n");
	while(scanf("%d%c",&x,&c))//while键盘输入的第一种用法
	{
		Create (T,x);//创建排序二叉树
		if(c=='\n') break;
	}
	cout<<"前序遍历为 "; PreOrder(T.root); cout<<endl;
	cout<<"中序遍历为 "; InOrder(T.root); cout<<endl;
	return 0;
}

程序运行的结果如图21所示：

图21

排序二叉树的优点是，建树方便，中序遍历为升序序列。

5.2哈夫曼树
先介绍几个概念 。

路径长度（Path Length）： 路径上的分支(边)数目。

树的路径长度（Tree Path Length）： 根结点到每个叶子结点的路径长度之和。

树的带权(叶子结点的权值)路径长度（Weighted Path Length）： 其中wi是第i个叶子结点的权值，li为从根结点到第i个叶子结点的路径长度，n为叶子结点的总数。

最优二叉树： WPL最小的二叉树，最优二叉树也称哈夫曼树（Huffman Tree）。

【例6】图27给出了三棵二叉树，分别计算它们的带权路径长度（即 W P L WPL WPL ）。
在这里插入图片描述

图27 二叉树的带权路径长度
解：

（a） W P L = 9 × 1 + 15 × 2 + 3 × 3 + 4 × 3 = 60 WPL=9×1+15×2+3×3+4×3=60 WPL=9×1+15×2+3×3+4×3=60

（b） W P L = 3 × 1 + 4 × 2 + 9 × 3 + 15 × 3 = 83 WPL=3×1+4×2+9×3+15×3=83 WPL=3×1+4×2+9×3+15×3=83

（c） W P L = 4 × 1 + 15 × 2 + 9 × 3 + 3 × 3 = 70 WPL=4×1+15×2+9×3+3×3=70 WPL=4×1+15×2+9×3+3×3=70

哈夫曼给出了一个创建最优二叉树的方法。下面，我们用一个实例来介绍这一方法。

【例7】设集合{12，3，10，5，2}为叶结点的权值，试创建哈夫曼树。

创建哈夫曼树的过程，可以由以下步骤和示意图来说明。

（1）将权值按升序排序，构建单结点的二叉树集T，T如图28所示。
在这里插入图片描述

图28
（2）从T中选取前两棵的二叉树，分别作为左、右子树，构造一棵新二叉树（注意，排序在前的作左子树），对T中权值再按升序排序（注意，如果出现权值相等的情况，则原树排前，新树排后），T如图29所示。
在这里插入图片描述

图29
（3）反复重复第（2）步的操作，T如图30 — 图32所示。
在这里插入图片描述

图30 创建过程3 图31 创建过程4 图32 创建过程5

必须指出，哈夫曼树的形状不唯一。但如果严格按上述规定来创建，哈夫曼树还是唯一

的，编程创建哈夫曼树将严格按上述规定进行。

性质1: 哈夫曼树不存在度为1的结点。

性质2: 设哈夫曼树的叶子结点数为 n 0 n_0 n0​，则哈夫曼树的结点数 n = 2 × n 0 − 1 n=2×n_0-1 n=2×n0​−1。

性质3: 哈夫曼树的带权路径长度等于所有度为2的结点值之和。

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/95461.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

线程安全-搞清synchronized的真面目

线程安全-搞清synchronized的真面目

多线程编程中&#xff0c;最难的地方&#xff0c;也是最重要的一个地方&#xff0c;还是一个最容易出错的地方&#xff0c;更是一个特别爱考的地方&#xff0c;就是线程安全问题。 万恶之源&#xff0c;罪魁祸首&#xff0c;多线程的抢占式执行,带来的随机性. 如果没有多线程,此…
阅读更多...
【VRRP】虚拟路由冗余协议

【VRRP】虚拟路由冗余协议

什么是VRRP&#xff1f; 虚拟路由冗余协议VRRP&#xff08;Virtual Router Redundancy Protocol&#xff09;是一种用于提高网络可靠性的容错协议。通过VRRP&#xff0c;可以在主机的下一跳设备出现故障时&#xff0c;及时将业务切换到备份设备&#xff0c;从而保障网络通信的…
阅读更多...
Redis基础知识

Redis基础知识

Redis基础知识 redis共有16个数据库&#xff0c;默认使用的是第0个 可以使用select进行切换数据库 # 切换数据库 127.0.0.1:6379> select 1 OK # 查看DB大小 127.0.0.1:6379[1]> DBSIZE (integer) 0查看当前数据库所有的key 127.0.0.1:6379> keys * #查看当前数据…
阅读更多...
Mybatis查询数据

Mybatis查询数据

上一篇我们介绍了在pom文件中引入mybatis依赖&#xff0c;配置了mybatis配置文件&#xff0c;通过读取配置文件创建了会话工厂&#xff0c;使用会话工厂创建会话获取连接对象读取到了数据库的基本信息。 如果您需要对上面的内容进行了解&#xff0c;可以参考Mybatis引入与使用…
阅读更多...
【业务功能篇87】微服务-springcloud-本地缓存-redis-分布式缓存-缓存穿透-雪崩-击穿

【业务功能篇87】微服务-springcloud-本地缓存-redis-分布式缓存-缓存穿透-雪崩-击穿

一、缓存 1. 什么是缓存 缓存的作用是减低对数据源的访问频率。从而提高我们系统的性能。 缓存的流程图 2.缓存的分类 2.1 本地缓存 其实就是把缓存数据存储在内存中(Map <String,Object>).在单体架构中肯定没有问题。 单体架构下的缓存处理 2.2 分布式缓存 在分布式环…
阅读更多...
Java学习笔记31——字符流

Java学习笔记31——字符流

字符流 字符流为什么出现字符流编码表字符串中的编码解码问题字符流写数据的5中方式字符流读数据的两种方式字符流复制Java文件 字符流 为什么出现字符流 汉字的存储如果是GBK编码占用2个字节&#xff0c;如果是UTF-8占用三个字节 用字节流复制文本文件时&#xff0c;文本文…
阅读更多...
2023年腾讯云轻量应用服务器优缺点大全

2023年腾讯云轻量应用服务器优缺点大全

2023年腾讯云轻量应用服务器优缺点大全&#xff0c;腾讯云轻量应用服务器性能如何&#xff1f;轻量服务器CPU内存带宽配置高&#xff0c;CPU采用什么型号主频多少&#xff1f;轻量应用服务器会不会比云服务器CVM性能差&#xff1f;腾讯云服务器网详解CPU型号主频、内存、公网带…
阅读更多...
Linux通过libudev获取挂载路径、监控U盘热拔插事件、U盘文件系统类型

Linux通过libudev获取挂载路径、监控U盘热拔插事件、U盘文件系统类型

文章目录 获取挂载路径监控U盘热拔插事件libusb 文件系统类型通过挂载点获取挂载路径添libudev加库 获取挂载路径 #include <stdio.h> #include <libudev.h> #include <string.h>int main() {struct udev *udev;struct udev_enumerate *enumerate;struct ud…
阅读更多...
数据库备份和Shell基础测试及AWK（运维）

数据库备份和Shell基础测试及AWK（运维）

第一题&#xff1a;简述一下如何用mysql命令进行备份和恢复&#xff0c;请以test库为例&#xff0c;创建一个备份&#xff0c;并再用此备份恢复备份 备份步骤&#xff1a; 备份test库&#xff1a;使用mysqldump命令备份test库&#xff0c;并将备份写入一个.sql文件中。命令示例…
阅读更多...
【第1章 数据结构概述】

【第1章 数据结构概述】

目录 一. 基本概念 1. 数据、数据元素、数据对象 2. 数据结构 二. 数据结构的分类 1. 数据的逻辑结构可分为两大类&#xff1a;a. 线性结构&#xff1b;b. 非线性结构 2. 数据的存储结构取决于四种基本的存储方法&#xff1a;顺序存储、链接存储、索引存储、散列存储 3. …
阅读更多...
【力扣每日一题】2023.8.24 统计参与通信的服务器

【力扣每日一题】2023.8.24 统计参与通信的服务器

目录 题目&#xff1a; 示例&#xff1a; 分析&#xff1a; 代码&#xff1a; 题目&#xff1a; 示例&#xff1a; 分析&#xff1a; 题目顾名思义&#xff0c;要我们统计参与通信的服务器&#xff0c;给我们一个二维矩阵&#xff0c;元素为1的位置则表示是一台服务器。 …
阅读更多...
学习Linux基础知识与命令行操作

学习Linux基础知识与命令行操作

开始学习Linux系统前&#xff0c;首先要掌握计算机基础知识&#xff0c;了解硬件、操作系统、文件系统、网络和安全等概念。对这些基础知识的了解能够帮助理解Linux系统的概念和功能。 在Linux系统中&#xff0c;文件和目录是数据管理的基本单位。每个文件和目录都有一个称为&…
阅读更多...
OAuth2.0 知识点梳理

OAuth2.0 知识点梳理

文章目录 OAuth2.0 知识点梳理一、四种角色二、四种模式的概述三、四种模式的图解 OAuth2.0 知识点梳理 一、四种角色 为了能够更好的理解本文中后续的内容&#xff0c;这里我先说下&#xff0c;OAuth2.0 中相关的四种角色&#xff0c;如下&#xff1a; 资源拥有者资源服务客…
阅读更多...
内网实战1

内网实战1

1、信息收集&#xff1a; 使用nmap做端口扫描&#xff1a; nmap -sV -Pn -T4 192.168.26.174重要端口&#xff1a;80、445、139、135、3306 目录扫描&#xff1a; 访问80端口&#xff1a;发现一个网站是phpstudy搭建的&#xff1b; 发现一个mysql数据库&#xff0c;那我们…
阅读更多...
[QT]设置程序仅打开一个，再打开就唤醒已打开程序的窗口

[QT]设置程序仅打开一个，再打开就唤醒已打开程序的窗口

需求&#xff1a;speedcrunch 这个软件是开源的计算器软件。配合launch类软件使用时&#xff0c;忘记关闭就经常很多窗口&#xff0c;强迫症&#xff0c;从网上搜索对版本进行了修改。 #include "gui/mainwindow.h"#include <QCoreApplication> #include <…
阅读更多...
CocosCreator3.8研究笔记（一）windows环境安装配置

CocosCreator3.8研究笔记（一）windows环境安装配置

一、安装Cocos 编辑器 &#xff08;1&#xff09;、下载Cocos Dashboard安装文件 Cocos 官方网站Cocos Dashboard下载地址 &#xff1a; https://www.cocos.com/creator-download9下载完成后会得到CocosDashboard-v2.0.1-win-082215.exe 安装文件&#xff0c;双击安装即可。 …
阅读更多...
智能工厂移动式作业轻薄加固三防平板数据采集终端

智能工厂移动式作业轻薄加固三防平板数据采集终端

在这个高度自动化和数字化的环境中&#xff0c;数据采集变得尤为重要。为了满足这个需求&#xff0c;工业三防平板数据采集终端应运而生。工业三防平板数据采集终端采用了轻量级高强度镁合金材质&#xff0c;这使得它在保持轻薄的同时具有更强的坚固性。这种材质还具有耐磨防损…
阅读更多...
机器学习笔记之核函数再回首：Nadarya-Watson核回归python手写示例

机器学习笔记之核函数再回首：Nadarya-Watson核回归python手写示例

机器学习笔记之核函数再回首——Nadaraya-Watson核回归手写示例 引言回顾&#xff1a; Nadaraya-Watson \text{Nadaraya-Watson} Nadaraya-Watson核回归通过核函数描述样本之间的关联关系使用 Softmax \text{Softmax} Softmax函数对权重进行划分将权重与相应标签执行加权运算 N…
阅读更多...
自动化测试(三)：接口自动化pytest测试框架

自动化测试(三)：接口自动化pytest测试框架

文章目录 1. 接口自动化的实现2. 知识要点及实践2.1 requests.post传递的参数本质2.2 pytest单元测试框架2.2.1 pytest框架简介2.2.2 pytest装饰器2.2.3 断言、allure测试报告2.2.4 接口关联、封装改进YAML动态传参&#xff08;热加载&#xff09; 2.3 pytest接口封装&#xff…
阅读更多...
Android 绘制之文字测量

Android 绘制之文字测量

drawText() 绘制文字 绘制进度条:paint.strokeCap Paint.CAP.RONUD 线条两边样式 设置文字字体:paint.typeFace Resources.Compat.getFont(context,font) 设置加粗 paint.isFakeBoldText 设置居中: paint.setTextAlign Paint.Align.CENTER //居中, 并不是真正的居中 往…
阅读更多...
最新文章

Copyright @ 2022~2023