数据结构--二叉树

《数据结构与算法》

廊坊师范学院数学与信息科学学院第五章二叉树★★★★★树型结构--实例:五子棋DEFBCA…...........…...........第五章二叉树本章重点难点

重点：二叉树的定义，性质，存储结构以及相关的应用——遍历，二叉搜索树，堆优先队列，Huffman树等

难点：二叉树的遍历算法及相关应用5.1二叉树的概念●二叉树递归定义：

由n(n>=0)个结点的有限集合，或为空集，或由一个根结点及两棵互不相交的左右子树组成，并且左右子树都是二叉树。●二叉树的五种基本形态：空仅有根右子树为空左子树为空左右均非空5.1二叉树的概念

相关概念根：二叉树中唯一的起始结点父结点：非根结点的前驱结点孩子结点：二叉树中，任何结点的后继结点（左孩子，右孩子）兄弟结点：父结点相同的结点叶子结点：没有子结点的结点内部结点：除叶子结点以外的非终端结点BDFEGCAABDFEGCA根BDA5.1二叉树的概念

相关概念

度：一个结点的子树数目

边：父结点结点和子结点之间的连线

路径：从一个结点到另外一个结点的边的集合，边的个数称为路径的长度

层数：从根结点到某个结点的路径长度称为结点的层数BDFEGCA二叉树的度最多为20层1层2层3层5.1二叉树的概念

两种特殊形态的二叉树---满二叉树，完全二叉树BDFEGCA

满二叉树：所有层数的结点都达到最大值的二叉树（与书中不同）1231145891213671014155.1二叉树的概念

两种特殊形态的二叉树---满二叉树，完全二叉树BDFEGCA

满二叉树：除最后一层外，每一层上的所有结点都有两个子结点

1231145891213671014155.1二叉树的概念

两种特殊形态的二叉树---满二叉树，完全二叉树

完全二叉树：树中所含的n个结点和满二叉树中编号为1--n的结点一一对应1234567满二叉树12345完全二叉树5.1二叉树的概念

两种特殊形态的二叉树---满二叉树，完全二叉树

完全二叉树：树中所含的n个结点和满二叉树中编号为1--n的结点一一对应1234567满二叉树12345完全二叉树5.1二叉树的概念

两种特殊形态的二叉树---满二叉树，完全二叉树12345完全二叉树

完全二叉树特点：

只有最下面两层的结点度数小于2

最下面一层的结点都集中在该层最左边连续的位置上5.1二叉树的概念

第三种特殊的二叉树---正则二叉树正则二叉树

正则二叉树：若二叉树的所有结点，或者是树叶，或者左右子树均非空，即除了叶子结点就是度为2的结点12345675.1二叉树的概念●二叉树的主要性质

●性质1：二叉树中第i层上最多有2i个结点0层1层2层BDFEGCA3层HGJILKNM数学归纳法证明：1.当i=0时：成立2.假设所有的j(0<j<i)层都成立3.j=i时也成立i-1层:2i-1i层：2×2i-1

=

2i

5.1二叉树的概念●二叉树的主要性质

●性质2：深度为k的二叉树，至多有2k+1-1个结点深度：二叉树中层数最大的叶结点的层数0层1层2层BDFEGCA3层HGJILKNM1+2+4+8+…..2k等比数列的求和公式：

a1-an*q1-2k*21-q1-22k+1-1==证明：由性质1可知：第i层的最大结点数为2i，因此：

∑2i=2k+1-1ki=05.1二叉树的概念●二叉树的主要性质

●性质3：任何一棵二叉树，若其终端结点数为n0，度为2的结点数为n2，则n0=n2+1BDFGCAG证明：(1)总结点数为

n=n0+n1+n2(2)除根结点外，每个结点都有一个边e进入

n=e+1(3)边e又是由度为1或2的点射出，因此

e=n1+2n2(4)由（2）（3）

n=n1+2n2+1(5)由（4）-（1）可得

n0=n2+15.1二叉树的概念●二叉树的主要性质

●性质3：任何一棵二叉树，若其终端结点数为n0，度为2的结点数为n2，则n0=n2+1BDFGCAG证明：(1)总结点数为

n=n0+n1+n2(2)除根结点外，每个结点都有一个边e进入

n=e+1(3)边e又是由度为1或2的点射出，因此

e=n1+2n2(4)由（2）（3）

n=n1+2n2+1(5)由（4）-（1）可得

n0=n2+15.1二叉树的概念●二叉树的主要性质

●性质3：任何一棵二叉树，若其终端结点数为n0，度为2的结点数为n2，则n0=n2+1BDFGCAG证明：(1)总结点数为

n=n0+n1+n2(2)除根结点外，每个结点都有一个边e进入

n=e+1(3)边e又是由度为1或2的点射出，因此

e=n1+2n2(4)由（2）（3）

n=n1+2n2+1(5)由（4）-（1）可得

n0=n2+15.1二叉树的概念●二叉树的主要性质

●性质3：任何一棵二叉树，若其终端结点数为n0，度为2的结点数为n2，则n0=n2+1BDFGCAG证明：(1)总结点数为

n=n0+n1+n2(2)除根结点外，每个结点都有一个边e进入

n=e+1(3)边e又是由度为1或2的点射出，因此

e=n1+2n2(4)由（2）（3）

n=n1+2n2+1(5)由（4）-（1）可得

n0=n2+15.1二叉树的概念●二叉树的主要性质

●性质3：任何一棵二叉树，若其终端结点数为n0，度为2的结点数为n2，则n0=n2+1BDFGCAG证明：(1)总结点数为

n=n0+n1+n2(2)除根结点外，每个结点都有一个边e进入

n=e+1(3)边e又是由度为1或2的点射出，因此

e=n1+2n2(4)由（2）（3）

n=n1+2n2+1(5)由（4）-（1）可得

n0=n2+15.1二叉树的概念●二叉树的主要性质

●性质4：正则二叉树定理：非空正则二叉树树叶数目等于其分支结点数加1证明：可由性质3直接推出性质3：n0=n2+1BDFEGCA5.1二叉树的概念●二叉树的主要性质

●性质5：正则二叉树定理推论：一个非空二叉树的空子树数目等于其结点数加1证明：由性质4可推出BDGCAFE5.1二叉树的概念●二叉树的主要性质

●性质6：有n(n>0)个结点的完全二叉树的高度为「log2(n+1),深度为「log2(n+1)-1

高度:二叉树中最大叶结点的层数+1123450层1层2层高度=3,深度=2证明：由性质2（深度为k的二叉树，至多有2k+1-1个结点）可知，高度为h(k+1)的二叉树，其结点个数n满足：

2h-1-1<n<=2h-12h-1<n+1<=2h取对数得到：

h-1<log2(n+1)<=h因为h是整数，所以

h=log2(n+1)

上取整：大于该数的最小整数3.4->45.1二叉树的概念●二叉树的主要性质

●性质7：具有n个结点的完全二叉树，结点按层次由左到右编号，则对任一结点i（0<=i<=n-1)有：（2）2i+1<=n-1i的左孩子结点是2i+12i+2<=n-1i的右孩子结点是2i+2（1）i=0i是根结点

i>0其父结点=（i-1）/2（3）0<i<ni为偶数时，其左兄弟结点是i-1i+1<ni为奇数时，其右兄弟结点是i+101234562k-22i+22k-1i

2k+1-12k+12i+32i+4i+12k+1-22i+12k+2-32k+2-2K-1层K层K+1层………..………..………..………..5.2二叉树的遍历（周游）●二叉树遍历：

按照一定的顺序依次访问树中的所有结点，并使得每个结点仅被访问一次。

遍历的目的：初始化一棵二叉树在树中查找具有某种特征的结点对树中全部结点逐一进行某种处理。5.2二叉树的遍历（周游）遍历分类：深度优先：尽可能沿分支结点向深度方向遍历广度优先：按二叉树的层次进行遍历

BDFGCAGTLR—先（根）序遍历，LTR—中（根）序遍历，LRT—后（根）序遍历。寻找遍历二叉树的规律二叉树基本组成单元：根结点T、左子树Ｌ和右子树Ｒ。遍历二叉树有TLR、LTR、LRT、TRL、RTL、RLT六种方案。规定先左后右，则只有三种：T左子树右子树根结点5.2二叉树的遍历（周游）深度优先遍历：DLR—先（根）序遍历5.2二叉树的遍历（周游）深度优先遍历：

（1）访问根结点；

（2）先序遍历左子树；

（3）

先序遍历右子树；ADBCDLRADLRDLR>B>>D>>CDLR先序遍历序列：ABDC先序遍历:ADBCLDRBLDRLDR>A>>D>>CLDR中序遍历序列：BDAC中序遍历:ADBCLRDLRDLRD>A>>D>>CLRD后序遍历序列：DBCA后序遍历:B第五章二叉树内容回顾二叉树的概念空仅有根右子树为空左子树为空左右均非空二叉树的性质满二叉树，完全二叉树，正则二叉树0256134满二叉树完全二叉树0213正则二叉树02341第五章二叉树内容回顾二叉树的概念二叉树的性质满二叉树，完全二叉树，正则二叉树012103478111256913140层1层2层3层2i2i+1-1n0=n2+1....「log2(n+1)2i+1;2i+2第五章二叉树内容回顾二叉树的概念二叉树的性质满二叉树，完全二叉树，正则二叉树二叉树的遍历深度优先广度优先BDFGCAG根二叉树的深度优先遍历根：root左子树：left右子树：rightTLRTLR—先（根）序遍历LTR—中（根）序遍历LRT—后（根）序遍历规定遍历顺序自左至右：创建、复制一棵二叉树遍历一棵二叉搜索树可以得到有序序列求树的高度，叶结点的数量BDFEGCA先序序列：二叉树的遍历练习ABCDEGFBDFEGCA先序序列：二叉树的遍历练习ABCDEGFBDFEGCA先序序列：二叉树的遍历练习ABCDEGFBDFEGCA先序序列：二叉树的遍历练习ABCDEGFBDFEGCA先序序列：二叉树的遍历练习ABCDEGFBDFEGCA先序序列：二叉树的遍历练习ABCDEGFBDFEGCA先序序列：二叉树的遍历练习ABCDEGFBDFEGCA先序序列：二叉树的遍历练习ABCDEGFBDFEGCA先序序列：二叉树的遍历练习ABCDEGF中序序列：CBEGDFABDFEGCA先序序列：二叉树的遍历练习ABCDEGF中序序列：CBEGDFABDFEGCA先序序列：二叉树的遍历练习ABCDEGF中序序列：CBEGDFABDFEGCA先序序列：二叉树的遍历练习ABCDEGF中序序列：CBEGDFABDFEGCA先序序列：二叉树的遍历练习ABCDEGF中序序列：CBEGDFABDFEGCA先序序列：二叉树的遍历练习ABCDEGF中序序列：CBEGDFABDFEGCA先序序列：二叉树的遍历练习ABCDEGF中序序列：CBEGDFABDFEGCA先序序列：二叉树的遍历练习ABCDEGF中序序列：CBEGDFABDFEGCA先序序列：二叉树的遍历练习ABCDEGF中序序列：CBEGDFA后序序列：CGEFDBABDFEGCA先序序列：二叉树的遍历练习ABCDEGF中序序列：CBEGDFA后序序列：CGEFDBABDFEGCA先序序列：二叉树的遍历练习ABCDEGF中序序列：CBEGDFA后序序列：CGEFDBABDFEGCA先序序列：二叉树的遍历练习ABCDEGF中序序列：CBEGDFA后序序列：CGEFDBABDFEGCA先序序列：二叉树的遍历练习ABCDEGF中序序列：CBEGDFA后序序列：CGEFDBABDFEGCA先序序列：二叉树的遍历练习ABCDEGF中序序列：CBEGDFA后序序列：CGEFDBABDFEGCA先序序列：二叉树的遍历练习ABCDEGF中序序列：CBEGDFA后序序列：CGEFDBABDFEGCA先序序列：二叉树的遍历练习ABCDEGF中序序列：CBEGDFA后序序列：CGEFDBA5.2二叉树的遍历（周游）广度优先遍历：BDFEGCA广度优先遍历序列：

ABCDEFG内存使用模拟：1.不同任务的数据申请使用内存2.部分程序结束，此时内存可用空间已经呈不连续状态5.3二叉树的存储结构数据的物理存储结构：连续存储：占用一片连续的存储区域优点：随机读取，存储密度大缺点：插入和删除元素费时，不适合存储数据量无法预知的数据5.3二叉树的存储结构数据的物理存储结构：连续存储：占用一片连续的存储区域优点：随机读取，存储密度大缺点：插入和删除元素费时，不适合存储数据量无法预知的数据5.3二叉树的存储结构数据的物理存储结构：连续存储：占用一片连续的存储区域优点：随机读取，存储密度大缺点：插入和删除元素费时，不适合存储数据量无法预知的数据5.3二叉树的存储结构数据的物理存储结构：

链式存储：使用不连续的存储区域，使用附加的指针信息，体现其逻辑关系优点：适于动态变化的数据结构缺点：随机查找困难，存储密度小5.3二叉树的存储结构数据域指针域数据的物理存储结构：

链式存储：使用不连续的存储区域，使用附加的指针信息，体现其逻辑关系优点：适于动态变化的数据结构缺点：随机查找困难，存储密度小5.3二叉树的存储结构5.3二叉树的存储结构二叉树的顺序存储结构：

用一组地址连续的存储单元，依次按满二叉树的结点编号位序，存储二叉树的结点。特点：适用于完全二叉树。否则可能对存储空间造成极大的浪费，比如单支树。abcdefg5.3二叉树的存储结构顺序存储结构：完全二叉树0a1b2c3d4e5f6g1234560顺序方式是完全二叉树存储的最简单，最节省空间的方式abcdefg5.3二叉树的存储结构顺序存储结构：非完全二叉树abcgg‘/’‘/’‘/’cba1234560非完全二叉树顺序存储时，会浪费一定的空间3’/’4’/’5’/’0a1b2c6g5.3二叉树的存储结构链式存储结构：二叉链表：从任何一个结点都可找到其左右孩子结点lChilddata0rChildlChilddata1rChildlChilddata2rChildRoot缺点：很难获取某个结点的父结点5.3二叉树的存储结构链式存储结构：三叉链表：从任何一个结点都可找到其父结点和左右孩子结点lChildparentdatarChildlChildparentdatarChildlChildparentdatarChildnullRoot5.3二叉树的存储结构链式存储结构的程序实现：结点类定义：//树结点类的定义template<classT>classTreeNode{public：

Tdata;TreeNode*lchild;//左，右子树

TreeNode*rchild;public:TreeNode(){ lchild=NULL; rchild=NULL;}};lChilddata0rChild5.3二叉树的存储结构链式存储结构的程序实现：二叉树类定义：//树类的定义template<classT>classBinTree{private: TreeNode<T>*root;//树的根结点public: BinTree() { root=NULL; } ~BinTree() { Destroy(root); }rootnull5.3二叉树的存储结构链式存储结构的程序实现：二叉树类定义：//树类的定义template<classT>classBinTree{private: TreeNode<T>*root;//树的根结点public: BinTree() { root=NULL; } ~BinTree() { Destroy(root); }BDCAroot//***************创建二叉树,主过程

voidCreatTree(){

cout<<"请按前序遍历输入结点元素值，空节点用/代替:"<<endl; CreatTree(root);}//***************创建二叉树,子过程voidCreatTree(TreeNode<T>*&p1){Tc; cin>>c; TreeNode<T>*point;point=newTreeNode<T>; if(c!='/') { p1=point;point->data=c;CreatTree(point->lchild);CreatTree(point->rchild); }}创建二叉树BDCAroot‘/’‘/’‘/’‘/’‘/’

//先序遍历二叉树

voidPreTree(){ PreTree(root);}voidPreTree(TreeNode<T>*point){ if(point!=NULL) { cout<<""<<point->data;PreTree(point->lchild);PreTree(point->rchild); }}BDCAroot‘/’‘/’‘/’‘/’‘/’

//先序遍历二叉树

voidPreTree(){ PreTree(root);}voidPreTree(TreeNode<T>*point){ if(point!=NULL) { cout<<""<<point->data;PreTree(point->lchild);PreTree(point->rchild); }}BDCAroot‘/’‘/’‘/’‘/’‘/’//中序遍历二叉树voidInoTree(){ InoTree(root);}voidInoTree(TreeNode<T>*point){

if(point!=NULL)

{

InoTree(point->lchild);

cout<<""<<point->data;

InoTree(point->rchild);

}}BDCAroot‘/’‘/’‘/’‘/’‘/’//后序遍历二叉树

voidPosTree(){ PosTree(root);}voidPosTree(TreeNode<T>*point){if(point!=NULL){PosTree(point->lchild);

PosTree(point->rchild);cout<<""<<point->data;}}BDCAroot‘/’‘/’‘/’‘/’‘/’#include<iostream>#include"BinTree.h"usingnamespacestd;//主函数voidmain(){BinTree<char>BinTreeOPP;BinTreeOPP.CreatTree();cout<<"先序："<<endl;BinTreeOPP.PreTree();cout<<endl;cout<<"中序："<<endl;BinTreeOPP.InoTree();cout<<endl;cout<<"后序："<<endl;BinTreeOPP.levelorder();cout<<endl;}BDCAroot‘/’‘/’‘/’‘/’‘/’《数据结构与算法》

廊坊师范学院数学与信息科学学院授课教师：崔业勤第五章二叉树★★★★★根二叉树的遍历TLRTLR—先（根）序遍历LTR—中（根）序遍历LRT—后（根）序遍历规定遍历顺序自左至右：内容回顾根二叉树的遍历TLRTLR—先（根）序遍历LTR—中（根）序遍历LRT—后（根）序遍历规定遍历顺序自左至右：内容回顾根LR二叉树的遍历TLR—先（根）序遍历规定遍历顺序自左至右：根TL根LRBDFECALTR—中（根）序遍历LRT—后（根）序遍历ABDEFCBEDFACEFDBCA中序遍历一棵二叉搜索树可以得到所有结点的有序序列二叉搜索树的用途：快速查找特定的元素5.4二叉搜索树构造二叉树搜索的过程就是给数据排序的过程，中序遍历可得到有序序列二分法思想二叉搜索树：其内部结点的左子树上所有结点的值，均小于它的根结点，右子树上所有结点的值，均大于它的根结点35403878942356515.4二叉搜索树构造二叉搜索树：从二叉树的根结点开始创建比根节点小的值作为左子树的根，比根结点大的值作为右子树的根重复值不允许插入56,34,78,4,7,98,64563478479864练习5.4二叉搜索树二叉搜索树插入结点：（同创建）25二叉搜索树删除结点：若该结点无左子树，则直接用该结点的右子树的根代替该结点56347847986470765.4二叉搜索树二叉搜索树插入结点：（同创建）56347849864725二叉搜索树删除结点：若该结点无左子树，则直接用该结点的右子树的根代替该结点4若该结点有左子树，则在左子树中找到最大的结点代替它70765.4二叉搜索树二叉搜索树插入结点：（同创建）56347849864725二叉搜索树删除结点：若该结点无左子树，则直接用该结点的右子树的根代替该结点4若该结点有左子树，则在左子树中找到最大的结点代替它707856765.4二叉搜索树二叉搜索树插入结点：（同创建）56347849864725二叉搜索树删除结点：若该结点无左子树，则直接用该结点的右子树的根代替该结点4若该结点有左子树，则在左子树中找到最大的结点代替它70785676左子树中的最大结点：1.该子树中没有右子树，根既是最大2.该子树中有右子树，则顺着右子树分支找到的最后一个结点为最大5.4二叉搜索树3422789864736删除结点练习：6146992278687263365.4二叉搜索树二叉搜索树特点：是一种插入，删除，检索效率都较高的数据组织方法123456788490939901234567线性顺序结构：检索快，插入删除效率低同其它数据组织方法的比较：

线性链式结构：插入删除快，检索效率低3456788490939912堆的用途：

在一组数据中快速查找最大值或最小值堆：是一种特殊的完全二叉树，其内部结点的值均不大于（或小于）其左右结点的值5.5堆与优先队列42345345767899958最小堆9823451418339911最大堆

局部有序士兵1士兵3********公主***士兵2谁先救走了公主？构造最小堆：按层次结构放置各个元素，构造一棵完全二叉树从最后一个非终端结点即无序序列中第

n/2

个元素开始，将该结点的左右子结点中较小的值与该结点互换位置。依次调整到根结点，在调整过程中，要注意维持最小堆的特性5.5堆与优先队列98234514183399119823451418339911构造最小堆：按层次结构放置各个元素，构造一棵完全二叉树从最后一个非终端结点即无序序列中第

n/2

个元素开始，将该结点的左右子结点中较小的值与该结点互换位置。依次调整到根结点，在调整过程中，要注意维持最小堆的特性5.5堆与优先队列98234514183399119823451418339911构造最小堆：按层次结构放置各个元素，构造一棵完全二叉树从最后一个非终端结点即无序序列中第

n/2

个元素开始，将该结点的左右子结点中较小的值与该结点互换位置。依次调整到根结点，在调整过程中，要注意维持最小堆的特性5.5堆与优先队列98234514183399119823451418339911构造最小堆：按层次结构放置各个元素，构造一棵完全二叉树从最后一个非终端结点即无序序列中第

n/2

个元素开始，将该结点的左右子结点中较小的值与该结点互换位置。依次调整到根结点，在调整过程中，要注意维持最小堆的特性5.5堆与优先队列98234514183399119823451418339911构造最小堆：按层次结构放置各个元素，构造一棵完全二叉树从最后一个非终端结点即无序序列中第

n/2

个元素开始，将该结点的左右子结点中较小的值与该结点互换位置。依次调整到根结点，在调整过程中，要注意维持最小堆的特性5.5堆与优先队列98234514183399119823451418339911构造最小堆：按层次结构放置各个元素，构造一棵完全二叉树从最后一个非终端结点即无序序列中第

n/2

个元素开始，将该结点的左右子结点中较小的值与该结点互换位置。依次调整到根结点，在调整过程中，要注意维持最小堆的特性5.5堆与优先队列98234514183399119823451418339911构造最小堆：按层次结构放置各个元素，构造一棵完全二叉树从最后一个非终端结点即无序序列中第

n/2

个元素开始，将该结点的左右子结点中较小的值与该结点互换位置。依次调整到根结点，在调整过程中，要注意维持最小堆的特性5.5堆与优先队列98234514183399119823451418339911堆插入结点：先将该元素排列到最后按堆性质调整元素到合适位置5.5堆与优先队列98234514183399116堆插入结点：先将该元素排列到最后按堆性质调整元素到合适位置5.5堆与优先队列98234514183399116堆插入结点：先将该元素排列到最后按堆性质调整元素到合适位置5.5堆与优先队列98234514183399116堆插入结点：先将该元素排列到最后按堆性质调整元素到合适位置5.5堆与优先队列98234514183399116堆删除结点：先将最后一个元素调整到删除元素位置按堆性质依次向下调整堆插入结点：先将该元素排列到最后按堆性质调整元素到合适位置5.5堆与优先队列982345143399116堆删除结点：先将最后一个元素调整到删除元素位置按堆性质依次向下调整18堆插入结点：先将该元素排列到最后按堆性质调整元素到合适位置5.5堆与优先队列98234514339911堆删除结点：先将最后一个元素调整到删除元素位置按堆性质依次向下调整18堆练习：5.5堆与优先队列18214724191339451845139194732124构造最小堆3451824191347921插入结点4堆练习：5.5堆与优先队列1821472419133945构造最小堆3451824191347921插入结点434518249134742119//创建二叉搜索树voidcreatbst(){creatbst(root);}voidcreatbst(TreeNode<T>*&root){ Tn; cin>>n;TreeNode<T>*point=root;TreeNode<T>*newpoint; newpoint=newTreeNode<T>; newpoint->data=n; if(root==NULL) { root=newpoint;return；} while(point!=NULL){//关键字相同的元素不予处理 if(newpoint->data==point->data)

return; elseif(newpoint->data<point->data){

if(point->lchild==NULL){

point->lchild=newpoint;

return;