计算机软件基础课件：树和二叉树

树和二叉树BasicsofComputerSoftware答辩人：XXX

目录树的定义与基本概念1二叉树及其性质2二叉树的存储结构3二叉树的遍历45树和森林哈夫曼树及其的应用6二叉排序树及其查找7树的定义与基本概念PART1线性结构的特征：线性结构的特点是数据元素之间存在一对一的线性关系线性结构有两种不同的存储结构，即顺序存储和链式存储。分别称为顺序表和链表，顺序表中的数据元素是连续的，链表中的存储元素不一定是连续的线性结构中存在两种操作受限的使用场景，即队列和栈。栈的插入和删除操作只能在线性表的一端进行，就是我们常说的先进后出（FILO），而队列的插入删除操作分别限定在线性表的两端进行，即先进先出(FIFO)非线性结构的特征：非线性结构中各个数据元素不再保持在一个线性序列中，每个数据元素可能与零个或者多个其他数据元素发生联系。根据关系的不同，可分为层次结构和群结构常见的非线性结构有：多维数组、广义表、树(二叉树等)、图等。（其中多维数组是由多个一维数组组成的，所以不再是线性结构）树的概念和基本术语树的定义：树是有n(n

0)个结点的有限集合。

如果n=0，称为空树；如果n>0，则：

有且仅有一个特定的称之为根(Root)的结点，它只有直接后继，但没有直接前驱；当n>1，除根以外的其它结点划分为m(m>0)个互不相交的有限集T1,T2,…,Tm，其中每个集合本身又是一棵树，并且称为根的子树。ACGBDEFKLHMIJA只有根结点的树ACGBDEFKLHMIJ有13个结点的树其中：A是根其余结点分成三个互不相交的子集T1={B,E,F,K,L}；T2={C,G}；T3={D,H,I,J,M},T1,T2,T3都是根A的子树，且本身也是一棵树空树树根家谱可以用树描述电气学院计算机学院航飞学院土木工程学院经管学院单位的组织结构软件的模块结构树的基本术语1层2层4层3层height=4ACGBDEFKLHMIJ结点结点的度树的度叶子结点分支结点孩子双亲祖先子孙兄弟结点层次堂兄弟树的深度树的度有序树和无序树森林1、结点(Node)：表示树中的数据元素，由数据项和数据元素之间的关系组成。在图中，共有13个结点。2、结点的度(DegreeofNode)：结点所拥有的子树的个数，在图中，结点A的度为3。3、树的度(DegreeofTree)：树中各结点度的最大值。在图5.1中，树的度为3。4、叶子结点(LeafNode)：度为0的结点，也叫终端结点。结点K、L、F、G、M、I、J都是叶子结点。5、分支结点(BranchNode)：度不为0的结点，也叫非终端结点或内部结点。在图5.1中，结点A、B、C、D、E、H是分支结点。6、孩子(Child)：结点子树的根。在图中，结点B、C、D是结点A的孩子。H、I、J是D的孩子7、双亲(Parent)：结点的上层结点叫该结点的双亲。在图中，结点B、C、D的双亲是结点A。8、祖先(Ancestor)：从根到该结点所经分支上的所有结点。在图中，结点E的祖先是A和B。m的祖先是a，d，h9、子孙(Descendant)：以某结点为根的子树中的任一结点称为该节点的子孙。在图中，除A之外的所有结点都是A的子孙。d的子孙是h、i、j、m10、兄弟(Brother)：同一双亲的孩子。在图5.1中，结点B、C、D互为兄弟。EF互为兄弟11、结点的层次(LevelofNode)：从根结点到树中某结点所经路径上的分支数称为该结点的层次。根结点的层次规定为1，其余结点的层次等于其双亲结点的层次加1。即a的层次为1，bcd的层次为2，klm的层次为4

12、堂兄弟(Sibling)：同一层的双亲不同的结点。在图中，G和H互为堂兄弟。13、树的深度(DepthofTree)：树中结点的最大层次数。在图中，树的深度为4。14、无序树(UnorderedTree)：树中任意一个结点的各孩子结点之间的次序构成，无关紧要的树。通常指无序树。

15、与无序树对应，有序树(OrderedTree)是指树中任意一个结点的各孩子结点有严格排列次序的树。二叉树是有序树，因为二叉树中每个孩子结点都确切定义为是该结点的左孩子结点还是右孩子结点。

16、森林(Forest)：m(m≥0)棵树的集合。自然界中的树和森林的概念差别很大，但在数据结构中树和森林的概念差别很小。从定义可知，一棵树有根结点和m个子树构成，若把树的根结点删除，则树变成了包含m棵树的森林。当然，根据定义，一棵树也可以称为森林。二叉树及其性质PART2二叉树(BinaryTree)的基本概念定义：一棵二叉树是n(n

0)个结点的一个有限集合，该集合或者为空（称为空二叉树），或者是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。621754389101112完全二叉树621754389101113141512满二叉树2154367一般二叉树2154367二叉树的特点每个结点最多有两棵子树，所以二叉树中不存在度大于2的结点左子树和右子树是有顺序的，次序不能任意颠倒即使树中某结点只有一棵子树，也要区分它是左子树还是右子树二叉树的形态只有根的二叉树空二叉树L有根且有一个左子树R有根且有一个右子树LR有根且左右子树均有思考题：画出3个节点的二叉树的所有形态性质1：在二叉树的第i层上至多有2i－1个结点。二叉树的性质证明：[证明用归纳法]—略设：深度为10的二叉树，问：第6层上最多有多少节点？第6层上最少有多少结点？第10层上最多有多少节点？第10层上最少有多少结点？问：第i层上结点数什么时候可以达到最大？——1个结点——32个结点(25)——512个结点(29)——1个结点答：i层之前每一层都达到了结点数的最大个数性质2深度为k的二叉树至多有2k-1个结点(k

1)。二叉树的性质设：深度为6的二叉树，问：这棵二叉树最少有多少结点？这棵二叉树最多有多少结点？设：深度为10的二叉树，问：这棵二叉树最少有多少结点？这棵二叉树最多有多少结点？——6个结点——63个结点(26-1)——1023个结点(210-1)——10个结点性质3对任何一棵二叉树T,如果其叶结点数为n0,度为2的结点数为n2,则n0＝n2＋1.二叉树的性质2154367216543621754389101113141512n0=4n2=3n0=8n2=7n0=3n2=2定义1

满二叉树(FullBinaryTree)

一棵深度为k且有2k-1个结点的二叉树称为满二叉树。两种特殊形态的二叉树满二叉树62175438910111314151262175432131定义2完全二叉树(CompleteBinaryTree)

深度为k，有n个结点的二叉树当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时，称为完全二叉树满二叉树891011121314154123567缺3个结点的完全二叉树89101112412356789104123567缺5个结点的完全二叉树

换一种描述：若设二叉树的高度为h，则共有h层。除第h层外，其它各层(0h-1)的结点数都达到最大个数，第h层从右向左连续缺若干结点，这就是完全二叉树。定义2完全二叉树(CompleteBinaryTree)完全二叉树891011124123567非完全二叉树891011124123567216543非完全二叉树2154367非完全二叉树结论：

满二叉树一定是一个完全二叉树完全二叉树不一定是满二叉树891011121314154123567问：一个深度为4的完全二叉树最少有多少结点？最多有多少结点？问：一个深度为k的完全二叉树最少有多少结点？最多有多少结点？答：最少8个结点最多15个结点答：最少2k-1个结点最多2K-1个结点性质4具有n(n

0)个结点的完全二叉树的深度为

log2(n)

＋1

891011121314154123567说明：

运算符代表向下取整，即取整数部分

问：有100个节点的完全二叉树的深度是多少？性质5

如将一棵有n个结点的完全二叉树自顶向下，同一层自左向右连续给结点编号1…n，则有以下关系：若i=1,则i无双亲若i>1,则i的双亲为

i/2

若2*i<=n,则i的左孩子结点编号为2*i，若2*i+1<=n,则i的右孩子结点编号为2*i+1891011124123567假设：一棵有500个结点的完全二叉树，则，210号结点的双亲结点编号是多少？左孩子结点编号分别是多少？右孩子结点编号分别是多少？再问：如果要求201、250号和300号结点的双亲和左右孩子呢？——105——420——421拓展问题：有n个结点的完全二叉树中有多少个叶子结点（n0）、单孩子结点（n1），双孩子结点（n2）？891011124123567当n=12时：n0=？n1=？n2=？当n=500时：n0=？n1=？n2=？当n=501时：n0=？n1=？n2=？615n0=n-

n/2

2502491二叉树的存储结构PART3完全二叉树的顺序表示二叉树的存储结构12489105637顺序表示法：利用完全二叉树的性质，存放到连续地址空间中123456789101234^5678^^^^91091235647810一般二叉树的顺序表示12345678910123456789101112131415二叉树的链式存储结构ABCDFE二叉链表lchildrchilddatatypedefcharTreeData;//结点数据类型typedefstructnode //结点定义{

TreeDatadata;structnode*lchild,*rchild;}BinTreeNode;typedefBinTreeNode*BinTree;//根指针

ABCDFEroot二叉链表ABCDFE三叉链表二叉树的链式存储结构lchildparentdatarchild三叉链表

ABCDFEroottypedefcharTreeData;//结点数据类型typedefstructnode //结点定义{

TreeDatadata;structnode*lchild,*rchild，*parent;}BinTreeNode;typedefBinTreeNode*BinTree;//根指针

二叉树的基本算法PART3

二叉树的基本算法（基于二叉链表）遍历算法建立算法查询算法删除算法二叉树的算法是以二叉树的定义和遍历操作为基础的二叉树遍历二叉树的遍历：就是按某种次序访问二叉树中的结点，要求每个结点访问一次且仅访问一次。

91235647810设根结点为V，左子树记作L，右子树记作RLR则可能的遍历次序有：前序：VLR

中序：LVR

后序：LRV

VRLRVLRLV

若规定先左后右遍历下列二叉树91235647810LR先序遍历：1-L-R其中L：2-Lm-空其中Lm：4-7-8R：3-5-Rm其中Rm：6-9-10Lm后序：Rm先序序列：12478356910同理中序：74821539610784259106312146850937先序：ABEFCDG中序：EFBCGDA后序：FEGDCBA先序：ABHFDECKG中序：HBDFAEKCG后序：HDFBKGCEA先序：5031249768中序：0123456789后序：2143068795二叉树遍历练习二叉树先序遍历算法的定义：若二叉树非空，则：访问根结点(V)；前序遍历左子树(L)；前序遍历右子树(R)。先序遍历算法(PreorderTraversal)先序遍历算法描述:PreOrder(BinTreeNode*T){if(T!=NULL){printf(“%d”,T->data);PreOrder(T->lChild);PreOrder(T->rChild);}}二叉树中序遍历算法的定义：若二叉树非空，则：中序遍历左子树(L)；访问根结点(V)；中序遍历右子树(R)。中序遍历算法(PreorderTraversal)中序遍历算法描述:InOrder(BinTreeNode*T){if(T!=NULL){InOrder(T->lChild);printf(“%d”,T->data);InOrder(T->rChild);}}二叉树后序遍历算法的定义：若二叉树非空，则：后序遍历左子树(L)；后序遍历右子树(R)。访问根结点(V)；后序遍历算法(PreorderTraversal)后序遍历算法描述:PostOrder(BinTreeNode*T){if(T!=NULL){PostOrder(T->lChild);PostOrder(T->rChild);printf(“%d”,T->data);}}--/+*abcdef后序遍历结果abcd-*+ef/-中序遍历结果a+b*c-d-e/f先序遍历结果-+a*b-cd/ef二叉树遍历的应用（先序建立二叉树）先建树根再建左子树再建右子树按先序遍历的原则建立二叉树1123说明：当前结点为空的时候，也必须告诉算法，要建一个空的二叉树，因此可以用输入特殊值代表该结点为空的方式来处理。输入：1空空输入：12空空3空空输入序列为ABC@@DE@G@@F@@@ABCDEGF@@@@@@@@说明：输入结点值的顺序必须对应二叉树结点前序遍历的顺序。并约定以输入序列中不可能出现的值作为空结点的值以结束递归。例如用“@”表示字符序列或正整数序列空结点。

voidCrtBinTree(BinTreeNode&T){TreeDatax;scanf("%d",&x);//读入根结点的值

if(x==0) T=nil;else{T=(BinTreeNode*)malloc(sizeof(BinTreeNode));

T->data=x;//建立根结点CrtBinTree(T->lChild);CrtBinTree(T->rChild);}}//先序建立二叉树的子程序

建立二叉树的主程序main(){bintreebt1;crtbintree(bt1);inorder(bt1);}

说明：先序遍历建立二叉树一般用在二叉树结构固定的情况下思考题：能否用中序或后序的方法建立二叉树？intCount(BinTreeNode*T){if(T==nil)return0;elsereturn1+Count(T->lChild)+Count(T->rChild);}计算二叉树结点个数(递归算法)算法思路：若：二叉树如果为空，则：结点个数为0否则：至少有一个根结点，再加上左子树和右子树的结点个数之和。问题：用三个遍历算法能实现吗？intLeaf_Count(BitreeT){if(T==nil)return0;//空树没有叶子elseif(T->lchild==nil&&T->rchild==nil)return1;//叶子结点

elsereturnLeaf_Count(T->lchild)+Leaf_Count(T->rchild);

//左子树的叶子数加上右子树的叶子数

}求二叉树中叶子结点的个数算法思路：若：二叉树为空，则：叶子数为0否则，若根是叶子，则：叶子树是1，否则：叶子数是左子树和右子树的叶子数之和。判断叶子的条件：左右孩子为空intHeight(BinTreeNode*T){if(T==NULL)return0;else { intm=Height(T->lChild); intn=Height(T->rChild)); return(m>n)?m+1:n+1;}}求二叉树的高度(递归算法)算法思路：若：二叉树为空，则：高度为0否则：至少有一层，再加上左子树和右子树中高度的最大值。复制二叉树(递归算法)*BinTreeNodeCopy(BinTreeNode*T){ if(T==nil)returnnil; BinTreeNode*temp=newBinTreeNode; Temp->data=T->data; Temp->lchild=Copy(T->lchild); Temp->rchild=Copy(T->rchild); returntemp;}思考题：能否用中序或后序的方法判断二叉树等价(递归算法)intEqual(BinTreeNode*a,BinTreeNode*b){if(a==NULL&&b==NULL)return1;if(a!==NULL&&b!==NULL &&a->data==b->data &&equal(a->lChild,b->lChild) &&equal(a->rChild,b->rChild)) return1;return0;//如果a和b的子树不等同，则函数返回0}思考题：能否用中序或后序的方法

Void destroy(BinTreeNode*t){if(t!=nil){destroy(t->lChild); destroy(t->rChild); free(t);}}删除根为t的二叉树思考题：能否用先序或中序的方法算法思路：若：二叉树不为空，则：应该先删除二叉树的左右子树，最后再删除根节点。BinTreeNode*Find(BinTreeNode*T,intx）{

if(T==nil)returnnil;if(T->data==x) returnT;//找到

elseif((p=Find(T->lchild,x))!=nil)returnp; //在左子树中找

elsereturnFind(T->rchild,x);//在右子树中找}在二叉树中查找元素值等于x的结点BinTreeNode*Parent(BinTreeNode*T,intx）

{//找当前结点的双亲结点，并返回

if(T==nil)returnnil;if(T->lchild->data==x||T->rchild->data==x) returnT;//找到

elseif((p=Parent(T->lchild,x))!=nil)returnp; //在左子树中找

elsereturnParent(T->rchild,x);//在右子树中找}在二叉树中查找元素值等于x的结点的双亲结点交换二叉树各结点的左、右子树voidunknown(BinTreeNode*T){BinTreeNode*p=T,*temp;if(p!=nil){temp=T->leftChild;T->leftChild=T->rightChild;T->rightChild=temp;unknown(T->leftChild);unknown(T->rightChild);}}思考题：能否用先序或中序的方法612345789612375849二叉树的确定例如：先序排列为：123456789我们可以用这个序列构造出不同的二叉树结论：某个二叉树的一个遍历序列，不能唯一确定这棵二叉树

例如,先序序列为{1,2,3}，可得5种不同的二叉树123123123123123设给定后序序列{3，2，1}后，任然有4种二叉树对应√√×√√结论：根据某二叉树的先序和后序序列，不能唯一确定这棵二叉树

例如,先序序列为{1,2,3}，可得5种不同的二叉树123123123123123中序321

231

213

132

123经证明：根据某二叉树中序以及先序和后序中的一个序列，就能唯一确定这棵二叉树二叉树的确定由二叉树的先序和中序序列或后序和中序序列可唯一地确定一棵二叉树。

例：先序序列：ABHFDECKG

和中序序列：HBDFAEKCGAEBHFDCKGAEKCGBHFDKCGAEBHFDAEBHFDCKGAEKCGBHDFAHBDFEKCG前序序列:ABHFDECKG中序序列:HBDFAEKCG,则构造过程如下：

二叉排序树定义：一棵空树，或者是具有下列性质的二叉树：（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；（2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值；（3）左、右子树也分别为二叉排序树；567030254236807590先序：56,30,25,42,36,70,80,75,90后序：25,36,42,30,75,90,80,70,56中序：25,30,36,42,56,70,75,80,90特点：对二叉排序树进行中序遍历可得到有序序列5030802090108540352523887066二叉排序树的构建过程：567030254236807590如输入顺序是：56,30,42,70,25,80,36,75,90先序：56,30,25,42,36,70,80,75,90后序：25,36,42,30,75,90,80,70,56中序：25,30,36,42,56,70,75,80,90由关键字序列3，1，2，5，4构造而得的二叉排序树：

→由关键字序列1，2，3，4，5构造而得的二叉排序树：→同一组数据，输入顺序不同，构造的二叉排序树不同，查找效率也不同2134535412ASL=(1+2+3+4+5)/5=3ASL=(1+2+3+2+3)/5=2.2BinTreeInsertBST(BinTreeT,inte)//建立过程就是不断将新数据{BinTreep;//插入到二叉排序树的过程if(T==nil)//空树的时候将本元素作为根结点{T=(BinTreeNode*)malloc(sizeof(BinTreeNode));T->data=e;T->lchild=T->rchild=nil;}elseif(e<T->data)T->lchild=InsertBST(T->lchild,e);elseif(e>T->data)T->rchild=InsertBST(T->rchild,e);returnT;}二叉排序树的插入算法：一个无序序列可以通过构造一棵二叉排序树而变成一个有序序列每次插入的新结点都是二叉排序树上新的叶子结点插入时不必移动其它结点，仅需修改某个结点的指针树和森林PART5树与森林ACFEBDG双亲表示法顺序表示法。孩子兄弟表示法左孩子右兄弟，即链表表示法树的存储结构0102ACFEBDG0123456ABCDEFG-1000113dataparent注意：结点A是根结点，所以其双亲是-1树与森林：树的存储结构01双亲表示法用一组连续空间存储树的结点，同时在结点中附设一个指针，存放双亲结点在表中的位置用双亲表示实现的树定义#defineMaxSize 100//最大结点个数typedefcharTreeData;//结点数据typedefstruct{//树结点定义

TreeDatadata;intparent;}TreeNode;TreeNodeTree[MaxSize];//树树与森林：树的存储结构第一种方案：用和树的度等数量的链域

data

child1child2child3childdABCDEFG

空链域：n(d-1)+1个ACFEBDG树与森林：树的存储结构02树的链式存储结构结点结构

datafirstChildnextSiblingABCDEFG第二种方案：树的左子女-右兄弟表示（二叉链表表示）BCDGFE

A

空链域：n+1个树与森林：树的存储结构（链式存储）typedefcharTreeData;typedefstructnode{TreeDatadata;structnode*firstChild,*nextSibling;}TreeNode;typedefTreeNode*Tree;用左子女-右兄弟表示实现的树定义树与森林：树的存储结构（孩子兄弟表示法）树和二叉树的转换：利用孩子兄弟表示法ABDCEGFABCDEFG树与森林：树和二叉树的转换T1T2T3BCDGIJEKAFHT2FG3棵树的森林各棵树的二叉树表示森林的二叉树表示ABDCET1

HIKJT3树和二叉树的转换：利用孩子兄弟表示法树与森林：树和二叉树的转换树的遍历树与森林02广度优先遍历按层遍历01深度优先遍历先跟次序遍历后跟次序遍历树的先根次序遍历结论：树的先根遍历可以借助对应二叉树的前序遍历算法实现ACFEBDGABDCEGF算法描述：当树非空时访问根结点依次先根遍历根的各棵子树树先根遍历结果：ABEFCDG对应二叉树前序遍历结果：ABEFCDG结果相同树与森林：深度优先遍历结论：树的后根遍历可以借助对应二叉树的中序遍历算法实现ACFEBDGABDCEGF算法描述：当树非空时：（1）依次后根遍历根的各棵子树（2）访问根结点树后根遍历结果：EFBCGDA对应二叉树中序遍历结果：EFBCGDA结果相同树的后根次序遍历树与森林：深度优先遍历广度优先遍历——按层遍历ACFEBDG广度优先遍历结果：ABCDEFG树与森林哈夫曼树及其应用PART6二叉树的应用—哈夫曼树路径长度(PathLength)

两个结点之间的路径长度PL是连接两结点的路径上的分支数。树的外部路径长度是各叶结点(外结点)到根结点的路径长度之和EPL。——重点树的内部路径长度是各非叶结点(内结点)到根结点的路径长度之和IPL。树的路径长度PL=EPL+IPL123645781234567812364578树的外部路径长度EPL=2*3+3*1=9树的外部路径长度EPL=1*1+2*1+3*1+4*1=10二叉树的应用—哈夫曼树带权路径长度(WeightedPathLength,WPL) 二叉树的带权(外部)路径长度是树的各叶子结点所带的权值

wi与该结点到根的路径长度

li的乘积的和。霍夫曼树带权路径长度达到最小的二叉树即为霍夫曼树。在霍夫曼树中，权值越大的结点离根越近。二叉树的应用—哈夫曼树WPL=2*2+4*2+5*2+7*2=36245747257254带权路径长度最小,是霍夫曼树WPL=2*1+4*2+5*3+7*3=46WPL=7*1+5*2+2*3+4*3=35二叉树的应用—哈夫曼树1.由给定的n个权值{w0