一．實驗要求
二叉樹的遍歷操作是樹形結構其他眾多操作的基礎。本實驗旨在使學生進一步加深對二叉樹的先序、中序和後序等三種遍歷次序特點的理解，熟悉二叉鏈表存儲結構，熟練掌握二叉樹上的遞歸算法的設計技術。
二．實驗題目
構造一棵二叉樹，使用二叉鏈表方式存儲，試設計程序，按照先序、中序、後序三種方式將這棵二叉樹遍歷出來，要求使用遞歸和非遞歸兩種實現方式。
三．實現提示
1．二叉樹的線性鏈表存儲數據結構：
[cpp]
typedef char elemtype;
typedef struct bitree{
elemtype data;
struct bitree *lchild,*rchild;
}BiTree;
2．二叉樹的構造方式（參考）：
[cpp]
BiTree *create()
{
BiTree *q[100]; //定義q數組作為隊列存放二叉鏈表中結點,100為最//大容量
BiTree *s; //二叉鏈表中的結點
BiTree *root ; //二叉鏈表的根指針
int front=1,rear=0; //定義隊列的頭、尾指針
char ch; //結點的data域值
root=NULL;
cin>>ch;
while(ch!='#') //輸入值為#號,算法結束
{ s=NULL;
if(ch!=',') //輸入數據不為逗號,表示不為虛結點,否則為虛結點
{ s=new BiTree;
s->data=ch;
s->lchild=NULL;
s->rchild=NULL;
}
rear++;
q[rear]=s; //新結點或虛結點進隊
if(rear==1)
root=s;
else
{ if((s!=NULL)&&(q[front]!=NULL))
{ if(rear%2==0)
q[front]->lchild=s; //rear為偶數,s為雙親左孩子
else
q[front]->rchild=s;//rear為奇數,s為雙親右孩子
}
if(rear%2==1) front++; //出隊
}
cin>>ch;
}
return root;
}
四．思考及選做
1．本實驗給出了建立二叉樹的二叉鏈表存儲結構的一種方法，是否還有更簡單的方法？
2．對於非遞歸先序遍歷一般需要對每個結點進行二次進棧，這就需要一個標志位，如何處理這個標志位，使得既不需要構造新的存儲結構也不需要增加一個新的標志棧。
五．我的實現
[cpp]
#include<stdio.h>
#include<stdlib.h>
#include <iostream>
#include<stack>
using namespace std;
/*******************數據結構的定義*************************/
typedef char elemtype;
typedef struct bitree
{
elemtype data;
struct bitree *lchild,*rchild;
}BiTree;
/**********************功能函數*******************************/
/*
建樹. 輸入格式為: a(b,c(d,e))
*/
BiTree *create(char *s,BiTree *&root)
{
int i;
bool isRight=false;
stack<BiTree*> s1; //用棧存放結點
stack<char> s2; //存放分隔符
BiTree *p,*temp;
root->data=s[0];
root->lchild=NULL;
root->rchild=NULL;
s1.push(root);
i=1;
while(i<strlen(s))
{
if(s[i]=='(')
{
s2.push(s[i]);
isRight=false;
}
else if(s[i]==',')
{
isRight=true;
}
else if(s[i]==')')
{
s1.pop();
s2.pop();
}
else if(isalpha(s[i]))
{
p=(BiTree *)malloc(sizeof(BiTree));
p->data=s[i];
p->lchild=NULL;
p->rchild=NULL;
temp=s1.top();
if(isRight==true)
{
temp->rchild=p;
cout<<temp->data<<"的右孩子是"<<s[i]<<endl;
}
else
{
temp->lchild=p;
cout<<temp->data<<"的左孩子是"<<s[i]<<endl;
}
if(s[i+1]=='(')
s1.push(p);
}
i++;
}
}
/*
遞歸打印函數 。
*/
void display(BiTree *root)
{
if(root!=NULL)
{
printf("%c",root->data);
if(root->lchild!=NULL)
{
printf("(");
display(root->lchild);
}
if(root->rchild!=NULL)
{
printf(",");
display(root->rchild);
printf(")");
}
}
}
/*
先序遍歷。遞歸 。
*/
void preOrder1(BiTree *root)
{
if(root!=NULL)
{
printf("%c ",root->data);
preOrder1(root->lchild);
preOrder1(root->rchild);
}
}
/*
先序遍歷。非遞歸 。
1)訪問結點P，並將結點P入棧;
2)判斷結點P的左孩子是否為空，若為空，則取棧頂結點並進行出棧操作，並將棧頂結點的右孩子置為當前的結點P，循環至1);若不為空，則將P的左孩子置為當前的結點P;
3)直到P為NULL並且棧為空，則遍歷結束。
*/
void preOrder2(BiTree *root)
{
stack<BiTree*> s; //也可以用數組來實現
BiTree *p=root;
while(p!=NULL||!s.empty())
{
while(p!=NULL)
{
cout<<p->data<<" ";
s.push(p);
p=p->lchild;
}
if(!s.empty())
{
p=s.top();
s.pop();
p=p->rchild;
}
}
}
/*
中序遍歷。遞歸。
*/
void inOrder1(BiTree *root)
{
if(root!=NULL)
{
inOrder1(root->lchild);
printf("%c ",root->data);
inOrder1(root->rchild);
}
}
/*
中序遍歷。非遞歸。
1)若其左孩子不為空，則將P入棧並將P的左孩子置為當前的P，然後對當前結點P再進行相同的處理；
2)若其左孩子為空，則取棧頂元素並進行出棧操作，訪問該棧頂結點，然後將當前的P置為棧頂結點的右孩子；
3)直到P為NULL並且棧為空則遍歷結束;
*/
void inOrder2(BiTree *root)
{
stack<BiTree*> s;
BiTree *p=root;
while(p!=NULL||!s.empty())
{
while(p!=NULL)
{
s.push(p);
p=p->lchild;
}
if(!s.empty())
{
p=s.top();
cout<<p->data<<" ";
s.pop();
p=p->rchild;
}
}
}
/*
後序遍歷 。遞歸。
*/
void postOrder1(BiTree *root)
{
if(root!=NULL)
{
postOrder1(root->lchild);
postOrder1(root->rchild);
printf("%c ",root->data);
}
}
/*
後序遍歷 。非遞歸。
要保證根結點在左孩子和右孩子訪問之後才能訪問，因此對於任一結點P，先將其入棧。
如果P不存在左孩子和右孩子，則可以直接訪問它；或者P存在左孩子或者右孩子，但
是其左孩子和右孩子都已被訪問過了，則同樣可以直接訪問該結點。若非上述兩種情況，
則將P的右孩子和左孩子依次入棧，這樣就保證了每次取棧頂元素的時候，左孩子在右孩
子前面被訪問，左孩子和右孩子都在根結點前面被訪問。
*/
void postOrder2(BiTree *root)
{
stack<BiTree*> s;
BiTree *cur; //當前結點
BiTree *pre=NULL; //前一次訪問的結點
s.push(root);
while(!s.empty())
{
cur=s.top();
if((cur->lchild==NULL&&cur->rchild==NULL)||
(pre!=NULL&&(pre==cur->lchild||pre==cur->rchild)))
{
cout<<cur->data<<" "; //如果當前結點沒有孩子結點或者孩子節點都已被訪問過
s.pop();
pre=cur;
} www.2cto.com
else
{
if(cur->rchild!=NULL)
s.push(cur->rchild);
if(cur->lchild!=NULL)
s.push(cur->lchild);
}
}
}
/***********************main函數*************************/
int main()
{
char s[100];
while((scanf("%s",s)))
{
BiTree *root=(BiTree *)malloc(sizeof(BiTree));
create(s,root);
printf("\n");
printf("先序遞歸遍歷:");
preOrder1(root);
printf("\n");
printf("中序遞歸遍歷:");
inOrder1(root);
printf("\n");
printf("後序遞歸遍歷:");
postOrder1(root);
printf("\n");
printf("\n");
printf("先序非遞歸遍歷:");
preOrder2(root);
printf("\n");
printf("中序非遞歸遍歷:");
inOrder2(root);
printf("\n");
printf("後序非遞歸遍歷:");
postOrder2(root);
printf("\n\n");
}
return 0;
}
