求C++的二叉树建立程序代码！

Question

1．将下图中的二叉树用二叉链表表示：（1）用三种遍历算法遍历该二叉树，给出对应的输出结果；（2）写一个函数对二叉树搜索，若给出一个结点，根据其是否属于该树，输出true 或者false。

Answer 1

#include
#include
typedef char datatype;
typedef struct BinNode{
datatype data;
struct BinNode* lchild;
struct BinNode* rchild;
}BinNode;

typedef BinNode* bintree; //bintree本身是个指向结点的指针

//前序遍历生成二叉树
void createtree(bintree *t){
datatype c;
c=getchar();
if(c == '#')
*t = NULL;
else{
*t = (bintree)malloc(sizeof(BinNode));
(*t)->data = c;
createtree(&(*t)->lchild);
createtree(&(*t)->rchild);
}
}
//中序遍历
void midorder(bintree t){
if(t){
midorder(t->lchild);
printf("%c ",t->data);
midorder(t->rchild);
}
}
//查找
bool search_tree(bintree t,datatype x){
if(!t){
return false;
}
if(t->data == x){
return t;
}else{
if(!search_tree(t->lchild,x)){
return search_tree(t->rchild,x);
}
return true;
}
}
//求深度
int height_tree(bintree t){
int h,left,right;
if(!t){
return 0;
}
left = height_tree(t->lchild);
right = height_tree(t->rchild);
h = (left>right?left:right)+1;
return h;
}
void main()
{
bintree Tree;
printf("Create tree in preorder:\n");
createtree(&Tree);
printf("Display tree in midorder:\n");
midorder(Tree);
printf("\n");
int height=height_tree(Tree);
printf("height:%d\n",height);
search_tree(Tree,'e')?printf("Found!\n"):printf("Not Found!\n");
return ;
}