編程中樹的遍歷

1. 二叉樹遍歷程序

二叉樹的遍歷有3種方式：

a
/ \
/ \
b e
/ \ \
/ \ \
c d f

（先序）先根遍歷：（根左右）先訪問根，再訪問左子樹，最後訪問右子樹，則可得如下的序列：abcdef

（中序）中根遍歷：（左根右）先訪問左子樹，再訪問根，最後訪問右子樹，則可得如下的序列：cbdaef

（後序）後根遍歷：（左右根）先訪問左子樹，再訪問右子樹，最後訪問根，則可得如下的序列：cdbfea

本文給出二叉樹先序、中序、後序三種遍歷的非遞歸演算法，此三個演算法可視為標准演算法。

1.先序遍歷非遞歸演算法
#define maxsize 100
typedef struct
{
Bitree Elem[maxsize];
int top;
}SqStack;

void PreOrderUnrec(Bitree t)
{
SqStack s;
StackInit(s);
p=t;

while (p!=null || !StackEmpty(s))
{
while (p!=null) //遍歷左子樹
{
visite(p->data);
push(s,p);
p=p->lchild;
}//endwhile

if (!StackEmpty(s)) //通過下一次循環中的內嵌while實現右子樹遍歷
{
p=pop(s);
p=p->rchild;
}//endif

}//endwhile

}//PreOrderUnrec

2.中序遍歷非遞歸演算法
#define maxsize 100
typedef struct
{
Bitree Elem[maxsize];
int top;
}SqStack;

void InOrderUnrec(Bitree t)
{
SqStack s;
StackInit(s);
p=t;
while (p!=null || !StackEmpty(s))
{
while (p!=null) //遍歷左子樹
{
push(s,p);
p=p->lchild;
}//endwhile

if (!StackEmpty(s))
{
p=pop(s);
visite(p->data); //訪問根結點
p=p->rchild; //通過下一次循環實現右子樹遍歷
}//endif

}//endwhile

}//InOrderUnrec

3.後序遍歷非遞歸演算法
#define maxsize 100
typedef enum{L,R} tagtype;
typedef struct
{
Bitree ptr;
tagtype tag;
}stacknode;

typedef struct
{
stacknode Elem[maxsize];
int top;
}SqStack;

void PostOrderUnrec(Bitree t)
{
SqStack s;
stacknode x;
StackInit(s);
p=t;

do
{
while (p!=null) //遍歷左子樹
{
x.ptr = p;
x.tag = L; //標記為左子樹
push(s,x);
p=p->lchild;
}

while (!StackEmpty(s) && s.Elem[s.top].tag==R)
{
x = pop(s);
p = x.ptr;
visite(p->data); //tag為R，表示右子樹訪問完畢，故訪問根結點
}

if (!StackEmpty(s))
{
s.Elem[s.top].tag =R; //遍歷右子樹
p=s.Elem[s.top].ptr->rchild;
}
}while (!StackEmpty(s));
}//PostOrderUnrec

2. c語言編程實現二叉樹的三種遍歷演算法 並針對一個二叉樹列出三種遍歷序列。功能要求：實現三種遍歷演算法、

#include<stdio.h>
#include<malloc.h>

typedefstructBTree{
chardata;
structBTree*lChild;
structBTree*rChild;
}BinTree;

BinTree*CreateTree(BinTree*p){
charch;
scanf("%c",&ch);
if(ch=='#')returnNULL;
p=(BinTree*)malloc(sizeof(BinTree));
p->data=ch;
p->lChild=CreateTree(p->lChild);
p->rChild=CreateTree(p->rChild);
returnp;
}

intSumLeaf(BinTree*T){
intsum=0,m,n;
if(T){
if((!T->lChild)&&(!T->rChild))
sum++;
m=SumLeaf(T->lChild);
n=SumLeaf(T->rChild);
sum+=m+n;
}
returnsum;
}

voidQianXu(BinTree*T){
if(T){
printf("%c,",T->data);
QianXu(T->lChild);
QianXu(T->rChild);
}
}

voidZhongXu(BinTree*T){
if(T){
ZhongXu(T->lChild);
printf("%c,",T->data);
ZhongXu(T->rChild);
}
}

voidHouXu(BinTree*T){
if(T){
HouXu(T->lChild);
HouXu(T->rChild);
printf("%c,",T->data);
}
}

intDepth(BinTree*T){
intdep=0,depl,depr;
if(!T)dep=0;
else{
depl=Depth(T->lChild);
depr=Depth(T->rChild);
dep=1+(depl>depr?depl:depr);
}
returndep;
}

voidFreeTree(BinTree*T){
if(T){
FreeTree(T->lChild);
FreeTree(T->rChild);
free(T);
}
}

intmain(){
BinTree*Tree=NULL;
Tree=CreateTree(Tree);
//前序遍歷
printf("QianXuTraversal:");
QianXu(Tree);
printf("
ZhongXuTraversal:");
ZhongXu(Tree);
printf("
HouXuTraversal:");
HouXu(Tree);

printf("
Leaf'snumber:%d
",SumLeaf(Tree));
printf("Tree'sDepth:%d",Depth(Tree));

FreeTree(Tree);
return0;
}

輸入:#ABCD###E##FG#H##I#J##
輸出:

3. c語言中的二叉樹用循環語句編程完成遍歷

void PrintTree(Node* tree)
{
printf(tree->value);
if (tree.left != NULL) PrintTree(tree.left);
if (tree.right != NULL) PrintTree(tree.right);
}

用根指針調用這個函數就可以了

4. 編程中的樹的遍歷分為哪3種

中序遍歷，前序遍歷，後序遍歷.

5. 數據結構編程：二叉樹的遍歷

發給你了注意查收
[email protected]

6. 二叉樹遍歷的程序

#include<iostream>
using namespace std;

typedef struct BinaryTree
{
char data;
struct BinaryTree *lchild,*rchild;
}BinaryTree,*BiTree;

void CreateBiTree(BiTree &T)
{
char z;
if((z=getchar())==' ')
T=NULL;
else
{
T=(BinaryTree*)malloc(sizeof(BinaryTree));
T->data=z;
CreateBiTree(T->lchild);
CreateBiTree(T->rchild);
}
}
//先序遍歷
void preBiTree(BiTree T)
{
if(T!=NULL)
{
cout<<T->data;
preBiTree(T->lchild);
preBiTree(T->rchild);
}
}
//中序遍歷
void InBiTree(BiTree T)
{
if(T!=NULL)
{
InBiTree(T->lchild);
cout<<T->data;
InBiTree(T->rchild);
}
}
//後序遍歷
void PostBiTree(BiTree T)
{
if(T!=NULL)
{
PostBiTree(T->lchild);
PostBiTree(T->rchild);
cout<<T->data;
}
}
int Depth(BiTree T)
{
if(T==NULL)
{
return 0;
}
else
return 1+(Depth(T->lchild)>Depth(T->rchild)? Depth(T->lchild):Depth(T->rchild));
}

void main()
{
BiTree T;
cout<<"請輸入相應二叉樹:"<<endl;
CreateBiTree(T);
cout<<"二叉樹的先序遍歷為:"<<endl;
preBiTree(T);
cout<<endl;
cout<<"二叉樹的中序遍歷為:"<<endl;
InBiTree(T);
cout<<endl;
cout<<"二叉樹的後序遍歷為:"<<endl;
PostBiTree(T);
cout<<endl;
cout<<"二叉樹的深度為:"<<endl;
cout<<Depth(T)<<endl;
}

7. 編程中的樹的遍歷分為哪三種

前序遍歷
中序遍歷
後序遍歷

這是數據結構這門課程中關於樹的知識，這章是很重要也很有意思的，能衍生出很多實際問題。