文章目录
- 一、树的基础概念
- 1、节点与度数
- 2、树的度与高度
- 3、引入:数组下标为何从0开始
- 4、祖先节点
- 5、树是递归定义的
- 6、树与非树的区别
- 7、代码表示
- 二、二叉树
- 2.1、满二叉树
- 2.2、完全二叉树
- 2.3、完全二叉树的存储
- 三、堆
一、树的基础概念
1、节点与度数
节点分为叶节点与分支节点
- 度数:其子节点的个数
- 叶节点:无子节点,即节点度数为0
- 分支节点:度数不为0的节点
2、树的度与高度
- 树的度:节点中度数最大的度数为树的度
- 树的高度(深度):树的最大层次
3、引入:数组下标为何从0开始
答:迫于无奈,方便计算。
已知:数组名=数组首元素的地址
且 a[i] = *( a+i )
若下标从1开始,那么首元素 = *( a+1 )该式显然不成立。
4、祖先节点
从我这个节点往上这条路径的节点均为我的祖先节点。
5、树是递归定义的
一个树可分为根和子树(度>=0)。
6、树与非树的区别
树:
- 子树间不相交
- 除根节点外,每个节点有且仅有一个母(父)节点
非树:子树间相交。
7、代码表示
存储方法:左孩子右兄弟模型(链表)
struct TreeNode
{int val;struct TreeNode* LeftChild;struct TreeNode* RightSister;
};
二、二叉树
1、定义:树的每个节点的度数最大为2
2、代码模型:左孩子右孩子(可参考左孩子右兄弟模型)
2.1、满二叉树
1、定义:每一层都是满的(2个节点),叶子只在最后一层。
2、第 k 层有 2^(k-1)个节点
总节点个数:2^k - 1
2.2、完全二叉树
1、定义:设二叉树的高度为k,其前k-1层都是满的,最后一层不满且从左到右必须是连续的。
2、满二叉树是特殊的完全二叉树。
2.3、完全二叉树的存储
物理结构:在内存中以数组的形式存储。
原理:在内存中存储以数组的形式,已知一个父节点,则它的后两个数据一定是它的子节点。
-
1、局限
只适用于完全/满二叉树,对非完全也可以,但存在很大的空间浪费。 -
2、优点
便于访问母(父)子关系
已知父节点下标为 i
则 左孩子下标为 2 * i+1, 右孩子下标为 2*i+2已知一个子节点的下标为 j
1、j 为奇数时,为左孩子,父下标为 (j -1)/2
2、j 为偶数时,为右孩子,父下标为 (j -2)/2
但在C语言中,除后取整
故可直接写为 (j -1)/2
三、堆
注:
1、堆是一个完全二叉树(可用数组存储)
2、C语言中的堆、栈是内存的划分,与数据结构中的堆(二叉树)、栈(后进先出)不一样
大堆:任何一个父节点都大于等于其子节点
小堆:任何一个父节点都小于等于其子节点
3、特点
可以直接得到极值。大堆:根是极大值,小堆:根是极小值。