前言
现在感觉自己基础太差了, 需要要补一下基础了。于是学习王道数据结构分析非常详细。
正文
树与二叉树
一, 树的基本术语
- 树中一个结点的子结点个数称为该结点的度, 树中结点的最大度数称为树的度。如结点B的度为2,结点D的度为3,树的度为3.
- 度大于0的结点称为分支结点(又称非终端结点),度为0(没有子女结点)的结点称为叶子结点(又称终端结点)。在分支结点中,每个结点的分支数就是该结点的度。
- 结点的深度,高度和层次。
二, 树的性质
- 树中的结点数等于所有结点的度数加1。
- 度为m的树中第i层上至多有m^(i-1)个结点(i>=0)。
- 高度为h的m叉树至多有(m^h-1)/(m-1)个结点。
- 具有n个结点的m叉树的最小高度为[log m(n(m-1)+1)]。
三, 二叉树的概念
1, 几种特殊的二叉树
- 满二叉树。一颗高度为h。且含有2^h - 1个结点的二叉树称为满二叉树,即树中的每层都含有最多的结点,上图所示。满二叉树的叶子结点都集中在二叉树的最下一层,并且除叶子结点之外的每个结点度数均为2。
可以对满二叉树按层续编号:约定编号从跟结点(跟结点编号为1)起,自上而下,自左而右。这样,每个结点对应一个编号,对于编号为i的结点,若有双亲,则其双亲为[i/2],若有左孩子,则左孩子为2i; 若有右孩子,则右孩子为2i+1。
- 完全二叉树。设一个高度为h,有n个结点的二叉树,当且仅当其每个结点都与高度为h的满二叉树中编号为1到n的结点一一对应时,称为完全二叉树,如上图。这种树的特点如下:
①. 如i<[i/2]，则结点i为分支结点,否则为叶子结点。
②. 叶子节点只可能在层次最大的两层上出现。对于最大层次中的叶子结点,都依赖排列在该层最左边的位置上。
③. 若有度为1的结点,则只可能有一个,且该结点只有左孩子而无右孩子。
④. 按层序编号后,一旦出现某个结点(编号为i)为叶子结点或只有左孩子, 则编号大于i的结点均为叶子结点。
⑤. 若n为奇数,则每个分支结点都有左子女和右子女; 若n为二数,则编号最大的分支结点(编号为n/2)只有左子女,没有右子女,其中分支结点左,右子女都有。
2, 二叉树的性质
- 非空二叉树上的叶子结点数等于度为2的结点数加1,即n0 = n2 + 1。
- 非空二叉树上第k层上至多有2^k-1结点(k>=1)。
- 高度为h的二叉树至多有2^h-1个结点(h>=1)。
- 对于完全二叉树按从上到下
-
具有n个(n>0)结点的完全二叉树的高度为[log2(n+1)]或者[ log2n +1]。
四, 二叉树的四种遍历和线索二叉树
1, 二叉树的四种遍历
所谓二叉树的遍历,是指按某条搜索路径访问树中的每个结点,使得每个结点均被服务一次,而且仅被访问一次。
由二叉树的递归定义可知,遍历一颗二叉树便要决定根结点N,左子树L和右子树R的访问顺序。按照先遍历左子树再遍历右子树的原则,常见的遍历次序有先序(NLR),中序(LNR),和后序(LRN)三种遍历算法,其中”序”指的是根结点再何时被访问。
① 先序遍历
先序遍历(preorder)的操作过程如下:
若二叉树为空,则什么也不做,否则,
1) 访问根结点; 2) 先序遍历左子树; 3) 先序遍历右子树；
对应的递归算法如下:
void preorder(BiTree T)
{
if (T)
{
//访问根结点
show(T);
//递归遍历左子树
preorder(T->lchild);
//递归遍历右子树
preorder(T->rchild);
}
}
如上图所示, 先序遍历所得的结点序列为 1, 2, 4, 8, 9, 5, 10, 11, 3, 6, 12, 13, 7, 14, 15
② 中序遍历
中序遍历(inorder)的操作过程如下: 若二叉树为空，则什么也不做，否则:
1) 中序遍历左子树， 2) 访问根结点 3) 中序遍历右子树
对应的递归算法如下:
void inorder(BiTree T)
{
if (T)
{
// 递归遍历左子树
inorder(T->lchild);
//访问根结点
show(T);
// 递归遍历右子树
inorder(T->rchild);
}
}
对应上图二叉树, 中序遍历所得到的结点序列为 8, 4, 9, 2, 10, 5, 11, 1, 12, 6, 13, 3, 14, 15, 7
③ 后序遍历
后序遍历(postorder)的操作过程如下 若二叉树为空，则什么也不做；否则
1) 后序遍历左子树 2) 后序遍历右子树 3) 访问根结点
对应的递归算法如下
void postorder(BiTree T)
{
if (T)
{
//递归遍历左子树
postorder(T->lchild);
// 递归遍历右子树
postorder(T->rchild);
//访问根结点
show(T);
}
}
对应上图二叉树 :后序遍历得到的结点序列为 8, 9, 4, 10, 11, 5, 2, 12, 13, 6, 14, 15, 7, 3, 1
总结三种遍历算法中,递归遍历左,右子树的顺序都是固定的, 只是访问根结点的顺序不同。不管采用哪种遍历算法,每个结点都访问一次且仅访问一次,故时间复杂度都是O(n)。在递归遍历中,递归工作栈的栈深恰好为树的深度,所以在再坏情况下,二叉树是有n个结点且深度为n的单支树,遍历算法的空间复杂度为O(n)。
④ 递归算法和非递归算法的转换
借助栈,可以将二叉树的递归遍历算法转换为非递归算法。下面以中序遍历为列子给出中序遍历的非递归算法。先扫描(并非访问)根结点的所有左结点并将它们一一进栈,然后出栈一个结点p(显然结点p没有左孩子结点或者左孩子结点已经被访问过),访问它。然后扫描该结点的右孩子结点,将其进栈,再扫描该右孩子结点的所有左结点并一一进栈,如此继续,直到栈空为止。
中序遍历的非递归算法如下:
void inorder2(BiTree T)
{
//初始化栈
initstatck(s);
//p是遍历指针
TiTree p = T;
// 栈不空或者p不空时循环
while (p || !s.emptr())
{
if (p)
{
//根指针进栈,遍历左子树
s.push(p);
//每遇到非空二叉树先向左走
p = p->lchild;
}
else
{
// 根指针退栈， 访问根结点，遍历右子树
//退栈， 访问根结点
s.pop(p);
show(p);
// 再向右子树走
p = p->rchild;
}
}
}
后序遍历算法如下
void postorder2(BiTree T)
{
if (T)
{
s.push(T);
BiTree p = NULL;
while (!s.empty())
{
p = s.top();
// 判断当前lcheild和rchild是否已经再栈中
if (p->lchild && p->lchild != T && p->rchild != T)
{
s.push(p);
}
else if (p->rchild && p->rchild != T)
{
s.push(p);
}
else
{
s.pop(p);
show(p);
T = p;
}
}
}
}
再写非递归遍历时要有递归压栈的模型 来使用栈的数据结构
⑤ 层次遍历
如上图所示为二叉树的层次遍历,即按照箭头所指方向,按照1, 2, 3, 4 层次顺序,对二叉树中的各个结点进行访问。
要进行层次遍历,需要借助一个队列。先将二叉树根结点入队,然后出队,访问该结点,若它有左子树,则将左子树根结点入队,如它有右子树,则将右子树根结点入队。然后出队,对出队结点访问,如此反复,直到队列为空。
二叉树的层次遍历算法如下
void level_order(BiTree T)
{
initqueue(q);
BiTree p;
//将根结点入队列中
q.endqueue(T);
//队列不空循环
while (!q.empty())
{
//队头元素出队
q.dequeue(p);
show(p);
if (p->lchild)
{
//左子树不空,则左子树入队列
q.endqueue(p->lchild);
}
if (p->rchild)
{
//右子树不空, 则右子树入队列
q.endqueue(p->rchild);
}
}
}
五, 树与二叉树的应用
1, 平衡二叉树
① 平衡二叉树的定义
为避免树的高度增长过快,降低二叉排序树的性能, 我们规定在插入和删除二叉树的结点的时, 要保证任意结点的左, 右子树高度差的绝对不超过1, 将这样的二叉树称为平衡二叉树(Balanced Binary Tree), 简称平衡树(AVL)。定义结点左子树和右子树的高度差为该结点的平衡因子,则平衡二叉树结点的平衡因子的值只可能是-1, 0或1。 因此,平衡二叉树可定义的为或者是一颗空树, 或者是具有下列性质的二叉树; 它的左子树和右子树都是平衡二叉树,且左子树和右子树的高度差的绝对值不超过1。如上图a所示 ,是平衡二叉树，如上图b所示是不平衡二叉树。结点种的值为该结点的平衡因子。
② 平衡二叉树的插入
二叉排序树保证平衡的基本思想如下:每当在二叉排序树种插入(或删除)一个结点时,首先检查其插入路径上的结点因为此次操作而导致了不平衡。若导致了不平衡,在保持二叉排序树特性的前提下,调整各结点的位置关系,使之重新达到平衡。
注意:每次调整的对象都是最小的不平衡子树,即以插入路径上离插入结点最近的平衡因子的绝对值大于1的结点作为根的子树。如上图所示框的为最小不平衡子树。
平衡二叉树的插入过程的前半部分与二叉排序树相同,但在新结点插入后,若造成查找路径上的某个结点不再平衡,则需要做出相应的调整。一般可将失去平衡后进行调整的规律归纳为下列4种情况:
1, LL平衡旋转(右单旋转)
由于在结点A的左孩子(L)的左子树(L)上插入了新的结点,A的平衡因子由1曾至2, 导致以A为根的子树失去平衡, 需要一次向右的旋转操作。将A的左孩子B向右上旋转代替A成为根结点,将A结点向右下旋转成为B的右子树的根结点,而B的原右子树则作为A结点的左子树。
2, RR平衡旋转(左单旋转)
由于在结点A的右孩子(R)的右子树(R)上插入了新结点,A的平衡因子由-1减至-2,导致以A为根的子树失去平衡,需要一次向左的旋转操作。将A的右孩子B向左上旋转替代A成为根结点,将A结点向左下旋转成为B的左子树的根结点,而B的原右子树则作为A结点的右子树，
3, LR平衡旋转(先左后右双旋转)
由于在A的左孩子(L)的右子树(R)上插入新的结点,A的平衡因子由1曾至2,导致以A为根的子树失去平衡,需要进行二次旋转操作,先左旋转后右旋转。先将A结点的左孩子B的右子树的根结点C向左上旋转提升到B结点的位置，然后再把该C结点向右上旋转提升到A结点的位置。
4, RL平衡旋转(先右后左双旋转)
由于在A的右孩子(R)的左子树(L)上插入新的结点,A的平衡因子由-1减至-2,导致以A为根的子树失去平衡，需要进行二次旋转操作,先右旋转后左旋转。先将A结点的右孩子B的左子树的根结点C向右上旋转提升到B结点的位置,然后再把该结点向左上旋转提升到A结点的位置。
