c++数据结构树的应用

Question

问题描述：设有二叉树结点的定义如下：
template <typename T>
class tnode
{
public: //注意都是公有成员
T nodeValue;
tnode<T> *left, *right;
tnode() { }
tnode(const T& item, tnode<T> *lptr = NULL, tnode<T> *rptr = NULL)
:nodeValue(item),left(lptr),right(rptr)
{ }
};
以及下面创建二叉树的函数
void createBtree(tnode<char> *&r)
{
char ch;
ch=getchar();
if(ch=='#')
r=NULL;
else
{
r=new tnode<char>(ch);
createBtree(r->left);
createBtree(r->right);
}
}
创建一个二叉树，然后给出它的先序、中序、后序遍历的结果。
创建二叉树函数应用举例：
//输入一个包含二叉树空子树的先序遍历序列，调用createBtree(ctree)创建这颗树，
//结果指针ctree指向所创建的树的树根
// A
// / \
// B C
// \
// D
//其含有空子树的先序遍历为:AB#D##C##回车，其中#表示空子树
//B的左子树为空，D和C的左右子树均为空
输入样例：
AB#D##C##

输出样例：
A B D C
B D A C
D B C A

注意字符之间有一个空格
要求，用递归或非递归实现先序、中序、后序函数，并使用上面tnode的定义和createBtree函数。

Answer 1

#include<cstdio>
#include<stack>
using namespace std;
template <typename T>
class tnode
{
public: //注意都是公有成员
T nodeValue;
tnode<T> *left, *right;
tnode() { }
tnode(const T& item, tnode<T> *lptr = NULL, tnode<T> *rptr = NULL)
:nodeValue(item),left(lptr),right(rptr)
{ }
};
void createBtree(tnode<char> *&r)
{
char ch;
ch=getchar();
if(ch=='#')
r=NULL;
else
{
r=new tnode<char>(ch);
createBtree(r->left);
createBtree(r->right);
}
}
void fun1(tnode<char> *&node)//先序遍历
{
if(node!=NULL)
{
printf("%c ",node->nodeValue);
fun1(node->left);
fun1(node->right);
}
}
void fun2(tnode<char> *&node)//中序遍历
{
if(node!=NULL)
{
fun2(node->left);
printf("%c ",node->nodeValue);
fun2(node->right);
}
}
void fun3(tnode<char> *&node)//后序遍历
{
if(node!=NULL)
{
fun3(node->left);
fun3(node->right);
printf("%c ",node->nodeValue);
}
}
void f1(tnode<char> *&node)
{
tnode<char>*p=node;
stack <tnode<char>*>s;
s.push(node);
while(!s.empty())
{
if(p)
{
printf("%c ",p->nodeValue);
s.push(p);
p=p->left;
}
else
{
p=s.top()->right;
s.pop();
}
}
}
void f2(tnode<char> *&node)
{
tnode<char>*p=node;
stack <tnode<char>*>s;
do
{
if(p)
{
s.push(p);
p=p->left;
}
else
{
printf("%c ",s.top()->nodeValue);
p=s.top()->right;
s.pop();
}
}while(p!=NULL||!s.empty());
}
void f3(tnode<char> *&node)
{
tnode<char>*p=node;
stack <tnode<char>*>s;
int flag[1000]={0};
do
{
if(p)
{
s.push(p);
p=p->left;
}
else
{
if(flag[s.size()-1]==0)
{
p=s.top()->right;
flag[s.size()-1]=1;
}
else
{
printf("%c ",s.top()->nodeValue);
s.pop();
flag[s.size()]=0;
}
}
}while(!s.empty());
}
int main()
{
tnode <char> *tree;
createBtree(tree);
printf("先序递归算法");
fun1(tree);
printf("\n");
printf("中序递归算法");
fun2(tree);
printf("\n");
printf("后序递归算法");
fun3(tree);
printf("\n");
printf("先序非递归算法");
f1(tree);
printf("\n");
printf("中序非递归算法");
f2(tree);
printf("\n");
printf("后序非递归算法");
f3(tree);
printf("\n");
return 0;
}追问

这题我已经搞懂了，不过还是很感谢你的！

追答

不客气的

本回答被提问者采纳