二叉树的遍历的完整代码是什么

Question

如题所述

Answer 1

二叉树遍历代码
#include"iostream.h"
#include"stdlib.h"
#include"stdio.h"
#include<stack>
using namespace std;
#define NULL 0
#define OK 1
#define OVERFLOW -1
typedef int Status;
typedef struct node
{
char data;
struct node *lchild;
struct node *rchild;
}*bitree;
int k=0;
int depth(bitree T)//树的高度
{
if(!T)return 0;
else
{
int m=depth(T->lchild); int n=depth(T->rchild); return (m>n?m:n)+1;
}
}
//先序，中序 建树
struct node *create(char *pre,char *ord,int n) {
struct node * T;
int m;
T=NULL;
if(n<=0)
{
return NULL;
}
else
{
m=0;
T=new(struct node);
T->data=*pre;
T->lchild=T->rchild=NULL; while(ord[m]!=*pre)
m++;
T->lchild=create(pre+1,ord,m);
T->rchild=create (pre+m+1,ord+m+1,n-m-1); return T;
}
}
//中序递归遍历
void inorder(struct node *T)
{
if(!T)
return;
else
{
inorder(T->lchild );
cout<<T->data;
inorder(T->rchild );
}
}
void inpre(struct node *T)
{
if(!T)
return;
else
{
cout<<T->data;
inpre(T->lchild );
inpre(T->rchild );

}
}
void postorder(struct node *T)
{
if(!T)
return;
else
{

postorder (T->lchild );
postorder (T->rchild );
cout<<T->data;

}
}
//先序非递归遍历
void inpre1(struct node *T)
第2/4页
{
struct node *p;
struct node *stack[20];
int top=0;
p=T;
cout<<"非递归先序为:"<<endl;
while(p||top!=0)
{
while (p)
{
stack[top++]=p;
cout<<p->data;
p=p->lchild;
}
p=stack[--top];

p=p->rchild ;
}
}
//中序非递归遍历
void inorder1(struct node *T)
{
struct node *p;
struct node *stack[20];
int top=0;
p=T;
cout<<"非递归中序为:"<<endl;
while(p||top!=0)
{
while (p)
{
stack[top++]=p;
p=p->lchild ;
}
p=stack[--top];
cout<<p->data;
p=p->rchild ;
}
}
//主函数
int main()
{
bitree T;
char pre[30],ord[30];
第3/4页
int n,m;
cout<<"请输入先序为-+a*b%cd/ef的二叉树:"<<endl; gets(pre);
cout<<"请输入中序为a+b*c%d-e/f的二叉树:"<<endl; gets(ord);
n=strlen(pre);
T=create(pre,ord,n);
cout<< "后序遍历为:"<<endl;
postorder (T);
cout<<endl;
inpre1(T);
cout<<endl;
inorder1(T);
cout<<endl;
m=depth(T);
cout<<"二叉树高度为："<<m<<endl;
return 0;
}

Answer 2

#include<iostream.h>
typedef struct node{
char data;
struct node* lchild;
struct node* rchild;
}bnode;

class Bitree{
public:
~Bitree(){delete_tree(T);}
bnode*get_root(){return T;}
void preorder(){preorder(T);cout<<endl;} //先序
void inorder(){inorder(T);cout<<endl;} //中序
void postorder(){postorder(T);cout<<endl;}//后序
private:
bnode *T;
void preorder(bnode*t);
void inorder(bnode*t);
void postorder(bnode*t);
void delete_tree(bnode*&t);
};

void Bitree::preorder(bnode*t){
if(t!=NULL){
cout<<t->data<<" ";
preorder(t->lchild);
preorder(t->rchild);
}
}
void Bitree::inorder(bnode*t){
if(t!=NULL){
inorder(t->lchild);
cout<<t->data<<" ";
inorder(t->rchild);
}
}
void Bitree::postorder(bnode*t){
if(t!=NULL){
postorder(t->lchild);
postorder(t->rchild);
cout<<t->data<<" ";
}
}
void Bitree::delete_tree(bnode*&t){
if(t!=NULL){
delete_tree(t->lchild);
delete_tree(t->rchild);
delete t;
}
}

void create(bnode* &t){ //先序建立二叉树
char x;
cin>>x;
if(x=='.')t=NULL;
else{
t=new bnode;
t->data=x;
create(t->lchild);
create(t->rchild);
}
}
void main(){
cout<<"请输入正确的二叉树先序序列(点表示左(右)孩子为空)\n(如：A B I C . . F . . J D . . E . . G H . . . )：";
Bitree tree1;
create(tree1.get_root());
cout<<"先序遍历：";
tree1.preorder();
cout<<"中序遍历：";
tree1.inorder();
cout<<"后序遍历：";
tree1.postorder();
}本回答被提问者和网友采纳

Answer 3