树与图c++

这篇具有很好参考价值的文章主要介绍了树与图c++。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

1.树

前言

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

一、树的基本概念

层次结构的数据在现实世界中大量存在。例如,一个国家有若干省,一个省有若干市县,一个市县有若干区乡。又如,一本书包含若干章,一章包含若干节,一节包含若干段。例如,下图是数组的层次关系,这种描述树形数据的形式称为倒置的树形表示法。
树与图c++,编程,c++,开发语言,算法,数据结构,树,图

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

1.1树的定义

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

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

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

1.2基本术语

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

树与图c++,编程,c++,开发语言,算法,数据结构,树,图

树中元素称为结点(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所示的五种基本形态。
树与图c++,编程,c++,开发语言,算法,数据结构,树,图

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

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

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

树与图c++,编程,c++,开发语言,算法,数据结构,树,图

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

这个性质很容易理解:

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

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

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

树与图c++,编程,c++,开发语言,算法,数据结构,树,图

在图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=n1

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) i0=<i<=n1的结点,有

(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]向下取整。(求双亲注意双亲只有一个)

树与图c++,编程,c++,开发语言,算法,数据结构,树,图

2.3二叉树的ADT
ADT BinTree

数据:

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

运算:

Create()

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

IsEmpty()

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

PreOrder()

前序遍历二叉树。

InOrder()

中序遍历二叉树。

PostOrder()

后序遍历二叉树。

Display():

输出二叉树。

三、二叉树的存储表示

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

【例1】:将图7(a)所示的二叉树,用一维字符数组表示。
树与图c++,编程,c++,开发语言,算法,数据结构,树,图

解:

首先将图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。

树与图c++,编程,c++,开发语言,算法,数据结构,树,图

具体的创建过程如下:

(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所示:
树与图c++,编程,c++,开发语言,算法,数据结构,树,图

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

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

(1)由前序遍历ABEKC,A为根结点;由中序遍历BEKAC,BEK为左子树,C为右子树;其对应的二叉树如图17所示。
树与图c++,编程,c++,开发语言,算法,数据结构,树,图

(2)对于左子树,由前序遍历BEK,B为根结点;由中序遍历BEK,EK为右子树,其对应的二叉树如图18所示。
树与图c++,编程,c++,开发语言,算法,数据结构,树,图

(3)对于右子树,由前序遍历EK,E为根结点;由中序遍历EK,K为右子树,其对应的二叉树如图19所示。
树与图c++,编程,c++,开发语言,算法,数据结构,树,图

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

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

(1)若左子树不空,则左子树上所有结点的值均小于根结点的值;(左小于根)

(2)若右子树不空,则右子树上所有结点的值均大于根结点的值;(右大于根)

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

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

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

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

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

树与图c++,编程,c++,开发语言,算法,数据结构,树,图

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

#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所示:

树与图c++,编程,c++,开发语言,算法,数据结构,树,图

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

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 )。
树与图c++,编程,c++,开发语言,算法,数据结构,树,图

图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所示。
树与图c++,编程,c++,开发语言,算法,数据结构,树,图

图28
(2)从T中选取前两棵的二叉树,分别作为左、右子树,构造一棵新二叉树(注意,排序在前的作左子树),对T中权值再按升序排序(注意,如果出现权值相等的情况,则原树排前,新树排后),T如图29所示。
树与图c++,编程,c++,开发语言,算法,数据结构,树,图

图29
(3)反复重复第(2)步的操作,T如图30 — 图32所示。
树与图c++,编程,c++,开发语言,算法,数据结构,树,图

图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×n01

性质3: 哈夫曼树的带权路径长度等于所有度为2的结点值之和。文章来源地址https://www.toymoban.com/news/detail-685165.html

到了这里,关于树与图c++的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构与算法】树与二叉树

    除了之前我们讲的栈、队列、链表等线性结构,数据结构中还有着一对多的 非线性结构 ——— 树 。 树是有 n 个结点组成的有限集,当n=0时为空树,在任意一颗非空树中,有且仅有一个 特定的根结点 ;当n1时,其余结点又可以分为一棵树,称为根的 子树 。 如下图所示: A为

    2023年04月09日
    浏览(50)
  • 数据结构与算法——树与二叉树

    😊各位小伙伴久等了,本专栏新文章出炉了!!! 我又回来啦,接下来的时间里,我会持续把数据结构与算法专栏更新完。 👉树型结构👈 是一类重要的 ✍非线性数据结构 ,其中以树和二叉树最为常用,直观来看,树是以分支关系定义的层次结构。树型结构在客观世界中

    2024年02月11日
    浏览(46)
  • 数据结构与算法——树与二叉树篇详解

    树形结构是一种非常重要的 非线性结构 ,树形结构中数据元素之间具有 一对多 的逻辑关系。 1.1.1 树的定义 树是由n(n=0)个结点所构成的有限集合 当n=0时,称为空树 当n0时,n个结点满足以下条件 有且仅有一个称为根的结点 其余结点可分为m个互不相交的有限集合,且每一个

    2024年02月06日
    浏览(50)
  • 数据结构之树与二叉树——算法与数据结构入门笔记(五)

    本文是算法与数据结构的学习笔记第五篇,将持续更新,欢迎小伙伴们阅读学习。有不懂的或错误的地方,欢迎交流 前面章节介绍的都是线性存储的数据结构,包括数组、链表、栈、队列。本节带大家学习一种非线性存储的数据结构,即树(tree)。 不管是在面试时,还是日

    2024年02月08日
    浏览(50)
  • 数据结构与算法--二叉树与树(单选题含题解)

    1、对以下算法功能最准确的描述是()。 A.判断二叉树根结点值是否为e B.判断二叉树是否存在值为e结点 C.求二叉树中值为e结点的层次 D.求二叉树值为e的结点的个数 C 2、二叉树的形态 由 3 个结点可以构造出 ▁▁▁▁▁ 种不同形态的二叉树。 A.2 B.3 C.4 D.5 D 由n个结点可以构

    2024年02月03日
    浏览(41)
  • 【数据结构】树与二叉树(十三):递归复制二叉树(算法CopyTree)

      二叉树是一种常见的树状数据结构,它由结点的有限集合组成。一个二叉树要么是 空集 ,被称为 空二叉树 ,要么由一个根结点和两棵不相交的子树组成,分别称为 左子树 和 右子树 。每个结点最多有两个子结点,分别称为左子结点和右子结点。 引理5.1:二叉树中层数

    2024年02月01日
    浏览(40)
  • 算法与数据结构--二叉搜索树与自平衡二叉搜索树

    注:字典的 \\\"member运算\\\" 指的是检查字典中是否存在某个特定的键的操作,即查询操作。 如果我们使用数组来实现字典/map,虽然使用二分法查询也可以达到logn,但是的话插入和删除太慢了。使用链表实现的话虽然插入和删除是O(1),但是查询的话达到了O(n),也不可取。 因此人

    2024年02月04日
    浏览(38)
  • 《数据结构、算法与应用C++语言描述》-列车车厢重排问题

    完整可编译运行代码见:Github::Data-Structures-Algorithms-and-Applications/_10Train_carriages_rearrangement/ 一列货运列车有 n 节车厢,每节车厢要停靠在不同的车站。假设 n个车站从 1 到n 编号,而且货运列车按照从n到1的顺序经过车站。车厢的编号与它们要停靠的车站编号相同。为了便于从

    2024年04月10日
    浏览(67)
  • 第五课 树与图

    题目描述 给定一个二叉树的根节点 root ,返回 它的 中序 遍历 。 示例 1: 示例 2: 示例 3: 提示: 树中节点数目在范围 [0, 100] 内 -100 = Node.val = 100 代码展示 题目描述 给定一个 N 叉树,返回其节点值的 层序遍历 。(即从左到右,逐层遍历)。 树的序列化输入是用层序遍历

    2024年02月07日
    浏览(44)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包