在用先序遍历建立二叉树，以下方法一中用指针函数来实现不行，为什么？
//..........二叉树...........
#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;
}
}
}
你们最讨厌了
11 years ago
Answers
你的方法一也是对的，只是输入的节点的方法不对，因为你是要保存一个字符串，你先看看直接赋值的方法：
//方法一：
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);
}
}
RachelC
answered 11 years ago