Question

编程-数据结构（C语言编程）二叉树相关问题求解？

、分别找出满足以下条件的所有二叉树：（9分）
１） 前序序列和中序序列相同。
２） 中序序列和后序序列相同。
３） 前序序列和后序序列相同。

请高手帮忙呀，你做好了，用QQ截图发到这上面嘛，谢谢

Answer 1

(1) 前序序列和中序序列相同的二叉树是：空二叉树或没有左子树的二叉树(右单支树)。
　(2) 中序序列和后序序列相同的二叉树是：空二叉树或没有右子树的二叉树(左单支树)。
　(3) 前序序列和后序序列相同的二叉树是：空二叉树或只有根的二叉树。
　

Answer 2

typedef char DataType;
typedef struct node{
DataType data;
struct node *lchild, *rchild;
}BinTNode;

typedef BinTNode *BinTree ;

#include <stdio.h>
#include <malloc.h>
void CreatBinTree(BinTree *T)
{ /*输入序列是先序序列*/
char ch;
if ((ch=getchar())==' ')
*T=NULL;
else{
*T=(BinTNode *)malloc(sizeof(BinTNode));
(*T)->data=ch;
CreatBinTree(&(*T)->lchild);
CreatBinTree(&(*T)->rchild);
}
}

int Node(BinTree T)
{
int static nodes=0;/*静态变量保证其值不会随递归调用而消失*/
if(T)
{/*使用中序序列*/
Node(T->lchild);
nodes++;
Node(T->rchild);
}
return nodes;
}

int Leaf(BinTree T)
{
int static leaves=0;/*静态变量保证其值不会随递归调用而消失*/
if(T)
{ /*使用中序序列*/
Leaf(T->lchild);
if(!(T->lchild||T->rchild))
leaves++;
Leaf(T->rchild);
}
return leaves;
}
#include <stdio.h>
void main()
{
int nodes;
int leaves;
BinTree root;
CreatBinTree(&root);
nodes=Node(root);
leaves=Leaf(root);
printf("\nnodes=%d leaves=%d",nodes,leaves);
}

/*输入ABD CE F */

/* 输入时注意：D后面三个空格，E后面两个空格，F后面两个空格*/

/*输出nodes=6 leaves=3*/