二叉数的遍历

Preorder traversal(中->左->右)

template<class T>

void PreOrder(BinaryNode<T>* t) // preorder traversal of *t.

{if(t)

{visit(t);

PreOrder(tàLeft);

PreOrder(tàRight);}

Inorder traversal(左->中->右)

//递归算法

template<class T>

void InOrder(BinaryNode<T>* t)

{if(t)

InOrder(tàLeft);

visit(t);

InOrder(tàRight);

//非递归算法

void Inorder(BinaryNode <T> * t)

Sack<BinaryNode<T>*> s(10);

BinaryNode<T> * p = t;

for ( ; ; )

while(p!=NULL)

s.push(p);

p = p->Left;

if (!s.IsEmpty( ))

p = s.pop( );

cout << p->element;

p = p->Right;

else

return

Postorder traversal(左->右->中)

//递归算法

template<class T>

void PostOrder(BinaryNode<T>* t)

if(t)

PostOrder(tàLeft);

PostOrder(tàRight);

visit(t)

//非递归算法

struct StkNode

BinaryNode <T> * ptr;

int tag;

vid Postorder(BinaryNode <T> * t)

Stack <StkNode<T>>s(10);

StkNode<T> Cnode;

BinaryNode<T> * p = t;

for( ; ; )

while (p!=NULL)

Cnode.ptr = p;

Cnode.tag = 0;

s.push(Cnode);

p = p->Left;

Cnode = s.pop( );

p = Cnode.ptr;

while ( Cnode.tag = = 1) //从右子树回来

cout << p->element;

if ( !s.IsEmpty( ))

Cnode = s.pop( );

p = Cnode.ptr;

else

return;

4)Cnode.tag = 1;

s.push(Cnode);

p = p->Right; //从左子树回来//for

Level order: it is a non-recursive function and a queue is used.

template<class T>

void LevelOrder(BinaryNode<T>* t)

LinkedQueue<BinaryNode<T>*> Q;

while(t)

visit(t); //visit t

if(tàLeft)

Q.Add(tàLeft);

if(tàRight)

Q.Add(tàRight);

try

Q.Delete(t);

}catch(OutOfBounds){return;}

· Preorder前序遍历--访问结点的操作发生在遍历其左右子树之前

· Inorder中序遍历--访问结点的操作发生在遍历其左右子树之间

· Postorder后序遍历--访问结点的操作发生在遍历其左右子树之后

· Level order层次遍历--按每一层的节点，从左到右逐次访问

在使用扩展先序遍历创建二叉树时，首先要根据一棵二叉树写出它的先序遍历序列，然后根据图中各个节点左右孩子的 状况进行加点遍历，凡是没有左右孩子的节点，遍历到它的左右孩子是都用"."表示它的左右孩子，注意这里面的"."只是用来表示它的父节点没有它这个左孩子或右孩子，并不表示节点，所以在遍历过程中应该访问到"."就结束了，不能再沿着"."继续遍历。

所谓遍历(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)

--访问根结点的操作发生在遍历其左右子树之后。

树的遍历是树的一种重要的运算。所谓遍历是指对树中所有结点的系统的访问，即依次对树中每个结点访问一次且仅访问一次。树的3种最重要的遍历方式分别称为前序遍历、中序遍历和后序遍历。以这3种方式遍历一棵树时，若按访问结点的先后次序将结点排列起来，就可分别得到树中所有结点的前序列表，中序列表和后序列表。相应的结点次序分别称为结点的前序、中序和后序。

树的这3种遍历方式可递归地定义如下:

§ 如果T是一棵空树，那么对T进行前序遍历、中序遍历和后序遍历都是空操作，得到的列表为空表。

§ 如果T是一棵单结点树，那么对T进行前序遍历、中序遍历和后序遍历都只访问这个结点。这个结点本身就是要得到的相应列表。

§ 否则，设T如图6所示，它以n为树根，树根的子树从左到右依次为T1,T2,..,Tk，那么有:

§ 对T进行前序遍历是先访问树根n,然后依次前序遍历T1,T2,..,Tk。

§ 对T进行中序遍历是先中序遍历T1，然后访问树根n，接着依次对T2,T2,..,Tk进行中序遍历。

§ 对T进行后序遍历是先依次对T1,T2,..,Tk进行后序遍历，最后访问树根n。

用二叉链表做为存储结构，先序遍历算法可描述为:

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\n",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 . .

运行结果: