一、树
1、什么是树?
(1)树的概念
树是一种非线性结构。
我们先来解释一下什么是非线性结构,什么是线性结构?
线性结构其实就是一对一的感觉,比如我们之前学的顺序表、链表、栈、队列他们都是一对一的,而非线性结构自然就是一对多的,如下图所示:
我们观察一下这个图中的非线性结构,将其倒过来的时候其实就形似一棵树,因此这种非线性结构就称之为“树”
(2)树与非树
树的子节点之间没有联系
树的子节点之间是没有联系的。下图所示的图中红线连接两个子节点,所以这个结构就不是树。
树的子节点有且仅有一个父节点
上述图片中有的子节点通过红线连接了新的父节点,导致这些子节点的父节点不只有一个。因此这种结构不称之为树。
(3)树的术语
节点的度
一个节点含有的子树的个数称之为改建点的度,简而言之,该节点直接相连了几个子节点,他的度就是多少。
叶结点
没有子节点的节点称之为叶结点。即度为0的节点称之为叶结点。
父节点
若一个节点有子节点,那么这个节点就是那些子节点的父节点。
兄弟节点
具有相同父节点的节点互为兄弟节点。
节点的祖先
从根到该节点的路径上,所有在该节点上方的节点都是该点的祖先。
A的度为3,E,F,G,H,I是叶节点,E和F是兄弟节点,A和C都是G的祖宗节点,A是所有点的祖宗节点,B是E的父节点。
(4)树的表示——孩子兄弟表示法
我们创建一个结构体,这个结构体除了存储该节点的数据外,还要存储左边第一个子节点的地址,以及右边第一个兄弟节点的地址。这样就能有效地串通所有的节点。
struct TreeNode
{
int a;
struct TreeNode *firstchild;
struct TreeNode *nextbrother;
};
2、二叉树
二叉树是一种特殊的树,节点的度都小于等于2。
(1)、满二叉树
满二叉树是一种特殊的二叉树,除了叶节点的度为0外,其余节点的度均为2。
(2)、完全二叉树
完全二叉树如下图所示:
假设我们不看最后一层叶结点,那么上面就是一个满二叉树,完全二叉树对最后一层的叶结点是有要求的。即,最后一层的叶结点是连续的,不能有间隔,比如下图所示的情况就不是完全二叉树。
3、二叉树的性质
-
若规定根节点的层数是1,则一棵非空二叉树的第i层上最多有2^(i-1)^个节点。
-
若规定根节点的层数是1,则深度为h的二叉树的最大节点数是2^h^-1。
-
对任何一棵二叉树,度为0的叶结点个数为$n_0$,度为2的节点个数为$n_2$,则有$n_0$=$n_2$+1
-
若规定根节点的层数为1,具有n个节点的满二叉树的深度为h,h=$\log_2$(n+1)
-
对于具有n个节点的完全二叉树,如果按照从上至下从左到右的数组顺序对所有节点从0开始编号,则对于序号为i的节点有:
-
若 i>0,i位置节点的父节点的序号为:(i-1)/2, i=0的时候,i为根节点的编号,没有父亲节点。
-
若2i+1[HTML_REMOVED]=n,没有左孩子。
-
若2i+2[HTML_REMOVED]=n,没有右孩子。
-
推导:
从上面的图片中的规律所示,我们能得到如下推导:
这是由层数n,也就是高度去推导节点个数,那么现在我们将这个过程倒过来,根据节点的个数去推导层数:如下图所示(假设一个满二叉树):
根据下面的图中编号很容易体会子节点和父节点之间的编号关系。
你写字好像我的一个同学牛某啊,哈哈