锐客网

  1. 首页 > 睿知 > it技术 > >

数据结构第五站（树和二叉树）

IT知识数据结构数据

出门莫恨无人随，书中车马多如簇。这篇文章主要讲述数据结构第五站：树和二叉树相关的知识，希望能为你提供帮助。

一.树的定义

??树（?Tree?）是n(n> =0)个结点的有限集，它既可以是??空树??，也可以是??非空树。????
???对于?非空树T?：???
???（1）?有且仅有?一个称之为根的结点。???
???（2）除根结点以外的其余结点可以分为m个互不相交的有限集T1，T2，T3.....,Tm,其中每一个集合又是一棵树，并且成为根的子树（?Subtree?）。???

二.二叉树（一）定义
??二叉树（?Binary Tree?)是n（n> =0）个结点所构成的集合，它既可以是??空树??，也可以是??非空树????
???对于?非空树T?：???
???（1）有且仅有一个称之为根的结点???
???（2）除根结点以外的其余结点分为两个互不相交的子集T1和T2，分别称为T的左右子              树???
???二叉树每个结点最多有两棵子树并且其子树有左右之分，次序不可以任意颠倒???

（二）重要类型二叉树
I.满二叉树定义
??深度为k且含有?2^k-1?个结点??
特点
??每一层的结点均是最大结点数??

II.完全二叉树定义
??在满二叉树中从最后一个结点开始，?连续去掉?任意个结点，即是一棵完全二叉树??
特点：
??（1）叶子结点?只可能?在层次最大的两层出现??
??（2）对任意一个结点，若其右分支下的子孙的最大层次为m，其左分支下的子孙的最大层次必为m或m+1(?即任意结点的左右子树层次相差0或1?)??

III.遍历二叉树定义
??遍历二叉树（?traversing binary tree?）是按照某条搜索路径访问树中的每个结点，使每个结点?均被且仅被?访问一次。??
??二叉树是有三个基本单元组成：?根结点?、?左子树?和?右子树???
?遍历方式（递归）?
??（1）方式1：先序遍历（根左右）??
??（2）方式2：中序遍历（左根右）??
??（3）方式3: 后序遍历（左右根）??
??（4）方式4：层次遍历（从左到右，从上到下）??

??由先序和后序的序列无法唯一确定二叉树的确定形态，由?先序+中序（或后序+中序?）可以唯一确定二叉树的形态??
??具体实例如下：??
??三个结点有五种二叉树形态如下：??

IV.线索二叉树定义
??二叉树链式存储结构中每个结点均有指向?前驱和后继?指针的二叉树称为线索二叉树??
?以?先序遍历的线索化为例??

V.哈夫曼树定义
??哈夫曼（Huffman）树又称最优树，是一类?带权路径长度?（如下图）最短的树??。

哈夫曼树的构造规则
??（1）根据给定的n个权值w1,w2,w3,w4,w5...wn,构造棵只有根结点的二叉树，这n棵二叉树构成的一个?森林F?.??
??  (2)在森林F中选取?两棵根结点的权值最小的树?作为左右子树构造一棵新的二叉树，且置新的二叉树德根结点的权值为其左、右子树上根结点的权值之和??
??（3）在森林F中删除这两棵树，同时将?新的二叉树加入到F?中??
??（4）重复（2）（3）步骤，直到F中只含有一棵树为止，这棵树便是哈夫曼树??

?哈夫曼编码规则?
?在构建好哈夫曼树后，根据“?左0右1?”规则来编码，节省空间?
?实例：?
【数据结构第五站（树和二叉树）】
三.二叉树相关代码（一）二叉树基本操作代码
/*二叉树遍历及相关基本操作先序、中序、后序遍历使用递归实现，层次遍历使用队列实现 */

#include< stdio.h>
#include< string.h>
#include< iostream>
using namespace std;
#define True 1
#define False 0
//测试数据:FCA##DB###EH##GM###

//树结点
typedef struct BiTNode
char data; //树结点数据域
struct BiTNode *rchild,*lchild; //左右孩子指针
BiTNode,*BiTree;

//队列结点
typedef struct QNode
BiTree data; //数据域
struct QNode *next; //指针域
QNode,*QueuePtr;
typedef struct
QueuePtr front; //队头指针
QueuePtr rear; //队尾指针
LinkQueue;

//函数声明
BiTree CreateBiTree(); //二叉树的创建（先序遍历）
void Copy(BiTree T,BiTree NewT); //二叉树的复制
int Depth(BiTree T); //计算二叉树的深度
int NodeCount(BiTree T); //统计二叉树的结点总个数
void PreOrderTraverse(BiTree T); //先序遍历二叉树
void InOrderTraverse(BiTree T); //中序遍历二叉树
void BaOrderTraverse(BiTree T); //后序遍历二叉树
void LevelTraverse(BiTree T); //层次遍历二叉树（队列）
void Swap(BiTree T); //交换左右子树

LinkQueue *InitQueue(); //队列的初始化
void EnQueue(LinkQueue *Q,BiTree T); //入队
void DeQueue(LinkQueue *Q); //出队
int Empty(LinkQueue *Q); //判断队列是否为空
BiTree GetHead(LinkQueue *Q); //获取队头元素

int main()
BiTree T;
int total,depth;
cout< < "请输入测试数据："< < endl;
T= CreateBiTree();
cout< < "先序遍历结果为："< < endl;
PreOrderTraverse(T);
printf("\\n");
cout< < "中序遍历结果为："< < endl;
InOrderTraverse(T);
printf("\\n");
cout< < "后序遍历结果为："< < endl;
BaOrderTraverse(T);
printf("\\n");
cout< < "层次遍历结果为："< < endl;
LevelTraverse(T);
Swap(T);
printf("\\n交换左右子树后的后序遍历结果为：\\n");
BaOrderTraverse(T);
total=NodeCount(T);
printf("\\n二叉树的结点总数为：%d\\n",total);
depth=Depth(T);
printf("二叉树的深度为：%d\\n",depth);
return 0;


//二叉树的创建
BiTree CreateBiTree()//按照先序次序输入二叉树中结点的值（一个字符），创建二叉链表表示的二叉树T
BiTree T;
char ch;
cin> > ch;
if(ch==#)T=NULL; //递归结束，建立树
else
T = new BiTNode; //生成根结点
T-> data=https://www.songbingjia.com/android/ch; //根结点的数据域置为ch
T-> lchild=CreateBiTree(); //递归创建左子树
T-> rchild=CreateBiTree(); //递归创建右子树

return T;

//复制二叉树
void Copy(BiTree T,BiTree NewT)//复制一棵和T完全相同的二叉树

if(T==NULL)

NewT=NULL;
printf("T为空树！\\n");

else
NewT=new BiTNode;

    推荐阅读


    上一篇：Flutter 专题68 图解基本约束 Box#yyds干货盘点#

    下一篇：#yyds干货盘点#wget/curl等ca证书失效问题解决办法