【数据结构】第6章 树(上)
第一次用markdown…..好高端的赶脚 数据结构第6章 树(上)§6.1 树的定义和基本术语树是n(n>=0)个结点的有限集 在非空树中有且仅有一个特定的根(root) 树的结构定义是一个递归的定义,即在树的定义中又用到了树的概念,有嵌套集合表示法,广义表表示法和凹入表示法等。 术语: §6.2二叉树二叉树的定义二叉树是每个结点最多有两棵子树的有序树。 递归定义:二叉树或为空,或是由一个根结点加上两棵分别称为左子树和右子树的,互不相交的二叉树组成。 二叉树的性质①二叉树第i层最多有2^(i-1)个结点 关于③的证明如下: 一棵深度为k且有(2^k-1)个结点的二叉树称为满二叉树(也叫完美二叉树),编号和满二叉树编号相同但最后一层的最后几个结点可以缺失的二叉树称为完全二叉树。 除了叶子结点的所有结点都只有左(或右)孩子的二叉树称为斜二叉树(链) 二叉树的存储结构对于完全二叉树可以很好的用顺序结构储存。s[1]表示第1层(根) s[2 3]表示第二层…..s[2^(k-1)…2^k-1] 表示第k层 s[2^n…m]表示最后一层即可 §6.3遍历二叉树和线索二叉树遍历二叉树根据访问根结点的顺序,有 Tip:已知中序遍历和先序遍历 或 已知中序遍历和后序遍历一定可以唯一的确定一棵二叉树,但只知道先序和后序遍历可能无法确定一个二叉树。 先序,中序和后序遍历,所经过的路线实际上是一样的,这条路线上每一个结点都会经过三遍。三种遍历不同的是在第一次遇见结点就访问,还是第二次遇见结点访问,还是最后一次遇见结点访问。 下面是用递归做先序遍历的代码 /** 先序遍历递归算法 */
void PreOrderTraverse( BinTree T )
{
if(T) {
if(Visit(T -> data)) {//先访问根
if(PreOrderTraverse(T -> Left)) {//访问左子树
if(PreOrderTraverse(T -> Right)) return OK;//访问右子树并返回
}
}
return ERROR;
}else return OK;//空树
}
遍历也可以用非递归的方式而直接借助栈来进行,如下面的代码就是非递归解决中序遍历 /** 中序遍历非递归算法 */
void InOrderTraverse( BinTree BT )
{
BinTree T = BT;
Stack S = CreatStack( MaxSize ); /** 创建并初始化栈S */
while( T || !IsEmpty(S) ) { /** 树不空且栈不空 */
while(T) { /** 一直向左并将沿途结点压入栈 */
/** 此处为第一次遇到结点 在此处访问结点即为先序遍历 */
Push(S,T);
T = T -> Left;
}
if(!IsEmpty(S) ) {
T = Pop(S); /** 结点弹出栈 */
/** 此处为第二次遇到结点 在此处访问结点即为中序遍历 */
printf("%d",T->Data); /** 访问结点 */
T = T -> Right; /** 转向右子树 */
}
}
}
二叉树的层次遍历需要用到队列。代码如下 /** 二叉树的层序遍历 */
void LevelOrderTraverse(BinTree BT)
{
Queue Q;
BinTree T;
if(BT) {
Q = CreatQueue(MaxSize);
AddQ(Q,BT); //入队
while(!IsEmptyQ(Q)) {
T = DeleteQ(Q); //出队
printf("%dn",T->Data); /** 访问取出队列的结点 */
if(T -> Left) AddQ(Q,T->Left);
if(T -> Right) AddQ(Q,T->Right);
}
}
}
下面是一个递归求二叉树深度的Demo /** Demo 求二叉树的高度 */
int PostOrderGetHeight(BinTree BT)
{
int HL,HR,MaxH;
if(BT) {
HL = PostOrderGetHeight(BT -> Left);
HR = PostOrderGetHeight(BT -> Right);
MaxH = max(HL,HR);
return (MaxH+1);//树的深度=左右子树最大深度+1
}else return 0;
}
线索二叉树二叉树的遍历实际上对二叉树线性化的过程。线索二叉树把所有的结点串起来,所有应该为空的右孩子指针指向该节点在中序序列中的后继,所有应该为空的左孩子指针指向该节点的中序序列的前驱。简单来说就是左指针指向从哪里来,右指针指向向哪里去 下面是中序遍历建立中序线索化链表的代码 /** 中序遍历建立中序线索化链表 */
Status InorderThreading(BiThrTree & Thrt,BiThrTree T)
{
if(!(Thrt = (BiThrTree)malloc(sizeof(BiThrNode)))) exit(OVERFLOW);
Thrt -> LTag = Link;Thrt -> RTag = Thread;//建立头结点
Thrt -> rchild = Thrt;//右指针回指
if(!T) Thrt -> lchild = Thrt;//若二叉树空 则左指针回指
else {
Thrt -> lchild = T; pre = Thrt;
InThreading(T);//中序遍历进行线索化
pre -> rchild = Thrt; pre -> Rtag = Thread;//最后一个结点线索化
Thrt -> rchild = pre;
}
return OK;
}//InOrderThreading
void InThreading(BiThrTree p)
{
if(p) {
InThreading(p -> lchild);//左子树线索化
if(!p -> lchild) {p -> LTag = Thread;p -> lchild = pre;}//前驱搜索
if(!pre -> rchild) {pre -> RTag = Thread;pre -> rchild = p;}//后继搜索
pre = p;//保持pre指向p的前驱
InThreading(p -> rchild);//右子树线索化
}
}//InThreading
【第6章上完】 (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |