配套资源下载
第6章树
6.1 应用实例
- 数据压缩问题
- 表达式的树形表示
- 等价类划分问题
6.2 树的概念
6.2.1树的定义与表示
1.树的定义
树(tree)是n(n≥0)个结点的有限集合。当n=0时,称为“空树”;当n>0时,该集合满足如下条件。
①有且仅有一个称为“根"(root)的特定结点，该结点没有前驱结点，但有零个或多个直接后继结点。
②除根结点之外的n-1个结点可划分成m(m≥0)个互不相交的有限集T1,T2,T3,…,Tn,
每个Ti又是一棵树,称为“根的子树”(subtree)。每棵子树的根结点有且仅有一个直接前驱就是树的根结点,同时可以有零个或多个直接后继结点。
树的定义采用了递归定义的方法,即树的定义中又用到了树的概念,这正好反映了树的特性。
2.树的表示方法
①树形图表示
②嵌套集合表示法（文氏图表示法）
③广义表表示法（嵌套括号表示法）
④凹入表示法
6.2.2 树的基本术语
以下列出一些有关树的基本术语。
结点(node):包含一个数据元素及若干指向其子树的分支。如图6-5©中的树有A、B、C、 D、E等13个结点。
结点的度(degree):结点拥有子树的个数称为该结点的“度”。如图6-5©中结点A的度为3,结点B的度为2.
树的度:树中所有结点的度的最大值。如图6-5( c )树的度为3。
叶子结点(leaf):度为0的结点称为“叶子结点”,也称“终端结点”。如图6-5©中结点E、 K、L.G等均为叶子结点。
内部结点(internal node):度不为0的结点称为“内部结点”,也称为“分支结点”或“非终端结点”。如图6-5( c )中结点B、C、D等均为内部结点
下面借助人类族谱的一些术语描述树中结点之间的关系,以便直观理解
孩子结点(child):结点的子树的根(即直接后继)称为该结点的“孩子结点”。如图6-5© 中结点B、C、D是A结点的孩子结点,结点E、F是B结点的孩子结点。
双亲结点(parent):结点是其子树的根的双亲,即结点是其孩子的双亲。如图6-5©中结 点A是B、C、D的双亲结点,结点D是H、I、J的双亲结点。
兄弟结点(sibling):同一双亲的孩子结点之间互称兄弟结点。如图6-5©中结点H、I、J互 为兄弟结点。
堂兄弟:双亲是兄弟或堂兄弟的结点间互称堂兄弟结点。如图6-5©中结点E、G、H互为 堂兄弟,结点L、M也互为堂兄弟。
祖先结点(ancestor):结点的祖先结点是指从根结点到该结点的路径上的所有结点。如图 6-5©中结点K的祖先是A、B、F结点。
子孙结点(descendant):结点的子孙结点是指该结点的子树中的所有结点。 结点D的子孙有H、1、J、M结点
结点的层次(level):结点的层次从树根开始定义,根为第一层,根的孩子为第二层。若某 点在第系层,则其孩子就在第k+1层,以此米推。如图6-5©中结点C在第二层,结点M在 四层
树的深度(deph):树中所有结点层次的最大值称为树的“深度”，也称树的“高度”。如果 6-5©中的树的深度为4。
前辈:层号比某结点层号小的结点，都可称为该结点的“前辈”。如图6-5©中结点A、B C、D都可称为结点E的前辈。
后辈:层号比某结点层号大的结点,都可称为该结点的“后辈”。如图6-5©中结点K、L 都可称为结点E的后辈
森林(forest):m(m=0)棵互不相交的树的集合称为“森林”。在数据结构中,树和森林不像自然界中有明显的量的差别,可以称0棵树、1棵树为森林。任意一棵非空的树，删去根结点变成了森林;反之,给森林中各棵树增加一个统一的根结点,就变成了一棵树
有序树(ordered tree)和无序树(unordered tree):树中结点的各棵子树从左到右是有特定次序的树称为“有序树”,否则称为“无序树”。
6.2.3树的抽象数据类型定义
略
6.3 二叉树
6.3.1二叉树的定义
二叉树(binary tree)是n(n20)个结点的有限集合。当n时,称为“空二叉树”;当n>( 时,该集合由一个根结点及两棵互不相交的,被分别称为“左子树”和“右子树”的二叉树 组成。
以前面定义的树为基础,二叉树可 以理解为是满足以下两个条件的树形结构
① 每个结点的度不大于2。
② 结点每棵子树的位置是明确区分左右的,不能随意改变。
由上述定义可以看出:二叉树中的每个结点只能有0、1或2个孩子,而且孩子有左右之分, 即使仅有一个孩子,也必须区分左右。位于左边的孩子(或子树)叫左孩子(左子树),位于右边 的孩子(或子树)叫右孩子(右子树)。
二叉树也是树形结构,故6.2.2小节所介绍的有关树的术语都适用于二叉树。
二叉树不是结点度不大于2的有序树，
反例：只有右子树的二叉树和只有左子树的二叉树不同
6.3.2 二叉树的性质
- 在二叉树的第i层上至多有2i-1个结点(i>=1)
- 深度为k的二叉树至多有2k-1个结点(k>=1)
- 对于任意一颗二叉树T,若终端结点数为n0,度为2的结点数为n2,则n0=n2+1.
下面给出两种特殊的二叉树,然后讨论其相关性质。
满二叉树 深度为k且含有2k-1个结占的一叉树称为“满二叉树”
满二叉树的连续编号：对含有n个结点的的满二叉树，约定从根开始,按层从上到下，每
层内从左到右,逐个对每一结点进行编号1,2,…,n。
完全二叉树 深度为k、结点数为n(n<=2k-1)的二叉树，当且仅当其n个结点与满二叉树
中连续编号为1至n的结点位置一一对应时，称为“完全二叉树”。
完全二叉树有两个重要特征:其一,所有叶子结点只可能出现在层号最大的两层上;其二,对
任意结点,若其右子树的层高为k,则其左子树的层高只可为k或k+1。
由定义可知,满二叉树必为完全二叉树,而完全二叉树不一定是满二叉树。
4.具有n个结点的完全二叉树的深度为[log2n」+1。向下取整
5.对于具有n个结点的完全二叉树,如果按照对满二义树结点进行连续编号的方式，
对所有结点从1开始顺序编号,则对于任意序号为的结点有以下结论。
① 如果i=1,则结点i为根,其无双亲结点；如果i>1,则结点i,则结点i的双亲结点为[i/2] 向下取整
② 如果2i<=n,则结点i的左孩子结点序号为2i,否则,结点i无左孩子。
③ 如果2i+1<=n,则结点i的右孩子结点序号为2i+1,否则,结点i无右孩子。
6.3.3 二叉树的存储
1.顺序存储结构
对于满二叉树和完全二叉树来说,可以按照对满二叉树结点连续编号的次序,将各结点数据
存放到一组连续的存储单元中,即用一维数组作存储结构,将二又树中编号为i的结点存放在数
组的第i号分量中、根据二叉树的性质5,可知数组中下标为i的结点的左孩子下标为2i,右孩
子下标为2i+1,双亲结点的下标为[ i/2」。
二叉树的顺序存储结构可描述如下。
#define MAX 100 typedef struct{ datatype SqBiTree[ MAX+1]; //0号单元不用 int nodemax; //数组中最后一个结点的下标 }Bitree;
2.链式存储结构
二叉树的二叉链表结点结构：
LChild域指向该结点的左孩子
Data域指向该结点的数据
RChild域指向该结点的右孩子
typedef char DataType; typedef struct Node{ DataType data; struct Node * LChild; struct Node * RChild; }BiTNode,*BiTree;
一个二叉树含有n个结点，则它的二叉链表中必含有2n个指针域，而仅有n-1个指针域指向其孩子，其余的n+1的指针域为空的链域。
可以用空链域存储其他有用的信息，便得到“线索二叉树”
二叉树的三叉链表结点结构：
Parent域指向该结点的双亲
LChild域指向该结点的左孩子
Data域指向该结点的数据
RChild域指向该结点的右孩子
6.4 二叉树的遍历
6.4.1 二叉树的遍历及递归实现
依据对根结点访问的先后次序不同来命名二叉树的访问方式,分别称DLR为先序遍历(或
先根遍历)、LDR为中序遍历(或中根遍历),LRD为后序遍历(或后根遍历)
下面给出二叉树三种遍历方式的递归定义。
(1)先序遍历
其二叉树为空,则空操作;否则依次执行如下二个操作，
①访问根结点。
②按先序遍历左子树。
③按先序遍历右子树。
(2)中序遍历
若二叉树为空,则空操作;否则依次执行如下三个操作。
①按中序遍历左子树。
②访问根结点。
③按中序遍历右子树。
(3)后序遍历
若二叉树为空,则空操作;否则依次执行如下三个操作。
①按后序遍历左子树。
②遍历右子树。
③访问根结点。
二叉树遍历的递归实现
6.4.2 二叉树遍历的非递归实现
1.先序遍历二叉树的非递归实现
2.中序遍历二叉树的非递归实现
3.后序遍历二叉树的非递归实现
4.二叉树的层次遍历
6.4.3 遍历算法的应用
1.统计二叉树的结点数
2.输出二叉树的叶子结点
3.统计二叉树的叶子结点数目
4.求二叉树的高度
5.求结点的双亲
6.二叉树相似性判定
7.按树状打印二叉树
8.创建二叉链表存储的二叉树
数据结构 二叉树.c 所有代码最全建议下载
二叉树最完整代码资源
int main(){ BiTree root; BiTree *_root=&root; printf("输入扩展先序序列\n"); //ABD^G^^^CE^H^^F^^ CreateBiTree(_root); printf("先序序列（递归）\n"); PreOrder(root); printf("\n"); printf("中序序列（递归）\n"); InOrder(root); printf("\n"); printf("后序序列（递归）\n"); PostOrder(root); printf("\n"); printf("先序序列（非递归）\n"); PreOrderN(root); printf("\n"); printf("中序序列-1（非递归）\n"); InOrderN1(root); printf("\n"); printf("中序序列-2（非递归）\n"); InOrderN2(root); printf("\n"); printf("后序序列（非递归）\n"); PostOrderN(root); printf("\n"); printf("层次遍历\n"); LevelOrder(root); printf("\n"); if(Count!=0){ Count=0; } printf("统计结点数\n"); CountWithPreOrder(root); printf("%d",Count); printf("\n"); printf("输出叶子结点\n"); PrintTNWithInOrder(root); printf("\n"); printf("统计叶子结点数\n"); int leafCount=leaf(root); printf("%d",leafCount); printf("\n"); if(depth!=0){ depth=0; } printf("二叉树的高度\n"); TreeDepth(root,1); printf("%d",depth); printf("\n"); printf("二叉树的高度\n"); int dpth=PostTreeDepth(root); printf("%d",dpth); printf("\n"); printf("求双亲\n"); BiTree current=(root->LChild)->LChild; BiTree pt=parent(root,current); Visit(pt->data); printf("\n"); BiTree rt; BiTree *_rt=&rt; printf("输入rt扩展先序序列\n"); //ABD^G^^^CE^H^^F^^ fflush(stdin); //清一下输入的\n CreateBiTree(_rt); printf("先序序列（递归）\n"); PreOrder(rt); printf("\n"); printf("root和rt是否相似\n"); int lk=like(root,rt); printf("%d",lk); printf("\n"); printf("树状打印\n"); int depth=PostTreeDepth(root); PrintTree(root,depth); }
展示类结构
运行展示
6.4.4由遍历序列确定二叉树
1.由先序和中序确定二叉树
思想：
先序确定根结点
中序确定左右结点
2.由中序和后序确定二叉树
思想：
后序确定根结点
中序确定左右结点
