扩展先序遍历序列
扩展先序遍历序列
扩展先序遍历序列是大学计算机基础课程《数据结构与算法 C语言描述》中的内容,在其中的树这一节中,详细地介绍了二叉树的先序遍历二叉树、中序遍历二叉树、后序遍历二叉树的方法,对于一个给定的二叉树,用上述三种方法遍历此二叉树得到的序列是唯一的,也是一一对应的;但是为了在程序中更有效和直观地创建一棵二叉树,可以使用:层次遍历和扩展先序遍历进行创建二叉树。
内容简介
在使用扩展先序遍历创建二叉树时,首先要根据一棵二叉树写出它的先序遍历序列,然后根据图中各个节点左右孩子的 状况进行加点遍历,凡是没有左右孩子的节点,遍历到它的左右孩子是都用“.”表示它的左右孩子,注意这里面的“.”只是用来表示它的父节点没有它这个左孩子或右孩子,并不表示节点,所以在遍历过程中应该访问到“.”就结束了,不能再沿着“.”继续遍历。
基本内容
所谓遍历(Traversal)是指沿着某条搜索路线,依次对树中每个结点均做一次且仅做一次访问。访问结点所做的操作依赖于具体的应用问 题。 遍历是二叉树上最重要的运算之一,是二叉树上进行其它运算之基础。本节主要讲二叉树中遍历过程,遍历方法,重点介绍扩展先序遍历序列以及利用此序列创建二叉树的过程,顺便比较一下各种遍历方法的异同和应用。
一、先序遍历
从二叉树的递归定义可知,一棵非空的二叉树由根结点及左、右子树这三个基本部分组成。因此,在任一给定结点上,可以按某种次序执行三个操作:
(1)访问结点本身(N),
(2)遍历该结点的左子树(L),
(3)遍历该结点的右子树(R)。
根据遍历的原则:先左后右,对于先序遍历,顾名思义就是先访问根节点,再访问左子树,最后访问右子树,
二、中序遍历
从二叉树的递归定义可知,一棵非空的二叉树由根结点及左、右子树这三个基本部分组成。因此,在任一给定结点上,可以按某种次序执行三个操作:
(1)遍历该结点的左子树(L),
(2)访问结点本身(N),
(3)遍历该结点的右子树(R)。
对于中序遍历,就是先访问左子树,再访问根节点,最后访问右子树;
三、后序遍历
从二叉树的递归定义可知,一棵非空的二叉树由根结点及左、右子树这三个基本部分组成。因此,在任一给定结点上,可以按某种次序执行三个操作:
(1)遍历该结点的左子树(L),
(2)遍历该结点的右子树(R)。
(3)访问结点本身(N),
对于后序遍历,就是先访问左子树,再访问右子树,最后访问根节点;
遍历的命名
根据访问结点操作发生位置命名:
① NLR:前序遍历(PreorderTraversal亦称(先序遍历))
——访问根结点的操作发生在遍历其左右子树之前。
② LNR:中序遍历(InorderTraversal)
——访问根结点的操作发生在遍历其左右子树之中(间)。
③ LRN:后序遍历(PostorderTraversal)
——访问根结点的操作发生在遍历其左右子树之后。
算法实现
先序遍历的算法实现
用二叉链表做为存储结构,先序遍历算法可描述为:
void InOrder(BinTree T)
{ //算法里①~⑥是为了说明执行过程加入的标号
① if(T) { // 如果二叉树非空
② printf("%c",T->data); // 访问结点 ③ InOrder(T->lchild); ④ InOrder(T->rchild); ⑤ }
⑥ } // InOrder
扩展先序遍历法创建二叉树算法实现
void createBiTree(BiTree *bt){
char ch;
ch = getchar();
if(ch == ''.'')
*bt = NULL;
else{
*bt = (BiTree)malloc(sizeof(BiTNode));//向内存申请节点空间
(*bt)->data = ch;
createBiTree(&((*bt)->LChild));//生成左子树
createBiTree(&((*bt)->RChild));//生成右子树
}
}/*createBiTree*/
打印二叉树算法实现
/*==================打印二叉树=============*/
void printTree(BiTree bt,int nLayer){
int i;
if(bt == NULL)
return ;
printTree(bt ->RChild,nLayer+1);
for(i=0;i<nLayer;i++)
printf(" ");
printf("%c\",bt->data);
printTree(bt->LChild,nLayer+1);
}
输入示例
图一:扩展先序遍历序列:
(a)1 2 4 . 6 . . . 3 . 5 . 7 . 8 . .
(b)1 2 4 . . 5 . . 3 6 . . 7 . .
图二:
扩展先序遍历序列:
(a)7 3 1 . . 2 . . 9 . 10 . 8 . 4 . .
(b)7 3 1 . . 5 4 . . . 11 10 . . 15 . .