二叉树的定义及其主要特征
标签: 数据结构
学习人数: 8450


全屏播放
赞赏支持

二叉树的定义

       二叉树是一种特殊的树形结构,其特点是每个结点至多只有两颗子树,并且二叉树的子树有左右之分,次序不能颠倒。

       二叉树是n(n≥0)个结点的有限集合:其或者为空二叉树(n=0),或者由一个根结点和两个互不相交的被称为根的左子树和右子树组成。左子树和右子树又分别是一棵二叉树。

       二叉树是有序树,若将其左右子树颠倒,则成为另一棵不同的二叉树。即使树中结点只有一棵子树,也要区分是左子树还是右子树。其有五种基本形态如下:

 二叉树与度为2的有序树的区别:

       (1)度为2的树至少有3个结点(根结点),而二叉树可以为空;

       (2)度为2的...

登录查看完整内容


课后作业

课后习题

【2018年真题】设一棵非空完全二叉树T的所有叶结点均位于同一层,且每个非叶结点都有2 个子结点。若 T有 k个叶结点,则T的结点总数是()。
A . 2k-1    B. 2k    C. k2    D. 2k-1

参考答案:A

 

【2011年真题】若一棵完全二叉树有768个结点,则该二叉树中叶结点的个数是()
A.257
B.258
C.384
D.385 

解答:C。叶结点数为n,则度为2的结点数为n-1,度为1的结点数为0或1,本题中为1(总结点数为偶数),故而即2n=768。 


【2009年真题】已知一棵完全二叉树的第 6 层(设根为第 1 层)有 8 个叶结点,则该完全二叉树的结点个数最多是()。 
A. 39         B.52         C.111         D.119

参考答案:C
答案解析:考查完全二叉树的特点。 
完全二叉树比起满二叉树只是在最下面一层的右边缺少了部分叶结点,而最后一层之上是个满二叉树,并且只有最后两层上有叶结点。第 6 层有叶结点则完全二叉树的高度可能为 6 或 7,显然树高为 7时结点更多。若第 6 层上有 8 个叶结点,则前六层为满二叉树,而第 7 层缺失了 8×2=16 个叶结点,故完全二叉树的结点个数最多为 27-1-16=111 个结点。


【2016年真题】如果一颗非空k(k>=2)叉树T中每个非叶结点都有k个孩子,则称T为正则后k树。请回答下列问题并给出推导过程。
(1)若T有m个非叶结点,则T中的叶结点有多少个?
(2)若T的高度为h(单结点的树h=1),则T的结点数最多为多少个?最少为多少个?

参考答案:
(1)根据定义,正则k叉树中仅含有两类结点:叶结点(个数记为n0)和度为k的分支结点(个数记为nk)。树T中的结点总数n=n0+nk=n0+m。树中所含的边数e=n-1,这些边均为m个度为k的结点发出的,即e=m*k。整理得:n0+m=m*k+1,故n0=(k-1)*m+1。
(2)高度为h的正则k叉树T中,含最多结点的树形为:除第h层外,第1到第h-1层的结点都是度为k的分支结点,而第h层均为叶结点,即树是“满”树。此时第j(1<=j<=h)层结点数为kj-1,结点总数M1为:

含最少结点的正则k叉树的树形为:第1层只有根结点,第2到第h-1层仅含1个分支结点和k-1个叶结点,第h层有k个叶结点。即除根外第2到第h层中每层的结点数均为k,故T中所含结点总数M2位:M2 = 1 + (h-1) * k。


登录后发布评论

暂无评论,来抢沙发