第七章二叉树

1、第七章 二叉树数据结构与关系数据库数据结构与关系数据库 福 建 江 夏 学 院 FUJIAN JIANGXIA UNIVERSITY应用场景 某公司想通过网络传输一些秘密信息给客户，把这些秘密信某公司想通过网络传输一些秘密信息给客户，把这些秘密信息变成二进制码进行传输，为了节省数据文件在计算机内的息变成二进制码进行传输，为了节省数据文件在计算机内的存储空间和提高信息的传输速度，必须采用一种有效的编码存储空间和提高信息的传输速度，必须采用一种有效的编码方法，编写程序实现之，得到如下所示的输出结果。方法，编写程序实现之，得到如下所示的输出结果。 掌握树、森林和二叉树的概念，掌握哈夫曼树的构造及哈弗

2、曼编码，掌握如何把树或森林转化为二叉树，掌握二叉树的基本性质、存储结构、遍历。 教学重点与难点： 二叉树基本运算和存储结构，二叉树的遍历。 教学目的与要求1.二叉树的第k层的结点数最多为多少？2(k-1)2设一棵二叉树的深度为k，则该二叉树中最多有多少个结点？2k-1问题二叉树（二叉树（Binary Tree）是个有限元素的集合，该集合或者为空、或者由一个称为根）是个有限元素的集合，该集合或者为空、或者由一个称为根(root)的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成。当集合为空时，称该的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成。当集合为空时，称该二叉树为空二叉

3、树。在二叉树中，一个元素也称作一个结点。二叉树为空二叉树。在二叉树中，一个元素也称作一个结点。二叉树是有序的，即若将其左、右子树颠倒，就成为另一棵不同的二叉树。即使树中结二叉树是有序的，即若将其左、右子树颠倒，就成为另一棵不同的二叉树。即使树中结点只有一棵子树，也要区分它是左子树还是右子树。因此二叉树具有五种基本形态，如图点只有一棵子树，也要区分它是左子树还是右子树。因此二叉树具有五种基本形态，如图7.1 所示。所示。7.1 二叉树的基本概念左子树左子树右子树右子树右子树右子树左子树左子树图图7.1 7.1 二叉树的五种基本状态二叉树的五种基本状态（b b）(c)(c)(d)(d)(e)(e)

4、满二叉树满二叉树在一棵二叉树中，如果在一棵二叉树中，如果满足：满足：（1）所有分支结点都存在左子树和右子树所有分支结点都存在左子树和右子树；（；（2）所所有叶子结点都在同一层上有叶子结点都在同一层上,则则这样的一棵二叉树称作满二叉树。这样的一棵二叉树称作满二叉树。如图如图7.2所示，所示，（a）图就是一棵满二叉树，（）图就是一棵满二叉树，（b）图则不是满二叉树）图则不是满二叉树。7.1 二叉树的基本概念A AB BC CD DE EF FG GH HI I1 12 23 34 45 56 67 78 89 9A AB BC CD DE EF FG GH HI IJ JK KL LM MN NO

5、 O1 12 23 34 45 56 67 78 89 9101011111212131314141515图图7.27.2（a a）一棵满二叉树）一棵满二叉树（b b）一棵非满二叉树）一棵非满二叉树完全二叉树完全二叉树一棵深度为一棵深度为k 的有的有n 个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为如果编号为i（1in）的结点与满二叉树中编号为）的结点与满二叉树中编号为i 的结点在二叉树中的位置相同的结点在二叉树中的位置相同，则这棵二，则这棵二叉树称为完全二叉树。完全二叉树的叉树称为完全二叉树。完全二叉

6、树的特点是：叶子结点只能出现在最下层和次下层，且最下特点是：叶子结点只能出现在最下层和次下层，且最下层的叶子结点集中在树的左部层的叶子结点集中在树的左部。显然，一棵满二叉树必定是一棵完全二叉树，而完全二叉树。显然，一棵满二叉树必定是一棵完全二叉树，而完全二叉树未必是满二叉树未必是满二叉树。7.1 二叉树的基本概念A AB BC CD DE EF FG GH HI IJ J1 12 23 34 45 56 67 78 89 91010图图7.37.3（a a）一棵完全二叉树）一棵完全二叉树A AB BC CD DE EF FG G1 12 23 34 46 67 78 8（b b）一棵非完全二叉

7、树）一棵非完全二叉树性质性质1 一棵非空二叉树的第一棵非空二叉树的第i 层上最多有层上最多有2i-1 个结点（个结点（i1）。）。性质性质2 一棵深度为一棵深度为k 的二叉树中，最多具有的二叉树中，最多具有2k1 个结点。个结点。性质性质3 对于一棵非空的二叉树，如果叶子结点数为对于一棵非空的二叉树，如果叶子结点数为n0，度数为，度数为2 的结点数为的结点数为n2，则有，则有:n0n21。7.2 二叉树的性质 性质性质4 具有具有n 个结点的完全二叉树的深度个结点的完全二叉树的深度k 为为log2n+1。 性质性质5 对于具有对于具有n 个结点的完全二叉树，如果按照从上至下和从左到右的个结点的

8、完全二叉树，如果按照从上至下和从左到右的顺序对二叉树中的所有结点从顺序对二叉树中的所有结点从1 开始顺序编号，则对于任意的序号为开始顺序编号，则对于任意的序号为i 的结的结点，有：点，有： （1）如果）如果i1，则序号为，则序号为i 的结点的双亲结点的序号为的结点的双亲结点的序号为i/2(“/”表示整除表示整除)；如；如果果i1，则序号为，则序号为i 的结点是根结点，无双亲结点。的结点是根结点，无双亲结点。 （2）如果）如果2in，则序号为，则序号为i 的结点的左孩子结点的序号为的结点的左孩子结点的序号为2i；如果；如果2in，则，则序号为序号为i 的结点无左孩子。的结点无左孩子。 （3）如果

9、）如果2i1n，则序号为，则序号为i 的结点的右孩子结点的序号为的结点的右孩子结点的序号为2i1；如果；如果2i1n，则序号为，则序号为i 的结点无右孩子。的结点无右孩子。7.2 二叉树的性质一、顺序存储结构一、顺序存储结构 所谓二叉树的顺序存储，就是用一组所谓二叉树的顺序存储，就是用一组连续的存储单元存放二叉树中的连续的存储单元存放二叉树中的结点结点。一般是按照二叉树结点。一般是按照二叉树结点从上至下、从左到右从上至下、从左到右的顺序存储。的顺序存储。7.3 二叉树的存储一棵完全二叉树一棵完全二叉树图图7.4 7.4 完全二叉树的顺序存储示意图完全二叉树的顺序存储示意图一、顺序存储结构一、顺

10、序存储结构7.3 二叉树的存储（b b）一棵不完全二叉树）一棵不完全二叉树（c c）改造后的完全二叉树）改造后的完全二叉树图图7.5 7.5 一般二叉树及其顺序存储示意图一般二叉树及其顺序存储示意图一、顺序存储结构一、顺序存储结构二叉树的顺序存储表示可描述为：二叉树的顺序存储表示可描述为：即将即将bt 定义为含有定义为含有MAXNODE 个个elemtype 类型元素的一类型元素的一维数组。维数组。7.3 二叉树的存储#define MAXNODE /#define MAXNODE /* *二叉树的最大结点数二叉树的最大结点数* */ /typedef elemtype SqBiTreeMAX

11、NODE typedef elemtype SqBiTreeMAXNODE / /* *0 0 号单元存放根结点号单元存放根结点* */ /SqBiTree bt;SqBiTree bt;（1）二叉链表存储）二叉链表存储 链表中每个结点由三个域组成，除了数据域外，还有两个指针域，链表中每个结点由三个域组成，除了数据域外，还有两个指针域，分别用来给出该结点左孩子和右孩子所在的链结点的存储地址。结分别用来给出该结点左孩子和右孩子所在的链结点的存储地址。结点的存储的结构为：点的存储的结构为： 其中，其中，data 域存放某结点的数据信息；域存放某结点的数据信息；lchild 与与rchild 分别存

12、放指向分别存放指向左孩子和右孩子的指针，当左孩子或右孩子不存在时，相应指针域左孩子和右孩子的指针，当左孩子或右孩子不存在时，相应指针域值为空（用符号值为空（用符号或或NULL 表示）。表示）。 二、链式存储结构（1）二叉链表存储）二叉链表存储二、链式存储结构（a）带头指针二叉链表（b）带头结点二叉链表（2）三三叉链表存储叉链表存储 每个结点由四个域组成，具体结构为：每个结点由四个域组成，具体结构为： 其中，其中，data、lchild 以及以及rchild 三个域的意义同二叉链表结构；三个域的意义同二叉链表结构；parent 域为指向该结点双亲结点的指针。域为指向该结点双亲结点的指针。 这种存

13、储结构既便于查找孩子结点，又便于查找双亲结点；但是，这种存储结构既便于查找孩子结点，又便于查找双亲结点；但是，相对于二叉链表存储结构而言，它增加了空间开销。相对于二叉链表存储结构而言，它增加了空间开销。二、链式存储结构（2）三三叉链表存储叉链表存储二、链式存储结构二叉树的二叉链表存储表示可描述为：即将BiTree 定义为指向二叉链表结点结构的指针类型。二、链式存储结构typedef struct BiTNode elemtype data; struct BiTNode *lchild,*rchild; /*左右孩子指针*/BiTNode,*BiTree;注：注：* * * * * * * *

14、 * *二叉链表是最常用的二叉树存储方式二叉链表是最常用的二叉树存储方式 知识回顾二叉树的定义二叉树的定义二叉树（二叉树（Binary Tree）是个有限元素的集合，该集合或者为）是个有限元素的集合，该集合或者为空空、或者、或者由一个称为根由一个称为根(root)的元素及两个不相交的、被分别称为的元素及两个不相交的、被分别称为左子树左子树和和右子树右子树的的二叉树组成。二叉树组成。A AB BC CD DE EF FG GH HI I1 12 23 34 45 56 67 78 89 9知识回顾二叉树的存储二叉树的存储顺序存储顺序存储二叉链表二叉链表三叉链表三叉链表结构如何定义？结构如何定义？

15、一、二叉树的基本操作一、二叉树的基本操作（1）Initiate（bt）建立一棵空二叉树。（2）Create（x，lbt，rbt）生成一棵以x 为根结点的数据域信息，以二叉树lbt 和rbt为左子树和右子树的二叉树。（3）InsertL（bt，x，parent）将数据域信息为x 的结点插入到二叉树bt 中作为结点parent 的左孩子结点。如果结点parent 原来有左孩子结点，则将结点parent 原来的左孩子结点作为结点x 的左孩子结点。（4）InsertR（bt，x，parent）将数据域信息为x 的结点插入到二叉树bt 中作为结点parent 的右孩子结点。如果结点parent 原来有右

16、孩子结点，则将结点parent 原来的右孩子结点作为结点x 的右孩子结点。（5）DeleteL（bt，parent）在二叉树bt 中删除结点parent 的左子树。（6）DeleteR（bt，parent）在二叉树bt 中删除结点parent 的右子树。（7）Search（bt，x）在二叉树bt 中查找数据元素x。（8）Traverse（bt）按某种方式遍历二叉树bt 的全部结点。7.4 二叉树的基本操作及实现（1）Initiate（bt）初始建立二叉树）初始建立二叉树bt，并使，并使bt 指向头结点。在指向头结点。在二叉树根结点前建立头结点，就如同在单链表前建立的头结点，二叉树根结点前建立头

17、结点，就如同在单链表前建立的头结点，可以方便后边的一些操作实现。可以方便后边的一些操作实现。二、算法实现int Initiate (BiTree int Initiate (BiTree * *bt)bt) / /* *初始化建立二叉树初始化建立二叉树* *bt bt 的头结点的头结点* */ /if(if(* *bt=(BiTNode bt=(BiTNode * *)malloc(sizeof(BiTNode)=NULL)malloc(sizeof(BiTNode)=NULL)return 0;return 0;( (* *bt)-lchild=NULL;bt)-lchild=NULL;(

18、(* *bt)-rchild=NULL;bt)-rchild=NULL;return 1;return 1; /算法算法7.17.1（2）Create（x，lbt，rbt）建立一棵以）建立一棵以x 为根结点的数据域信息，以二叉为根结点的数据域信息，以二叉树树lbt 和和rbt为左右子树的二叉树。建立成功时返回所建二叉树结点的指针；为左右子树的二叉树。建立成功时返回所建二叉树结点的指针；建立失败时返回空指针。建立失败时返回空指针。二、算法实现BiTree Create(elemtype x,BiTree lbt,BiTree rbt)BiTree Create(elemtype x,BiTree

19、 lbt,BiTree rbt) / /* *生成一棵以生成一棵以x x 为根结点的数据域值以为根结点的数据域值以lbt lbt 和和rbt rbt 为左右子树的二叉树为左右子树的二叉树* */ /BiTree p;BiTree p;if (p=(BiTNode if (p=(BiTNode * *)malloc(sizeof(BiTNode)=NULL) )malloc(sizeof(BiTNode)=NULL) return NULL;return NULL;p-data=x;p-data=x;p-lchild=lbt;p-lchild=lbt;p-rchild=rbt;p-rchild=

20、rbt;return p;return p; /算法算法7.27.2二、算法实现BiTree InsertL(BiTree bt,elemtype x,BiTree parent)BiTree InsertL(BiTree bt,elemtype x,BiTree parent)/* *在二叉树在二叉树bt bt 的结点的结点parent parent 的左子树插入结点数据元素的左子树插入结点数据元素x x* */ /BiTree p;BiTree p;if (parent=NULL)if (parent=NULL) printf(n printf(n 插入出错插入出错););return N

21、ULL;return NULL;if (p=(BiTNode if (p=(BiTNode * *)malloc(sizeof(BiTNode)=NULL) return NULL;)malloc(sizeof(BiTNode)=NULL) return NULL;p-data=x;p-data=x;p-lchild=NULL;p-lchild=NULL;p-rchild=NULL;p-rchild=NULL;if (parent-lchild=NULL) parent-lchild=p;if (parent-lchild=NULL) parent-lchild=p;else p-lchild

22、=parent-lchild;else p-lchild=parent-lchild;parent-lchild=p;parent-lchild=p; return bt;return bt; /算法算法7.3 7.3 ，右插入功能类同，略。，右插入功能类同，略。二、算法实现BiTree DeleteL(BiTree bt,BiTree parent)BiTree DeleteL(BiTree bt,BiTree parent)/* *在二叉树在二叉树bt bt 中删除结点中删除结点parent parent 的左子树的左子树* */ /BiTree p;BiTree p;if (parent

23、=NULL|parent-lchild=NULL)if (parent=NULL|parent-lchild=NULL) printf(n printf(n 删除出错删除出错););return NULL;return NULL; p=parent-lchild;p=parent-lchild;parent-lchild=NULL;parent-lchild=NULL;free(p); /free(p); /* *当当p p 为非叶子结点时为非叶子结点时, ,这样删除仅释放了所删子树根结点的空间这样删除仅释放了所删子树根结点的空间, ,* */ / /* *若要删除子树分支中的结点若要删除子树

24、分支中的结点, ,需用后面介绍的遍历操作来实现。需用后面介绍的遍历操作来实现。* */ /return bt;return bt; /算法算法7.47.4二叉树的遍历二叉树的遍历什么是遍历？什么是遍历？按照某一顺序，访问数据结构中的按照某一顺序，访问数据结构中的所有结点所有结点，使每个结点都被使每个结点都被访问一次访问一次，而且，而且只访问一次只访问一次。7.5 二叉树的遍历方法及递归实现也叫也叫“周游周游”二叉树的遍历二叉树的遍历为什么要遍历？为什么要遍历？它是插入、删除、修改、查找和排序运算的前它是插入、删除、修改、查找和排序运算的前提，是二叉树一切运算的基础。提，是二叉树一切运算的基础。

25、7.5 二叉树的遍历方法及递归实现“遍历遍历”曾经很简单曾经很简单7.5 二叉树的遍历方法及递归实现 a a1 1 a a2 2 a an n .H H“遍历遍历”也可以很复杂也可以很复杂7.5 二叉树的遍历方法及递归实现V0V1V2V4V3V5V7V8V6历史上的历史上的“遍历遍历”问题问题-柯尼斯堡七桥问题柯尼斯堡七桥问题7.5 二叉树的遍历方法及递归实现7.5 二叉树的遍历方法及递归实现历史上的历史上的“遍历遍历”问题问题-柯尼斯堡七桥问题柯尼斯堡七桥问题7.5 二叉树的遍历方法及递归实现图论和拓扑学均由此问题发展而来图论和拓扑学均由此问题发展而来7.5 二叉树的遍历方法及递归实现图论和

26、拓扑学均由此问题发展而来图论和拓扑学均由此问题发展而来计算机网络拓扑计算机网络拓扑怎样遍历一棵二叉树怎样遍历一棵二叉树-规定一个顺序规定一个顺序根据定义：非空二叉树由根据定义：非空二叉树由根根、左子树左子树、右子树构成右子树构成只需要按顺序进行以下三个操作：只需要按顺序进行以下三个操作：访问根节点（访问根节点（D）遍历左子树（遍历左子树（L）遍历右子树（遍历右子树（R）7.5 二叉树的遍历方法及递归实现ABCDE怎样遍历一棵二叉树怎样遍历一棵二叉树-规定一个顺序规定一个顺序D、L、R的组合定义了几种可能的遍历方案呢？的组合定义了几种可能的遍历方案呢？LDR、LRD、DLR、DRL、RLD、RD

27、L若限定先左后右，则有三种实现方案：若限定先左后右，则有三种实现方案：7.5 二叉树的遍历方法及递归实现D DLRLRL LD DR RL LR RD D 先先序遍历序遍历 中中序遍历序遍历 后后序遍历序遍历怎样遍历一棵二叉树怎样遍历一棵二叉树-规定一个顺序规定一个顺序7.5 二叉树的遍历方法及递归实现D DLRLRL LD DR RL LR RD D 先先序遍历序遍历 中中序遍历序遍历 后后序遍历序遍历三种方式的步骤是什么三种方式的步骤是什么？（1 1）访问根结点；）访问根结点；（2 2）先序遍历根结点的左子树；）先序遍历根结点的左子树；（3 3）先序遍历根结点的右子树。）先序遍历根结点的右

28、子树。（1 1）中序遍历根结点的左子树；）中序遍历根结点的左子树；（2 2）访问根结点；）访问根结点；（3 3）中序遍历根结点的右子树。）中序遍历根结点的右子树。（1 1）后序遍历根结点的左子树；）后序遍历根结点的左子树；（2 2）后序遍历根结点的右子树。）后序遍历根结点的右子树。（3 3）访问根结点；）访问根结点；例例7.5.1 7.5 二叉树的遍历方法及递归实现先序遍历：先序遍历：根节点根节点左子树左子树右子树右子树ABCDEA AB D EB D E E E例例7.5.1 7.5 二叉树的遍历方法及递归实现中序遍历：中序遍历：根节点根节点左子树左子树右子树右子树ABCDEA AD B E

29、D B E C C例例7.5.1 7.5 二叉树的遍历方法及递归实现后序遍历：后序遍历：根节点根节点左子树左子树右子树右子树ABCDEA AD E BD E B C C例例7.5.2 7.5 二叉树的遍历方法及递归实现中序遍历、先序遍中序遍历、先序遍历、后序遍历分别历、后序遍历分别是什么样的序列？是什么样的序列？a + b a + b * * c - d - e c - d - e / f/ f- + a - + a * * b - c d / b - c d / e fe fa b c d - a b c d - * * + e f + e f / -/ -先先序遍历二叉树的递归算法如下：序

30、遍历二叉树的递归算法如下：7.5 二叉树的遍历方法及递归实现void PreOrder(BiTree bt)void PreOrder(BiTree bt)/* *先序遍历二叉树先序遍历二叉树btbt* */ /if (bt=NULL) return; /if (bt=NULL) return; /* *递归调用的结束条件递归调用的结束条件* */ /Visit(bt); /Visit(bt); /* *访问结点的数据域访问结点的数据域* */ /PreOrder(bt-lchild); /PreOrder(bt-lchild); /* *先序递归遍历先序递归遍历bt bt 的左子树的左子树*

31、 */ /PreOrder(bt-rchild); /PreOrder(bt-rchild); /* *先序递归遍历先序递归遍历bt bt 的右子树的右子树* */ / 中中序遍历二叉树的递归算法如下：序遍历二叉树的递归算法如下：7.5 二叉树的遍历方法及递归实现void InOrder(BiTree bt)void InOrder(BiTree bt)/* *中序遍历二叉树中序遍历二叉树btbt* */ /if (bt=NULL) return; /if (bt=NULL) return; /* *递归调用的结束条件递归调用的结束条件* */ /InOrder(bt-lchild); /In

32、Order(bt-lchild); /* *中序递归遍历中序递归遍历bt bt 的左子树的左子树* */ /Visit(bt); /Visit(bt); /* *访问结点的数据域访问结点的数据域* */ /InOrder(bt-rchild); /InOrder(bt-rchild); /* *中序递归遍历中序递归遍历bt bt 的右子树的右子树* */ / 中序遍历二叉树的递归算法如下：中序遍历二叉树的递归算法如下：7.5 二叉树的遍历方法及递归实现void PostOrder(BiTree bt)void PostOrder(BiTree bt)/* *后序遍历二叉树后序遍历二叉树btbt

33、* */ /if (bt=NULL) return; /if (bt=NULL) return; /* *递归调用的结束条件递归调用的结束条件* */ /PostOrder(bt-lchild); /PostOrder(bt-lchild); /* *后序递归遍历后序递归遍历bt bt 的左子树的左子树* */ /PostOrder(bt-rchild); /PostOrder(bt-rchild); /* *后序递归遍历后序递归遍历bt bt 的右子树的右子树* */ /Visit(bt); /Visit(bt); /* *访问结点的数据域访问结点的数据域* */ / 7.5 二叉树的遍历方

34、法及递归实现int main(void) BiTree bt,lt,rt;lt=Create(E,NULL,NULL);rt=Create(F,NULL,NULL);rt=Create(C,lt,rt); lt=Create(G,NULL,NULL);lt=Create(D,NULL,lt);lt=Create(B,lt,NULL);bt=Create(A,lt,rt); printf(先序遍历：先序遍历：); PreOrder(bt);printf(n);printf(中序遍历：中序遍历：); InOrder(bt);printf(n);printf(后序遍历：后序遍历：); PostOrd

35、er(bt);printf(n);return 0;层次遍历层次遍历所谓二叉树的层次遍历，是指从二叉树的第一所谓二叉树的层次遍历，是指从二叉树的第一层（根结点）开始，层（根结点）开始，从上至下从上至下逐层遍历逐层遍历，在，在同一层中同一层中，则，则按按从左到右从左到右的顺序对结点的顺序对结点逐个访问逐个访问。7.5 二叉树的遍历方法及递归实现ABCDEA AB CB CD ED E层次遍历层次遍历-算法实现思路算法实现思路可设置一个队列结构，遍历从二叉树的根结点开始，首先将根可设置一个队列结构，遍历从二叉树的根结点开始，首先将根结点指针入队列，然后从对头取出一个元素，每取一个元素，结点指针入队

36、列，然后从对头取出一个元素，每取一个元素，执行下面两个操作：执行下面两个操作：（1）访问该元素所指结点；）访问该元素所指结点；（2）若该元素所指结点的左、右孩子结点非空，则将）若该元素所指结点的左、右孩子结点非空，则将该元素所指结点的左孩子指针和右孩子指针顺序入队。该元素所指结点的左孩子指针和右孩子指针顺序入队。7.5 二叉树的遍历方法及递归实现a1 a2 a3 a4 a1 a2 a3 a4 a5a5入队入队出队出队层次遍历层次遍历-算法实现算法实现7.5 二叉树的遍历方法及递归实现void LevelOrder(BiTree bt)void LevelOrder(BiTree bt) BiTree queueMAXSIZENODE; BiTree queueMAXSIZENODE; int front,rear; int front,rear; if(bt=NULL) return; if(bt=NULL) return; front=-1; front=-1; rear=0; rear=0; queuerear=bt; queuerear=bt; 层次遍历层次遍历-算法实现算法实现7.5 二叉树的遍历方法及递归实现 while(front!=rear) while(front!=