问题遇到的现象和发生背景
问题相关代码,请勿粘贴截图
运行结果及报错内容
我的解答思路和尝试过的方法
我想要达到的结果
#include <iostream>
#define MAXSIZE 30
using namespace std;
#include <stack>
#include <vector>
struct BTNode
{
char data;
BTNode *lchild,*rchild;
BTNode (char d){
data = d;
lchild = rchild = NULL;
}
};
class BTree
{
BTNode * r;
public:
BTree() {r = NULL;}
//1.
bool CreateBTree(string str)
{
int i = 0;
char flag ;
stack <BTNode *> st;
BTNode * p;
while (i < str.size())
{
switch(str[i])
{
case '(':flag = 'L';st.push(p);break;
case ')':if(!st.empty()){st.pop();break;} else return false;
case ',':flag = 'R';
default:
p = new BTNode (str[i]);
if(r == NULL)
{
r = p;
}
else
{
if(!st.empty())
{
if(flag == 'L')st.top() -> lchild = p;
else st.top() -> rchild = p;
}
else return false;
}
}
i++;
}// end while
//串结束后,栈应该为空
if(!st.empty()) return false;
else return true;
return true;
}
//2.
void inorder(BTNode *b)
{
if(b != NULL)
{
inorder(b->lchild);
cout<<b->data;
inorder(b->rchild);
}
}
void InOrder(BTree& bt)
{
inorder(bt.r);
}
//3.前序
void porder(BTNode *b)
{
if(b != NULL)
{
cout<<b->data;
porder(b->lchild);
porder(b->rchild);
}
}
void Porder(BTree& bt)
{
porder(bt.r);
}
//4.后序
void postorder(BTNode *b)
{
if(b != NULL)
{
postorder(b->lchild);
postorder(b->rchild);
cout<<b->data;
}
}
void PostOrder(BTree& bt)
{
postorder(bt.r);
}
//5.深度
int height(BTNode *b)
{
if(b != NULL)
{
return 1+max(height(b->lchild),height(b->rchild)) ;
}
else return 0;
}
int Height(BTree& bt)
{
return height(bt.r);
}
//6.统计二叉树的结点个数 。
int NodeNumber(BTNode *d)
{
if(d != NULL)
{
return 1+NodeNumber(d->lchild)+NodeNumber(d->rchild);
}
else return 0;
}
//7.统计二叉树的叶结点个数。
int leaf(BTNode *b)
{
if(b != NULL)
{
if(b->lchild == NULL&&b->rchild == NULL)
{
return 1;
}
else
{
return leaf(b->lchild)+leaf(b->rchild);
}
}
else return 0;
}
//8.统计二叉树的度为1的结点个数。
int nodecount(BTNode *b)
{
if(b == NULL)
{
return 0;
}
if(b->lchild == NULL&&b->rchild != NULL||b->rchild == NULL&&b->lchild != NULL)
{
return 1+nodecount(b->lchild) + nodecount(b->rchild);
}
return nodecount(b->lchild)+nodecount(b->rchild);
}
int NodeCount(BTree& bt)
{
nodecount(bt.r);
}
//9.输出二叉树中从每个叶子结点到根结点的路径。243
bool lujing(BTNode *b,char x,vector<char> path,vector<char>& res)
{
if(b == NULL) return false;
path.push_back(b->data);
if(b->data == x)
{
path.pop_back();
res = path;
return true;
}
if(lujing(b->lchild,x,path,res))
return true;
else
return lujing(b->rchild,x,path,res);
}
void LuJing(BTree& bt,char x,vector<char>&res)
{
vector<char> path;
lujing(bt.r,x,path,res);
}
//在树上找结点x
BTNode * findNode(BTNode * b ,char x)
{
if(b == NULL) return NULL;
else if(b -> data == x) return b;
else
{
BTNode * p = findNode(b ->lchild , x);
if(p != NULL ) return p;
else return findNode(b -> rchild , x);
}
}
//获取根指针
BTNode * getRoot()
{
return r;
}
};
int main()
{
BTree tree;
string str;
cin >> str;
char path[MAXSIZE];
//1
if(tree.CreateBTree(str))
cout << "创建成功" <<endl;
else cout << "创建失败" << endl;
char x;
cout<<"请输入要查找的结点名称:"<<endl;
cin >> x;
BTNode * root = tree.getRoot();//定义root为tree树根的指针
BTNode *p =tree.findNode(root,x); //在tree上进行查找
if(p != NULL) cout <<" 找到了\n" << endl;//p空,没找到,否则找到了。
else cout << "没有找到\n" <<endl;
//2
cout<<"中序遍历结果为:"<<endl;
tree.InOrder(tree);
cout<<endl;
//3
cout<<"前序遍历结果为:"<<endl;
tree.Porder(tree);
cout<<endl;
//4
cout<<"后序遍历结果为:"<<endl;
tree.PostOrder(tree);
cout<<endl;
//5
cout<<"该树的深度为:"<<endl;
cout<<tree.Height(tree);
cout<<endl;
//8
cout<<"度为一的结点个数为:"<<endl;
cout<<tree.NodeCount(tree);
//9
cout<<"从每个叶子结点到根结点的路径为:"<<endl;
tree.LuJing(tree,x,path,res);
return 0;
}