1、q一个二叉树一个二叉树是是n（n0）个结点的有限集，）个结点的有限集，特点是特点是每每个结点至多有两棵子树，即每个结点至多有两个孩个结点至多有两棵子树，即每个结点至多有两个孩子结点，且子结点，且每个孩子结点都有各自的位置关系每个孩子结点都有各自的位置关系。二叉树二叉树或者为空（或者为空（n=0），或者是由一个，或者是由一个根结点根结点及两棵互不相交的、分别称为及两棵互不相交的、分别称为左子树左子树和和右子右子树树的的二叉树二叉树组成。组成。(递归定义递归定义)q由上述定义可知，由上述定义可知，二叉树二叉树可以是空集，其可以是空集，其根根可以有可以有空的左子树或右子树，或者左、右子树皆为空。空的
2、左子树或右子树，或者左、右子树皆为空。5.2 二叉树的定义和性质二叉树的定义和性质 5.2.1 二叉树的定义二叉树的定义1234567123456满二叉树满二叉树q在一个二叉树中，若第在一个二叉树中，若第i层的结点数为层的结点数为2i-1，则称则称此层的结点数是满的此层的结点数是满的，当树中的每一，当树中的每一层都是满的，则称此二叉树为层都是满的，则称此二叉树为满二叉树满二叉树。q即如果一个二叉树中，即如果一个二叉树中，除最下一层的各结除最下一层的各结点点度数为度数为0以外，以外，其它各层结点其它各层结点的的度数均等度数均等于于2，则此二叉树为满二叉树。，则此二叉树为满二叉树。q满二叉树满二叉
3、树每一层的结点数都是上一层结点每一层的结点数都是上一层结点数的二倍。数的二倍。所以，在满二叉树的第所以，在满二叉树的第i层共有层共有2i-1个结点（个结点（i1），），一个深度为一个深度为h的满二叉的满二叉树的结点总数为树的结点总数为2h-1。123114589121367101415完全二叉树完全二叉树q如果一个二叉树各层都是如果一个二叉树各层都是“满满”的，只是的，只是最底层最底层从右边起连续缺从右边起连续缺n个结点，这种二叉树叫做个结点，这种二叉树叫做完全完全二叉树二叉树。q例如下图：例如下图：特点特点：n前前k-1层是满二叉树，第层是满二叉树，第k层结点层结点靠左对齐靠左对齐；n叶子叶
4、子结点只可能在结点只可能在层次最大的两层层次最大的两层上出现；上出现；n满二叉树满二叉树必为必为完全二叉树完全二叉树，而完全二叉树不而完全二叉树不一定是满二叉树。满二叉树是完全二叉树的一一定是满二叉树。满二叉树是完全二叉树的一个特例。个特例。123114589126710性质性质1：在二叉树的第在二叉树的第i层层(i 1)上至多有上至多有_ _ 个结点。个结点。12 i5.2.2 二叉树的性质与结论二叉树的性质与结论 证明：证明：用用归纳法归纳法证明之证明之 i=1i=1时，只有一个根结点，时，只有一个根结点，是对的是对的 假设对所有假设对所有j(1j(1ji)j1，则其双亲是则其双亲是 i/
5、2 (2)其左孩子其左孩子结点编号是结点编号是 2i (1in/2)因为：因为：22in (3)其其右孩子右孩子结点编号是结点编号是 2i+1(1i(n-1)/2)因为：因为：22i+1n123114589126710性质性质6：完全二叉树完全二叉树中中至多至多只有只有一个度为一个度为1的结点：的结点：当结点个数是当结点个数是偶数偶数时，有且仅有一个度为时，有且仅有一个度为1的结点；的结点；当结点个数是当结点个数是奇数奇数时，无度为时，无度为1的结点。的结点。即即n1=(n+1)%2123114589126710奇数个结点奇数个结点偶数个结点偶数个结点偶数个结点偶数个结点奇数个结点奇数个结点思
6、路：关键是求出思路：关键是求出n1+n2证明：证明：(1)当当n为偶数时，由性质为偶数时，由性质6可知，可知，n1=1由性质由性质3可知，可知，n0=n2+1，即，即n0=n2+n1又又n=n0+n1+n2得得：n=2n0 所以：所以：n0=n/2=n/2因为因为n为偶数，所以为偶数，所以n1+n2=n-n0=n-n/2=n/2=n/2 即当即当n为偶数时，编号大于为偶数时，编号大于 n/2 的结点均为叶子结点。的结点均为叶子结点。(2)n为奇数时，由性质为奇数时，由性质6可知，可知，n1=0由性质由性质3可知，可知，n0=n2+1又又n=n0+n1+n2=n0+n2得得：n=2n2+1 所以
7、：所以：n2=(n-1)/2 即：即：n1+n2=(n-1)/2=n/2 即当即当n为奇数时，编号大于为奇数时，编号大于 n/2 的结点的结点均为叶子结点。均为叶子结点。性质性质7：在在完全二叉树完全二叉树中编号大于中编号大于 的结点均为的结点均为叶子结点叶子结点。2/n123114589126710引申：引申：非叶子结点数为非叶子结点数为 。叶子结点数为叶子结点数为n-。2/n2/nq将二叉树上的结点值按将二叉树上的结点值按从上到下、从左到右从上到下、从左到右的次序的次序存储到一个存储到一个一维数组一维数组中，这种存储方式称为中，这种存储方式称为二叉树二叉树的顺序存储的顺序存储。ABCDEF
8、G二叉树中各个结点之间的逻辑关系二叉树中各个结点之间的逻辑关系(层次关系层次关系)如何表示？如何表示？q若存储结构不能反映结点间的逻辑关系，那么二叉若存储结构不能反映结点间的逻辑关系，那么二叉树上的树上的各种基本运算各种基本运算在顺序存储结构上很难实现。在顺序存储结构上很难实现。5.3 二叉树的存储二叉树的存储顺序、链式顺序、链式5.3.1 顺序存储结构顺序存储结构ABCDEFGq对于对于完全二叉树完全二叉树来说，可以采用来说，可以采用“以编号为地址以编号为地址”的方法，将的方法，将编号为编号为i的结点的结点存入存入一维数组的第一维数组的第i个单个单元元。q如下图所示的完全二叉树按此方法存入数
9、组中如下如下图所示的完全二叉树按此方法存入数组中如下图所示。图所示。q这种存储结构适用于这种存储结构适用于完全二叉树完全二叉树和和满二叉树满二叉树。ABCDEHIFGJ12345678910 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 下标:A:aA 一维数一维数 组组ABCDEFGHIJ图图 非完全二叉树的顺序表示非完全二叉树的顺序表示 A B C E F G D A B D C E G F 1245101121q非完全二叉树：非完全二叉树：增加一些增加一些虚结点虚结点，使之变成，使之变成完全二完全二叉树叉树的树形。的树形。q 如果某二叉树如果某二叉树
10、不是完全二叉树不是完全二叉树，中间有一些结点不存在，则采用顺序存，中间有一些结点不存在，则采用顺序存储结构时，数组中必然要有一些储结构时，数组中必然要有一些空闲空闲单元，对存储空间利用不够。单元，对存储空间利用不够。1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 二叉树顺序存储的实现方式：二叉树顺序存储的实现方式：按按的形式进行存储。的形式进行存储。abcdefg15123465810971114151213a b c d e 0 0 f 0 0 g 0 0 0 0 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
11、 151)增加虚结点补全成满二叉树增加虚结点补全成满二叉树;2)结点按层次编号结点按层次编号;3)按按层次层次存储结点，结点存放存储结点，结点存放到到以其编号为下标以其编号为下标的位置上，的位置上，虚结点虚结点用用特殊标志特殊标志(0)标识。标识。图图 二叉树的二叉树的顺序存储顺序存储4)数组中下标为数组中下标为0的单元：存放的单元：存放满二叉树结点总数满二叉树结点总数或或二叉树的二叉树的深度深度。ABCD(a)单支二叉树(b)单支二叉树的顺序存储结构单支二叉树的顺序存储结构A0 BCD0 0 00 0 0 0 0 0 0150 1 2 3 4 5 6 7 8 9 10 11 12 13 14
12、 15图图 一棵单支二叉树的一棵单支二叉树的顺序存储顺序存储13715例：例：常用的链式存储结构有：常用的链式存储结构有：二叉链表二叉链表（重点）（重点）三叉链表三叉链表（了解）（了解）线索链表线索链表（熟悉）（熟悉）5.3.2 二叉树的链式存储结构二叉树的链式存储结构二叉树的二叉树的链式存储结构链式存储结构：以：以链表链表的形式存储二叉的形式存储二叉树中的结点及其相互之间的关系。树中的结点及其相互之间的关系。1.的存储类型说明的存储类型说明typedef char ElemType;typedef struct Node ElemType data;struct Node *lchild；s
13、truct Node *rchild;BitTree;/*BitTree为二叉树结点类型名为二叉树结点类型名*/例如：例如：BitTree at;/*定义一个二叉链表定义一个二叉链表结点变量结点变量*/BitTree *bt;/*定义一个二叉链表结点定义一个二叉链表结点指针变量指针变量bt，若将其指向二叉链，若将其指向二叉链表表根结点根结点，就可以用，就可以用bt来来标识整个二叉链表标识整个二叉链表*/lchild data rchild 指向左子树指向左子树指向右子树指向右子树是指按是指按一定的规律一定的规律依次访问依次访问二二叉树的每个结点，且每个结点叉树的每个结点，且每个结点只被访问一次
14、只被访问一次的的过程。过程。q对二叉树的遍历过程实际上是将对二叉树的遍历过程实际上是将非线性结构非线性结构的的二叉树中的结点排列成一个二叉树中的结点排列成一个线性序列线性序列的过程。的过程。q对于用对于用顺序结构顺序结构表示的二叉树，各结点在数组表示的二叉树，各结点在数组中的编号很有规律，其遍历较容易进行，但对中的编号很有规律，其遍历较容易进行，但对于用于用链式存储链式存储结构表示的二叉树，进行遍历就结构表示的二叉树，进行遍历就复杂一些。复杂一些。q研究：研究：各种遍历算法的实现及应用各种遍历算法的实现及应用5.4 二叉树的遍历及应用二叉树的遍历及应用5.4.1 二叉树的遍历二叉树的遍历按层次
15、遍历结果按层次遍历结果:A:AB BC CD DE EFGFG特点：特点：“先被访问的父结点的孩子结点先被访问的父结点的孩子结点”先于先于“后被后被访问的父结点的孩子结点访问的父结点的孩子结点”进行访问。进行访问。q 按层次遍历：按层次遍历：从上到下、从左到右访问各结点。从上到下、从左到右访问各结点。思考：思考：实现二叉树的按层次遍历需要借助于实现二叉树的按层次遍历需要借助于_线性结构存储结点。线性结构存储结点。队列队列层次：层次：1 2 3 4A B C D E FGq 一个非空的二叉树一个非空的二叉树由由根结点根结点及及左左、右子树右子树这三个基本部分组这三个基本部分组成，因此若能依次遍历
16、这三部分，便是遍历了整个二叉树。成，因此若能依次遍历这三部分，便是遍历了整个二叉树。q 在在任一给定结点任一给定结点上，可以按某种次序执行上，可以按某种次序执行三个操作三个操作：访问结：访问结点本身点本身(以其为根以其为根)，遍历该结点左子树，遍历该结点右子树。，遍历该结点左子树，遍历该结点右子树。：左、左、根根、右；、右；根根、左、右；左、右、左、右；左、右、根根；右、根、左；根、右、左；右、左、根右、根、左；根、右、左；右、左、根q 由于实际问题一般都是要求由于实际问题一般都是要求左子树较右子树先遍历左子树较右子树先遍历，故只采，故只采用其中、三种遍历次序，分别称为用其中、三种遍历次序，分
17、别称为中序中序(根根)遍历、遍历、先序先序(根根)遍历遍历和和后序后序(根根)遍历遍历。q 二叉树遍历是一个二叉树遍历是一个递归递归过程。过程。q 假设以假设以L、D、R分别表示遍历左子树、分别表示遍历左子树、访问根结点和遍历右子树。访问根结点和遍历右子树。则将上述则将上述3种形式遍历表示为种形式遍历表示为 LDR、DLR、LRD。q 二叉树的遍历过程二叉树的遍历过程(1)先序遍历二叉树先序遍历二叉树(DLR)若二叉树非空，则若二叉树非空，则 访问根结点；访问根结点；先序遍历先序遍历根的左子树；根的左子树；先序遍历先序遍历根的右子树。根的右子树。(2)中序遍历二叉树中序遍历二叉树(LDR)若二
18、叉树非空，则若二叉树非空，则 中序遍历中序遍历根的左子树；根的左子树；访问根结点；访问根结点；中序遍历中序遍历根的右子树。根的右子树。(3)后序遍历二叉树后序遍历二叉树(LRD)若二叉树非空，则若二叉树非空，则 后序遍历后序遍历根的左子树；根的左子树；后序遍历后序遍历根的右子树；根的右子树；访问根结点。访问根结点。q先序遍历二叉树先序遍历二叉树(DLR)q中序遍历二叉树中序遍历二叉树(LDR)q后序遍历二叉树后序遍历二叉树(LRD)q中序遍历序列：中序遍历序列：H，D，I，B，E，A，F，C，Gq先序遍历序列先序遍历序列：A，B，D，H，I，E，C，F，Gq后序遍历序列：后序遍历序列：H，I，
19、D，E，B，F，G，C，A B C D E F G A H I 例例2：写出图示二叉树的中、先、后序遍历序列。写出图示二叉树的中、先、后序遍历序列。例例5.7、5.8、5.9(P120)：1)已知一棵二叉树：已知一棵二叉树：序列序列KAFGIBEDHJC和和序列序列AGFKEDBHJIC，画出这颗二叉树的形状。画出这颗二叉树的形状。KAIBCDEFGHJ2)已知一颗二叉树：已知一颗二叉树：序列序列FBCGIEJDAH和和序列序列BFGCHIEADJ，画出这棵二叉树。画出这棵二叉树。ABCDEFGH IJ3)已知一棵二叉树的已知一棵二叉树的序列序列AB和和序列序列BA，画出这棵二叉树的形状。画出这棵二叉树的形状。答：不唯一答：不唯一ABAB若已知一棵二叉树的若已知一棵二叉树的先先（后后）序序列和）序序列和中中序序列，则这棵二叉树唯一。序序列，则这棵二叉树唯一。30已知二叉树的前序、中序和后序遍历序列如下，其中有一些看不清的字母用X表示，请将每个序列补充完整，(1)前序遍历序列是：XBCBCXXXG GX (2)中序遍历序列是：CBCBXEAGHEAGHX(3)后序遍历序列是：XEDBEDBXXFAFA构造一棵符合条件的二叉树。
