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

;目;;线性结构的特征：;非线性结构的特征：;树的概念和基本术语;A;家谱可以用树描述;;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，h

9、子孙(Descendant)：以某结点为根的子树中的任一结点称为该节点的子孙。在图中，除A之外的所有结点都是A的子孙。d的子孙是h、i、j、m

10、兄弟(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棵树的森林。当然，根据定义，一棵树也可以称为森林。

;;二叉树(BinaryTree)的基本概念;;二叉树的形态;性质1：在二叉树的第i层上至多有2i－1个结点。;性质2深度为k的二叉树至多有2k-1个结点(k?1)。;性质3对任何一棵二叉树T,如果其叶结点数为n0,度为2的结点数为n2,则n0＝n2＋1.;定义1满二叉树(FullBinaryTree)

一棵深度为k且有2k-1个结点的二叉树称为满二叉树。;定义2完全二叉树(CompleteBinaryTree)

深度为k，有n个结点的二叉树当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时，称为完全二叉树;定义2完全二叉树(CompleteBinaryTree);;性质4具有n(n?0)个结点的完全二叉树的深度为?log2(n)?＋1;性质5如将一棵有n个结点的完全二叉树自顶向下，同一层自左向右连续给结点编号1…n，则有以下关系：

若i=1,则i无双亲

若i1,则i的双亲为?i/2?

若2*i=n,则i的左孩子结点编号为2*i，

若2*i+1=n,则i的右孩子结点编号为2*i+1;拓展问题：有n个结点的完全二叉树中有多少个叶子结点（n0）、单孩子结点（n1），双孩子结点（n2）？;;完全二叉树的顺序表示;二叉树的链式存储结构;;;;二叉树遍历;遍历下列二叉树;;二叉树先序遍历算法的定义：

若二叉树非空，则：

访问根结点(V)；

前序遍历左子树(L)；

前序遍历右子树(R)。;二叉树中序遍历算法的定义：

若二叉树非空，则：

中序遍历左子树(L)；

访问根结点(V)；

中序遍历右子树(R)。;二叉树后序遍历算法的定义：

若二叉树非空，则：

后序遍历左子树(L)；

后序遍历右子树(R)。

访问根结点(V)；

;;二叉树遍历的应用（先序建立二叉树）;输入序列为

ABC@@DE@G@@F@@@;;;intCount(BinTreeNode*T)

{

if(T==nil)retu