配套资源下载

数据结构资源下载导航【数据结构】

第6章树

6.1 应用实例

1. 数据压缩问题
2. 表达式的树形表示
3. 等价类划分问题

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 二叉树的性质

1. 在二叉树的第i层上至多有2^i-1个结点(i>=1)
2. 深度为k的二叉树至多有2^k-1个结点(k>=1)
3. 对于任意一颗二叉树T,若终端结点数为n₀,度为2的结点数为n₂,则n₀=n₂+1.

下面给出两种特殊的二叉树,然后讨论其相关性质。
满二叉树 深度为k且含有2^k-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.由中序和后序确定二叉树

思想：

后序确定根结点

中序确定左右结点