做网站客户拖着不验收wordpress 注册地址
数据结构-二叉树-基础知识
- 1.树
- 1.1什么是树
- 1.2基本概念
- 子节点、父节点
- 叶节点
- 节点的度
- 树的高度/深度
- 节点的子孙、祖先
- 1.3树与非树
- 1.4如何实现
- 1.5实例
- 2.二叉树
- 2.1什么是二叉树
- 2.2特殊的二叉树
- 满二叉树
- 完全二叉树
- 2.3性质
- 层数
- 度
- 节点
- 2.4存储结构
1.树
1.1什么是树
树型结构是一类重要的非线性数据结构。树是以分支关系定义的层次结构。
把它叫做“树”是因为它常看起来像一棵倒挂的树,也就是说它常是根朝上,而叶朝下的。

1.2基本概念
子节点、父节点
子节点也叫孩子节点。
子节点:在树形图中,当前节点的各个子树的根称为当前节点的子节点。即当前节点所直接支配的节点。
可理解为:指该节点下一层与其直接相连的节点。

A的子节点为B、C、D。
E的子节点为J、K。
对于各个子节点,它们上面的那个就叫父节点,也叫双亲节点。
B、C、D的父节点为A。
J、K的父节点为E。
叶节点
叶节点也叫终端节点、叶子。特点是度为0。

对于上图,C、F、G、H、I、J、K就是叶节点。
节点的度
节点的度:节点拥有子节点的数量。
可理解为:该节点的下一层与其直接相连的节点数。

A的度为3。
D的度为4。
树的高度/深度
指树的最大层次。

上图,树的高度为4。
节点的子孙、祖先
子孙:指该节点下面所有与其直接或间接相连的节点。
祖先:指从该节点到根所经过的所有节点。

B的子孙为E、J、K。
J的祖先为E、B、A。
A为所有节点的祖先。
1.3树与非树
对于一个树,有几个重要的特点:
- 子树不能相交。
- 除了根节点,每个节点有且仅有一个父节点。
- 有
N个节点,就有N+1条边。
反例:


1.4如何实现
左孩子右兄弟表示法。
即,在每个节点中,存储其最左边的子节点的地址、其右边那个兄弟节点的地址。
大概是这样:

typedef int DataType;
struct TreeNode
{struct TreeNode* pFistChild;struct TreeNode* pNextBorther;DataType data;
};
1.5实例
如文件夹:

2.二叉树
2.1什么是二叉树
二叉树每个节点的度最大为二,即,每个节点最多分出两个子树,且有左右之分。
每一个二叉树都由下面几种情况组合而成:

2.2特殊的二叉树
满二叉树
每层都是满的,就是满二叉树,如下面这几个:

完全二叉树
现假设有个满二叉树,有h层,那么,在第h层的最后去掉几个节点就得到完全二叉树:

需注意:满二叉树是特殊的完全二叉树。
2.3性质
层数
令根节点层数为1。
| 层数 | 1 | 2 | 3 | 4 | … | h |
|---|---|---|---|---|---|---|
| 每层最多节点数 | 1 | 2 | 4 | 8 | … | 2^(h-1) |
| 最多节点总数 | 1 | 3 | 7 | 15 | … | (2^h)-1 |
n个节点的满二叉树:层数h=log(n+1)。
度
- 对任意的二叉树,当度为
2的节点有n1个,度为0的节点有n2个,有n2=n1+1。
节点
n个节点的完全二叉树,由根节点开始从0编号。

那么,对于一个序号为k的节点,有:
k == 0,为根;k != 0,双亲节点的序号为(k-1)/2。
如对D、E:(4-1)/2 == (3-1)/2 == 1。- 当
2*k + 1 < n,左孩子序号为2k+1。 - 当
2*k + 2 < n,右孩子序号为2k+2。
2.4存储结构
可用两种结构存储,一种顺序结构,一种链式结构。
顺序结构:用数组存储,一般只适合完全二叉树,否则会造成空间浪费。
链式结构:用链表存储,用指针链接节点。
希望本篇文章对你有所帮助!并激发你进一步探索数据结构的兴趣!
本人仅是个C语言初学者,如果你有任何疑问或建议,欢迎随时留言讨论!让我们一起学习,共同进步!
