C-在用先序遍历建立二叉树,以下方法一中用指针函数来实现不行,为什么?

C-在用先序遍历建立二叉树,以下方法一中用指针函数来实现不行,为什么?

瑾兮 发布于 2016-10-15 字数 8897 浏览 1259 回复 1
//..........二叉树...........
#include <iostream>
using namespace std;

#define MAXSIZE 100
typedef char TElemType;
#define NULL 0
#define OK 1

typedef struct BiThrNode
{
TElemType data;
struct BiThrNode *lchild,*rchild;
int lTag,rTag;
}BiThrNode,*BiThrTree;

//........二叉树功能系统.........
void print()
{
cout<<"t****************Welcome To You*******************"<<endl;

cout<<"t* 1.先序遍历建立二叉树 *"<<endl;
cout<<"t* 2. 先 序 遍 历 *"<<endl;
cout<<"t* 3. 中 序 遍 历 *"<<endl;
cout<<"t* 4. 后 序 遍 历 *"<<endl;
cout<<"t* 5. 复 制 二 叉 树 *"<<endl;
cout<<"t* 6. 计算二叉树的深度 *"<<endl;
cout<<"t* 7.统计二叉树中结点的个数 *"<<endl;
cout<<"t* 8.统计二叉树页子结点的个数 *"<<endl;
cout<<"t* 9.统计二叉树中度为1结点的个数 *"<<endl;
cout<<"t* 10.统计二叉树中度为2结点的个数 *"<<endl;
cout<<"t* 11.前 序 线 索 二 叉 树 *"<<endl;
cout<<"t* 12.中 序 线 索 二 叉 树 *"<<endl;
cout<<"t* 13.后 序 线 索 二 叉 树 *"<<endl;
cout<<"t* 0. 退 出 程 序 *"<<endl;

cout<<"t********************Good-Bye*********************"<<endl;
}

//.........1.先序遍历建立二叉树.........
//方法一:
BiThrNode *CreatTree()
{
BiThrNode *Setup(char str[]);
BiThrNode *root;
char str[MAXSIZE];
cout<<"Input the string:";
gets(str);
root=Setup(str);
return (root);
}
int i=0;
BiThrNode *Setup(char str[])
{
BiThrNode *ptr;
if(str[i]=='#') return (NULL);
if(str[i]!='#')
{
ptr=new BiThrNode;
ptr->data=str[i];
i++;
ptr->lchild=Setup(str);
i++;
ptr->rchild=Setup(str);
return(ptr);
}else{
return (NULL);
}
}

/*
//方法二:
void CreateBiTree(BiThrTree &T)
{
char ch;
cout<<"Input the ch: ";
cin>>ch;
if(ch=='#') T=NULL;
else{
T=new BiThrNode;
T->data=ch;
CreateBiTree(T->lchild);
CreateBiTree(T->rchild);
}
}
*/

//.........2.先序遍历.........
void PreOrderTraverse(BiThrTree &T)
{
if(T){
cout<<T->data;
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->rchild);
}
}

//.........3.中序遍历........
void InOrderTraverse(BiThrTree &T)
{
if(T){
InOrderTraverse(T->lchild);
cout<<T->data;
InOrderTraverse(T->rchild);
}
}

//.........4.后序遍历.........
void PostOrderTraverse(BiThrTree &T)
{
if(T){
PostOrderTraverse(T->lchild);
PostOrderTraverse(T->rchild);
cout<<T->data;
}
}

//.........5.复制二叉树...........
void Copy(BiThrTree T,BiThrTree &NewT)
{
if(T==NULL)
{
NewT=NULL;
return;
}
else
{
NewT=new BiThrNode;
NewT->data=T->data;
Copy(T->lchild,NewT->lchild);
Copy(T->rchild,NewT->rchild);
}
}

//......全局变量.........
int n=1;
int m=1;
//.........6. 计算二叉树的深度.........
int Depth(BiThrTree T)
{
if(T==NULL) return 0;
else{
m=Depth(T->lchild);
n=Depth(T->rchild);
if(m>n) return (m+1);
else return (n+1);
}
}

//.........7.统计二叉树中结点的个数.......
int NodeCount(BiThrTree T)
{
if(T==NULL) return 0;
else return NodeCount(T->lchild)+NodeCount(T->rchild)+1;
}

//.........8.统计二叉树页子结点的个数.......
int LeNoCount(BiThrTree T)
{
if(T==NULL) return 0;
else
if((LeNoCount(T->lchild)==NULL)&&(LeNoCount(T->rchild)==NULL))
return (n+1);
}

//.........9.统计二叉树中度为1结点的个数.........
int OnNoCount(BiThrTree T)
{
if(T=NULL) return 0;
else
if( ((LeNoCount(T->lchild)==NULL)&&(LeNoCount(T->rchild)!=NULL))||((LeNoCount(T->lchild)==NULL)&&(LeNoCount(T->rchild)!=NULL)) )
return (n+1);
}

//.........10.统计二叉树中度为2结点的个数.........
int TwNoCount(BiThrTree T)
{
if(T==NULL) return 0;
else
if( (LeNoCount(T->lchild)!=NULL)&&(LeNoCount(T->rchild)!=NULL) )
return (n+1);
}

//.........11.前序线索二叉树..........
BiThrTree pre;
void PreThreading(BiThrTree p)
{
if(p){
if(!p->lchild)
{ p->lTag=1;
p->lchild=pre;
}
else p->lTag=0;
if(!pre->rchild)
{ pre->rTag=1;
pre->rchild=p;
}
else p->rTag=0;
pre=p;
PreThreading(p->lchild);
PreThreading(p->rchild);
}
}

//.........12.中序线索二叉树..........
void InThreading(BiThrTree p)
{
if(p){
InThreading(p->lchild);
if(!p->lchild)
{ p->lTag=1;
p->lchild=pre;
}
else p->lTag=0;
if(!pre->rchild)
{ pre->rTag=1;
pre->rchild=p;
}
else pre->rTag=0;
pre=p;
InThreading(p->rchild);
}
}

//.........13.后序线索二叉树..........
void PostThreading(BiThrTree p)
{
if(p){
PostThreading(p->lchild);
PostThreading(p->rchild);
if(!p->lchild)
{ p->lTag=1;
p->lchild=pre;
}
else p->lTag=0;
if(!pre->rchild)
{ pre->rTag=1;
pre->rchild=p;
}
else pre->rTag=0;
pre=p;
}
}

//.......主函数........
void main()
{
print();
BiThrNode *T;
BiThrNode *p;
BiThrNode *NewT; //复制而成的二叉树
while(1)
{
int n;
cout<<endl;
cout<<"请输入要选择小功能:";
cin>>n;
if(n<0||n>=14)
{ cout<<"不在服务区,请重新输入:"<<endl;
cin>>n;
}
cout<<endl;
switch(n)
{
case 1: cout<<"先序遍历建立二叉树:"<<endl;
T=CreatTree();
// CreateBiTree(T);
break;

case 2: cout<<"先序遍历:";
PreOrderTraverse(T);
break;

case 3: cout<<"中序遍历:";
InOrderTraverse(T);
break;

case 4: cout<<"后序遍历:";
PostOrderTraverse(T);
break;

case 5: cout<<"复制二叉树:"<<endl;
Copy(T,NewT);
cout<<"前序遍历输出为:";
PreOrderTraverse(NewT);
break;

case 6: cout<<"计算二叉树的深度为:";
cout<<Depth(T)<<endl;
break;

case 7: cout<<"统计二叉树中结点的个数为:";
cout<<NodeCount(T)<<endl;
break;

case 8: cout<<"统计二叉树页子结点的个数为:";
cout<<LeNoCount(T)<<endl;
break;

case 9: cout<<"统计二叉树中度为1的个数为:";
cout<<OnNoCount(T)<<endl;
break;

case 10: cout<<"统计二叉树中度为2的结点个数为:";
cout<<TwNoCount(T)<<endl;
break;
case 11: cout<<"前序线索二叉树:"<<endl;
PreThreading(p);
break;

case 12: cout<<"中序线索二叉树:"<<endl;
InThreading(p);
break;
case 13: cout<<"后序线索二叉树:"<<endl;
PostThreading(p);
break;
default: cout<<"NULL"<<endl;
}
}
}

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(1

归属感 2017-04-21 1 楼

你的方法一也是对的,只是输入的节点的方法不对,因为你是要保存一个字符串,你先看看直接赋值的方法:

//方法一:
BiThrNode *CreatTree()
{
BiThrNode *Setup(char str[]);
BiThrNode *root;
char str[MAXSIZE] = "ABC##D##E#F##";// 这个是节点序列
cout<<"Input the string:";
root=Setup(str);
return (root);
}

像上面那样是没错的,如果你一定要用字符串,那就改为用 string 吧,向下面这样改:

 //方法一:
BiThrNode *CreatTree()
{
BiThrNode *Setup(string str); // 改成 string
BiThrNode *root;
//char str[MAXSIZE] = "ABC##D##E#F##";
string str; // 这里用 string,当然在前面要加 #include<string>
cout<<"Input the string:";
cin >> str;
root=Setup(str);
return (root);
}
int i=0;
BiThrNode *Setup(string str) // 改成 string
{
BiThrNode *ptr;
if(str[i]=='#') return (NULL);
if(str[i]!='#')
{
ptr=new BiThrNode;
ptr->data=str[i];
i++;
ptr->lchild=Setup(str);
i++;
ptr->rchild=Setup(str);
return(ptr);
}else{
return (NULL);
}
}