编程中树的遍历
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. 编程中的树的遍历分为哪三种
前序遍历
中序遍历
后序遍历
这是数据结构这门课程中关于树的知识，这章是很重要也很有意思的，能衍生出很多实际问题。