树是一种非线性的数据结构,它是由n(n>=0)个有限结点组成一个具有层次关系的集合。之所以叫它树,是因为将此结构倒转后与现实生活中的树极其相似,一个主干分出多个分支,分支还可继续分展。
“树”和树大致可以用如下形式表示:
注意:树形结构中,子树之间不能有交集,否则就不是树形结构:
以上这三种结构都不是树形结构,由此也可推断出:
N
个节点的树只能有N-1
条边。树结构相对线性表就比较复杂了,要存储表示起来就比较麻烦了,既然保存值域,也要保存结点和结点之间的关系,实际中树有很多种表示方式如:双亲表示法,孩子表示法、孩子双亲表示法以及孩子兄弟表示法等。我们这里就简单的了解其中最常用的孩子兄弟表示法。
孩子兄弟表示法: 定义一个结构体,并在其中定义两个结构体指针,一个指向下一层次的第一个孩子节点(firstChild
),另一个指向同层次的第一个兄弟节点(pNextBrother
),若不存在就将这些节点指向NULL
。于是乎我们可以通过pNextBrother
指针来遍历某一层的全部节点,通过firstChild
指针来调整层次。此结构体如下定义:
typedef int TreeDataType;
struct Node
{
struct Node* firstChild; // 第一个孩子结点
struct Node* pNextBrother; // 指向其下一个兄弟结点
TreeDataType data; // 结点中的数据域
};
理论结构大致如下:
表示文件系统的目录树结构,如Linux
树状目录结构
一棵二叉树是结点的一个有限集合,该集合:
二叉树满足的条件:
对于任意的二叉树都是由以下几种情况复合而成的:
K
,且结点总数是2^k-1
, 则它就是满二叉树。1
,则一棵非空二叉树的第i层上最多有2^(i-1)
个结点。1
,则深度为h
的二叉树的最大结点数是2^h-1
。0
其叶结点个数为n0
, 度为2
的分支结点个数为n2
,则有n0=n2+1
。1
,具有n
个结点的满二叉树的深度,h= log以2 为底,n+1为对数
。n
个结点的完全二叉树,如果按照从上至下从左至右的数组顺序对所有节点从0
开始编号,则对于序号为i
的结点有:
- 若
i>0
,i
位置节点的双亲序号:(i-1)/2
;i=0
,i
为根节点编号,无双亲节点;- 若
2i+1<n
,左孩子序号:2i+1
,2i+1>=n
否则无左孩子;- 若
2i+2<n
,右孩子序号:2i+2
,2i+2>=n
否则无右孩子。
二叉树一般可以使用两种结构存储,一种顺序结构,一种链式结构:
- 某二叉树共有 399 个结点,其中有 199 个度为 2 的结点,则该二叉树中的叶子结点数为(
B
)
A 不存在这样的二叉树
B 200
C 198
D 199解:叶子节点数 = 度为
2
的节点数+ 1
,即199+1=200
- 在具有 2n 个结点的完全二叉树中,叶子结点个数为(
A
)
A n
B n+1
C n-1
D n/2解:因为为完全二叉树,且总节点数为偶,可以得出第
2n
个节点为左孩子,所以度为二的节点数为最后一个节点的父亲节点2n/2
再减去1
,最终的叶子节点数为2n/2-1+1 = n
。
- 一棵完全二叉树的节点数位为531个,那么这棵树的高度为(
B
)
A 11
B 10
C 8
D 12解:设高度为
h
,当2^h-1 >= 531
且h
为整数,h
的最小值为10
。