标题:考研求救!!!
只看楼主
wufangchen
Rank: 1
等 级:新手上路
帖 子:7
专家分:0
注 册:2005-10-22
 问题点数:0 回复次数:2 
考研求救!!!

我想问大家一个问题啊,就是二叉树的前,中,后序线索是怎么做?那中序是要找结点的前驱和后继?其他两个呢?

搜索更多相关主题的帖子: 考研 
2005-12-14 19:51
hlstone
Rank: 1
等 级:新手上路
帖 子:9
专家分:0
注 册:2005-12-13
得分:0 

#include <iostream.h>
#include <malloc.h>
#include <iomanip.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define length 50
typedef struct BiTNode{
char data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
int CreateBiTree(BiTree &BT) //先序次序输入二叉树中节点的值,空格表示空树
{
char ch;
cin>>ch;
if (ch== '/') BT=NULL;
else
{
BT=(BiTNode *)malloc(sizeof(BiTNode)); //构造新结点
BT->data=ch;
CreateBiTree(BT->lchild); //构造左子树
CreateBiTree(BT->rchild); //构造右子树
}
return OK;
}
//先序遍历
void PreTraverse(BiTree BT)
{
if(BT!=NULL)
{
cout<<BT->data;
PreTraverse(BT->lchild);
PreTraverse(BT->rchild);
}
}
// 中序遍历
void InTraverse(BiTree BT){
if (BT!=NULL){
InTraverse(BT->lchild);
cout<<BT->data;
InTraverse(BT->rchild);
}
}
//后序遍历
void LastTraverse(BiTree BT){
if (BT!=NULL){
LastTraverse(BT->lchild);
LastTraverse(BT->rchild);
cout<<BT->data;
}
}
//层次遍历
void LevelTraverse(BiTree BT){
BiTree array[length],pos;
int front,end; //头尾指针
array[1]=BT;
front=end=1;
while (front<=end){ //出队
pos=array[front];
front++;
cout<<pos->data<<" ";
if(pos->lchild!=NULL)
{
end++;
array[end]=pos->lchild;
}
if(pos->rchild!=NULL)
{
end++;
array[end]=pos->rchild;
}
}
}

//计算节点数目
void Node(BiTree BT,int *count1){
if(BT){
(*count1)++;
Node(BT->lchild,count1);
Node(BT->rchild,count1);
}
}
//计算叶子节点数目
void Leaf(BiTree BT,int *count2)
{
if (BT)
{
Leaf(BT->lchild,count2);
if (BT->lchild==NULL && BT->rchild==NULL)
(*count2)++;
Leaf(BT->rchild,count2);
}
}
//计算二叉树的高度,其中h1和h2分别是以BT为根的左右子树的高度
int hight(BiTree BT)
{
int h1=0,h2=0;
if (BT==NULL)
return ERROR;
else
{
h1=hight(BT->lchild);
h2=hight(BT->rchild);
if(h1<h2)
{
int c=h1;
h1=h2;
h2=c;
}
h1++;
}
return h1;
}
//交换左右二叉数
void Change_Left_Right(BiTree BT)
{
if(BT)
{
Change_Left_Right(BT->lchild);
Change_Left_Right(BT->rchild);
BiTree k=BT->lchild;
BT->lchild=BT->rchild;
BT->rchild=k;
}
}
void main()
{
int x=0;
int count1=0,count2=0;
BiTree BT;
cout<<"please input the value of node"<<endl;
CreateBiTree(BT);
if(BT==NULL)
cout<<"The BiTree is Empty."<<endl;
else{
cout<<"先序遍历为"<<endl;
PreTraverse(BT);
cout<<endl;

cout<<"中序遍历为"<<endl;
InTraverse(BT);
cout<<endl;

cout<<"后序遍历为"<<endl;
LastTraverse(BT);
cout<<endl;

cout<<"层次遍历为:"<<endl;
LevelTraverse(BT);
cout<<endl;

//交换左右二叉数
Change_Left_Right(BT);
cout<<"交换左右二叉数后先序遍历为"<<endl;
cout<<BT->data;
PreTraverse(BT->lchild);
PreTraverse(BT->rchild);

Node(BT,&count1);
cout<<"节点个数为:"<<count1<<endl;

Leaf(BT,&count2);
cout<<"叶子结点个数:"<<count2<<endl;

cout<<"二叉树高度:"<<hight(BT)<<endl;

}
}

2005-12-14 22:36
hlstone
Rank: 1
等 级:新手上路
帖 子:9
专家分:0
注 册:2005-12-13
得分:0 

不懂的再问我
82172087

2005-12-14 22:41



参与讨论请移步原网站贴子:https://bbs.bccn.net/thread-38173-1-1.html




关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.303368 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved