第六章
结点的出度(OD)：结点拥有的非空子树数目。
结点的入度(ID)：指向结点的分支(或有向弧、指针)的数目。
树的度(TD)：树中结点出度的最大值。
结点的度：该结点的出度
例如 在下述结论中，正确的是( D )【南京理工大学 1999 一、4 (1分)】
①只有一个结点的二叉树的度为0; ②二叉树的度为2; ③二叉树的左右子树可任意交换;④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。
A.①②③ B.②③④ C.②④ D.①④
有关二叉树下列说法正确的是( B )【南京理工大学 2000 一、11 (1.5分)】
A.二叉树的度为2 B.一棵二叉树的度可以小于2
C.二叉树中至少有一个结点的度为2 D.二叉树中任何一个结点的度都为2
有序树和无序树：若树中任一结点的各子树从左到右有序，则该树为有序树(强调子树的次序)，否则为无序树。(只强调各子树之间相对有序，而并不像二叉树那样，当只有一个子树是要么是左子树要么是右子树。而在有序树中，只有一个子树的有序树就不唯一了。)
例题：在下列情况中，可称为二叉树的是( B )
A.每个结点至多有两棵子树的树 B. 哈夫曼树 C.每个结点至多有两棵子树的有序树 D. 每个结点只有一棵右子树 E.以上答案都不对
C错在有序树不一定是二叉树，有序只是子树的相对保持有序，并没有严格定义具体那颗子树就是第几颗子树。
森林(或树林)：m(m≥0) 棵互不相交的有序树的有序集合。
深度=h(h≥1)的K(K>1)叉树至多有( -1)/(K-1)个结点。
包含n(n≥0)个结点的K(K>1)叉树的最小深度为：
证：设有n个结点的K叉树的深度为h，若该树h-1层都是满的，即每层有最大结点数 -1(1≤i≤h-1)，且其余结点都落在第h层，则该树的深度达最小，如图6.11所示：
或：(Kh-1 -1)
即：Kh-1
取对数：(h-1)
因为h为正整数，所以：h=
含有n(n ≥1)个结点的完全二叉树的深度
n个叶结点的非满的完全二叉树的高度是élog2nù+1。(最下层结点数>=2)。
设完全二叉树BT结点数为n，结点按层编号。对BT中第i结点(1≤i≤n)，注意结点编号从1开始，在数组存储时也是从数组1开始,若题目已然确定从0开始，则在计算孩子父亲结点时都需要重新变换一下。
有：
(1)若i=1，则i结点(编号为i的结点)是BT之根，无双亲;否则( i>1)，parent(i)= ，即i结点双亲的编号为 ;
(2)若2i>n，则i结点无左子，否则Lchild(i)=2i，即i结点的左子位于第2i号结点;
(3)若2i+1>n，则i结点无右子，否则Rchild(i)=2i+1，即i结点的右子位于第2i+1号结点。
证明：采用数学归纳法，先证(2)和(3)。
设n个结点的完全二叉树如图所示。
i=1时,显然 i 结点的左子编号为2，i的右子编号为2+1=3，除非2>n , 3>n 。
设对i结点，命题(2)、(3)成立，即Lchild(i)=2i，Rchild(i)=2i+1。根据按层编号规则，i+1时有：
Lchild(i+1)=(2i+1)+1=2(i+1)，除非2(i+1)>n,
Rchild(i+1)=(2i+1)+1+1=2(i+1)+1，除非2(i+1)+1>n，
故(2)、(3)得证。
再证(1)，它可看作是(2)、(3)的推广。
因Lchild(j)=2j，所以Parent(2j)=j,令2j=i，有 Parent(i)=i/2= (i/2为正整数);
又：Rchild(j)=2j+1，所以Parent(2j+1)=j，令2j+1=i (i=3,5,7…)，有:
Parent(i)=(i-1)/2= ，证毕。
n
2i
2i+1
1
2
3
2i+1+1
2i+1+2
i
i+1
例题：一棵完全二叉树上有1001个结点，其中叶子结点的个数是( )【西安交通大学 1996 三、2 (3分)】
A. 250 B. 500 C.254 D.505 E.以上答案都不对 501
例题1：由二叉树结点的公式：n=n0+n1+n2=n0+n1+(n0-1)=2n0+n1-1， 因为n=1001,所以1002=2n0+n1,在完全二叉树树中，n1只能取0或1,在本题中只能取0，故n=501，因此选E。
例题2：高度为K的完全二叉树至少有_ __个叶子结点。(刚好第K上只有一个叶子时，高度为K，N= -1+1= 例题3：在顺序存储的二叉树中，编号为i和j的两个结点处在同一层的条件是
用顺序存储二叉树时，要按完全二叉树的形式存储，非完全二叉树存储时，要加“虚结点”。设编号为i和j的结点在顺序存储中的下标为s 和t ,则结点i和j在同一层上的条件是ëlog2sû=ëlog2tû。
考研有疑问、不知道如何总结考研考点内容、不清楚考研报名当地政策，点击底部咨询官网，免费领取复习资料：
https://www.87dh.com/xl/