树是一种非线性的数据结构,它是由n(n>=0)个有限结点组成一个具有层次关系的集合。把它叫做树是因 为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。
如图所示的树就是由根和三个子树构成的,子树也是如此,例如第一个子树就是由根和两个子树构成的,第二个子树是由根和一个子树构成的,第三个子树是由根和两个子树构成的,这就是为什么树是递归定义的原因。
注意:树形结构中,子树之间不能有交集,否则就不是树形结构。
在上面的结构图中,如果树带了回路就是图了。
节点的度:一个节点含有的子树的个数称为该节点的度; 如上图:A的为6
叶节点或终端节点(重点):度为0的节点称为叶节点; 如上图:B、C、H、I…等节点为叶节点
非终端节点或分支节点:度不为0的节点; 如上图:D、E、F、G…等节点为分支节点
双亲节点或父节点(重点):若一个节点含有子节点,则这个节点称为其子节点的父节点; 如上图:A是B的父节点
孩子节点或子节点(重点):一个节点含有的子树的根节点称为该节点的子节点; 如上图:B是A的孩子节点
兄弟节点:具有相同父节点的节点互称为兄弟节点; 如上图:B、C是兄弟节点,但是H和I就不是兄弟节点
树的度:一棵树中,最大的节点的度称为树的度; 如上图:树的度为6
节点的层次:从根开始定义起,根为第1层,根的子节点为第2层,以此类推;当然,也有从根开始定义起,根为第0层开始的,不过这种比较少。
树的高度或深度(重点):树中节点的最大层次; 如上图:树的高度为4
堂兄弟节点:双亲在同一层的节点互为堂兄弟;如上图:H、I互为兄弟节点
节点的祖先:从根到该节点所经分支上的所有节点;如上图:A是所有节点的祖先,Q的祖先是Q、A、E、J
注意:自己可以认为是自己的祖先。
例题:在上面的图中。F和K的最近公共祖先是F,因为F可以认为是自己的祖先,而F同时也是K的祖先。
子孙:以某节点为根的子树中任一节点都称为该节点的子孙。如上图:所有节点都是A的子孙
注意:自己可以认为是自己的子孙。
森林:由m(m>0)棵互不相交的树的集合称为森林
树结构相对线性表就比较复杂了,要存储表示起来就比较麻烦了,既然保存值域,也要保存结点和结点之间的关系,实际中树有很多种表示方式如:双亲表示法,孩子表示法、孩子双亲表示法以及孩子兄弟表示法 等。我们这里就简单的了解其中最常用的孩子兄弟表示法。
typedef int DataType;
struct Node
{
struct Node* _firstChild1; // 第一个孩子结点
struct Node* _pNextBrother; // 指向其下一个兄弟结点
DataType _data; // 结点中的数据域
};
//一个节点有多少个子节点都无所谓,,父亲指向第一个孩子,剩下的孩子,用孩子的兄弟指针链接起来。
一棵二叉树是结点的一个有限集合,度最大为2,该集合:
从上图可以看出:
注意:对于任意的二叉树都是由以下几种情况复合而成的:
若规定根节点的层数为1,则一棵非空二叉树的第i层上最多有2(i-1)个结点 .
若规定根节点的层数为1,则深度为h的二叉树的最大结点数是2h-1.
对任何一棵二叉树, 如果度为0其叶结点个数为n0, 度为2的分支结点个数为n2,则有n0=n2+1.(只要增加一个度为2的,就必然增加两个度为0的)
若规定根节点的层数为1,具有n个结点的满二叉树的深度,h= log2(n+1). (ps:log2(n+1)是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否则无右孩子
A 不存在这样的二叉树
B 200
C 198
D 199
解析:运用的是上面的性质3,度为0的个数比度为2的个数多1,即199+1即200就能得到我们想要的结果。
A 非完全二叉树
B 堆
C 队列
D 栈
A N
B N+1
C N-1
D N/2
解析:
假设度为2的节点数为N2,那么度为1的节点数为N1,度为1的节点数为N0,从上面的性质可以得到N2和N0的关系,即N0 = N2 + 1
N0 + N1 + N2 = 2N
运用上面的关系即可得到下面的式子:
N0 + N1 + N0 - 1 = 2N
2N0 - 1 + N1 = 2N
完全二叉树N1是1个或者0个
如果上面的式子要满足,那么N1只能是1个(必须满足2N0 - 1 + N1 = 2N),所以得到下面的式子
2N0 = 2N
即N0 = N
所以叶子节点的个数为N
A 11
B 10
C 8
D 12
解析:
有h层的满二叉树的节点的数量为:2h-1
假设某个满二叉树的节点数量为N,此时二叉树的深度为:h = log2(N+1)
针对此题,假设高度是h,那么该二叉树的节点个数为:
最多:2h-1
最少:2h-1(即前h-1层节点的数量加1公式为N = 2h-1-1+1(加1是因为最后一层还有一个节点))
假设某二叉树的节点数量为N,那么N必然满足下面这个不等式:
2^h-1 < N < 2h-1
将所给条件带入之后,经过计算可得,h为10
A 383
B 384
C 385
D 386
假设度为2的节点数为N2,那么度为1的节点数为N1,度为1的节点数为N0,从上面的性质可以得到N2和N0的关系,即N0 = N2 + 1
N0 + N1 + N2 = 767
N0 + N1 + N0-1 = 767
2*N0 - 1 + N1 = 767
此时N1只能是0,为什么?因为当N1是1的时候,此时节点的数目应该是偶数,但是题目所给的是奇数,所以N1只能是0。
所以计算之后叶子节点的个数是384。
二叉树一般可以使用两种结构存储,一种顺序结构,一种链式结构。
顺序结构存储就是使用数组来存储,一般使用数组只适合表示完全二叉树,因为不是完全二叉树会有空 间的浪费。而现实中使用中只有堆才会使用数组来存储,关于堆我们后面的章节会专门讲解。二叉树顺序存储在物理上是一个数组,在逻辑上是一颗二叉树。
二叉树的链式存储结构是指,用链表来表示一棵二叉树,即用链来指示元素的逻辑关系。 通常的方法是 链表中每个结点由三个域组成,数据域和左右指针域,左右指针分别用来给出该结点左孩子和右孩子所 在的链结点的存储地址 。链式结构又分为二叉链和三叉链,当前我们学习中一般都是二叉链,后面课程 学到高阶数据结构如红黑树等会用到三叉链。
typedef int BTDataType;
// 二叉链
struct BinaryTreeNode
{
struct BinTreeNode* _pLeft; // 指向当前节点左孩子
struct BinTreeNode* _pRight; // 指向当前节点右孩子
BTDataType _data; // 当前节点值域
}
// 三叉链
struct BinaryTreeNode
{
struct BinTreeNode* _pParent; // 指向当前节点的双亲
struct BinTreeNode* _pLeft; // 指向当前节点左孩子
struct BinTreeNode* _pRight; // 指向当前节点右孩子
BTDataType _data; // 当前节点值域
};
版权说明 : 本文为转载文章, 版权归原作者所有 版权申明
原文链接 : https://blog.csdn.net/m0_57304511/article/details/124227733
内容来源于网络,如有侵权,请联系作者删除!