一个关于二叉树的问题
#include<iostream>
using namespace std;
//二叉树结点类声明
class BinTreeNode{
private:
BinTreeNode *left,*right;
int data;
public:
BinTreeNode(const int &item,BinTreeNode *lptr=NULL,BinTreeNode *rptr=NULL):data(item),left(lptr),right(rptr){} //构造函数
BinTreeNode *GetLeft(void)const{return left;} //返回左子结点
void SetLeft(BinTreeNode *L){left=L;} //设置左子结点
BinTreeNode *GetRight(void)const{return right;} //返回右子结点
void SetRight(BinTreeNode *R){right=R;} //设置右子结点
int &GetData(){return data;} //返回结点数据值
void SetData(const int &item){data=item;} //设置结点数据值
};
//二叉树类声明class BinTree{
private:
BinTreeNode *root; //指向二叉树根结点的指针
int stop; //构造二叉树时的输入结束符，输入stop则停止输入
public:
BinTree(BinTreeNode *t=NULL):root(t){} //构造函数
virtual ~BinTree(){Del(root);} //析构函数，删除整个二叉树
BinTreeNode *Father(BinTreeNode *t,BinTreeNode *p); //在以结点t为根结点的子树中搜索结点p的父结点
BinTreeNode *Find(BinTreeNode *t,const int &item)const; //在以结点t为根结点的子树中查找data域为item的结点
void DelSubtree(BinTreeNode *t); //从树中删除结点t及左右子树
void Del(BinTreeNode *t); //直接删除结点t及左右子树
void PreOrder(BinTreeNode *t)const; //先根遍历并输出以结点t为根节点的子树
void InOrder(BinTreeNode *t)const; //中根遍历并输出以结点t为根节点的子树
void PostOrder(BinTreeNode *t)const; //后根遍历并输出以结点t为根节点的子树
void LevelOrder(BinTreeNode *t)const; //遍历层次并输出以结点t为根节点的子树
void NorecOrder(BinTreeNode *t)const;
void NorecInOrder(BinTreeNode *t)const;
void NorecPostOrder(BinTreeNode *t)const;
void CreateBinTree(int tostop); //创建二叉树
BinTreeNode *Create();
BinTreeNode *CopyTree(BinTreeNode *t); //复制结点t为根的二叉树
BinTreeNode *GetRoot(){return root;}
void SetRoot(BinTreeNode *t){root=t;}
int GetStop(){return stop;}
void SetStop(int tostop){stop=tostop;}
int IsEmpty(){return root==NULL?1:0;} //判断二叉树是否为为空
};
//在以t为根结点的子树中搜索结点p的父结点
BinTreeNode * BinTree::Father(BinTreeNode *t,BinTreeNode *p){
BinTreeNode *q;
if(t==NULL||p==NULL) return NULL;
if(t->GetLeft()==p||t->GetRight()==p) return t;
if((q=Father(t->GetLeft(),p))!=NULL) return q;
else return Father(t->GetRight(),p);
};
//在以t为根指针的二叉树中搜索data域为item的结点，并令指针q指向此结点
BinTreeNode *BinTree::Find(BinTreeNode *t,const int &item)const{
BinTreeNode *p,*q;
if(t==NULL) return NULL;
if(t->GetData()==item) return t;
if((p=Find(t->GetLeft(),item))!=NULL) return p;
else return q=Find(t->GetRight(),item);
};
//从树中删除结点t及其左右子树
void BinTree::DelSubtree(BinTreeNode *t){
if(t==NULL) return;
if(t==root){
Del(t);
root=NULL;
return;
}
BinTreeNode *q,*p;
p=t;
q=Father(root,p);
if(q){
if((q->GetLeft())==p) q->SetLeft(NULL);
if((q->GetRight())==p) q->SetRight(NULL);
}
Del(p);
}
//直接删除结点t及左右子树
void BinTree::Del(BinTreeNode *t){
if(t!=NULL){
Del(t->GetLeft());
Del(t->GetRight());
delete t;
}
};
//递归先根遍历以结点t为根结点的子树
void BinTree::PreOrder(BinTreeNode *t)const{
if(t!=NULL){
cout<<t->GetData();
PreOrder(t->GetLeft());
PreOrder(t->GetRight());
}
};
//递归中根遍历以结点t为根结点的子树
void BinTree::InOrder(BinTreeNode *t)const{
if(t!=NULL){
InOrder(t->GetLeft());
cout<<t->GetData();
InOrder(t->GetRight());
}
};
//递归后根遍历以结点t为根结点的子树
void BinTree::PostOrder(BinTreeNode *t)const{
if(t!=NULL){
PostOrder(t->GetLeft());
PostOrder(t->GetRight());
cout<<t->GetData();
}
};
//通过调用Create（）函数，创建一棵一root为根的二叉树
void BinTree::CreateBinTree(int tostop){
SetStop(tostop);
root=Create();
}
//创建一棵二叉树,并返回该二叉树根结点
BinTreeNode * BinTree::Create(){
BinTreeNode *t1,*t2,*t;
int item;
cin>>item;
if(item==stop){t=NULL;return t;}
else{
if(!(t=new BinTreeNode(item,NULL,NULL))) return NULL;
t1=Create();
t->SetLeft(t1);
t2=Create();
t->SetRight(t2);
return t;
}
};
//主函数
int main(){
BinTreeNode * BinTreeNode1;
BinTree BinTree1;
BinTree1.CreateBinTree(1);
BinTreeNode1=BinTree1.GetRoot();
cout<<"先根遍历表示为："<<endl;
BinTree1.PreOrder(BinTreeNode1);
cout<<endl;
cout<<"中根遍历表示为："<<endl;
BinTree1.InOrder(BinTreeNode1);
cout<<endl;
cout<<"后根遍历表示为："<<endl;
BinTree1.PostOrder(BinTreeNode1);
cout<<endl;
return 0;
}
我是一个学生
学c++不久
做的程序不知道为什么不对
附近也没有可以沟通的同学（学编程对女生还是比较难的，能懂的很少）
感觉好像卡在死角里了
希望能被指导
可爱哒小鱼人
12 years, 4 months ago
Answers
提问也是有技巧的，首先纯代码要放在code标签(在文本输入框的左上角“Code”字样)里，这样代码被转义后还能继续显示。
仔细看你的代码：
本来应该是
因为*号是特殊字符，所以你的代码在显示后被转义，*不见了，而是left变成了斜体。
还有几处也是这种情况，不再一一指出。
关于程序逻辑错误，暂时没有时间来排查，建议先将你的帖子重新编辑下，这样会有更过的人帮你解答。
首先分析程序
从你CreateBinTree定义来看，输入1时表示空(NULL)节点。
BinTreeNode * BinTree::Create(){
BinTreeNode *t1,*t2,*t;
int item;
cin >> item;
if(item == stop) {
t = NULL;
return t;
}
else {
if(!(t=new BinTreeNode(item,NULL,NULL)))
return NULL;
t1=Create();
t->SetLeft(t1);
t2=Create();
t->SetRight(t2);
return t;
}
};
可以看出来是先根创建二叉树。
程序运行时错误，极有可能是你输入的时候没有把握好NULL节点的个数，导致二叉树没有创建成功。
考虑下程序输入和输出情况：
的情况，树的结构如下图：
在来个复杂点的树：
其他的情况，楼主就自己举一反三了。
PS：
不太清楚楼主的学习情况，还是先把清华版《数据结构》相关章节了解清楚，二叉树这块对初学者来说有点不好理解（用到了递归思想），但罗马不是一天建成的，keep moving吧。
白玉楼的游魂
answered 12 years, 4 months ago