扩展先序遍历

内容简介(基本内容 一、先序遍历 二、中序遍历 三、后序遍历 遍历的命名)

算法实现(先序遍历的算法实现 扩展先序遍历法创建二叉树算法实现 打印二叉树算法实现 输入示例 扩展先序遍历序列： 扩展先序遍历序列：)

扩展先序遍历

扩展先序遍历是大学计算机基础课程《数据结构与算法 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 . .

运行结果：