已知二叉树的中序和先序序列,求后序序列.doc

#include #include #include typedef struct Node /* 树结点类型 */ int info; /* 数据域 */ struct Node* parent; /* 父结点 */ struct Node* lchild; /* 左孩子结点 */ struct Node* rchild; /* 右孩子结点 */PNode;struct Stack /* 栈结点类型 */ int* pre; int* in; int n; PNode parent;PNode *Init_tree(int *pre,int *in,int n);/声明/* 前序遍历 */void pre_order(PNode *root) if (root != NULL) printf(%d ,root-info); pre_order(root-lchild); pre_order(root-rchild); /* 中序遍历 */void in_order(PNode *root) if (root != NULL) in_order(root-lchild); printf(%d ,root-info); in_order(root-rchild); /* 后序遍历 */void post_order(PNode *root) if (root != NULL) post_order(root-lchild); post_order(root-rchild); printf(%d ,root-info); int main(void) PNode *root;int pre50=1,2,4,8,10,5,9,3,6,7;int in 50=8,10,4,2,5,9,1,6,3,7 ; /* 建树 */ root = Init_tree(pre,in,10); printf(n前序遍历结果：n); pre_order(root); printf(n中序遍历结果：n); in_order(root); printf(n后序遍历结果：n); post_order(root); printf(n); return 0;PNode *Init_tree(int *pre,int *in,int n) PNode *root; int *p,*q,i,j,m;if(ninfo=pre0;root-lchild=root-rchild=NULL;i=0;while(ilchild=Init_tree(p,q,i);p=pre+i+1;q=in+i+1;root-rchild=Init_tree(p,q,n-i-1);return(root);树的形状 1 / 2 3 / / 4 5 6 7 / 8 9 10 这种题一般有二种形式，共同点是都已知中序序列。如果没有中序序列，是无法唯一确定一棵树的，证明略。一、已知二叉树的前序序列和中序序列，求解树。1、确定树的根节点。树根是当前树中所有元素在前序遍历中最先出现的元素。2、求解树的子树。找出根节点在中序遍历中的位置，根左边的所有元素就是左子树，根右边的所有元素就是右子树。若根节点左边或右边为空，则该方向子树为空；若根节点左边和右边都为空，则根节点已经为叶子节点。3、递归求解树。将左子树和右子树分别看成一棵二叉树，重复1、2、3步，直到所有的节点完成定位。二、已知二叉树的后序序列和中序序列，求解树。1、确定树的根。树根是当前树中所有元素在后序遍历中最后出现的元素。2、求解树的子树。找出根节点在中序遍历中的位置，根左边的所有元素就是左子树，根右边的所有元素就是右子树。若根节点左边或右边为空，则该方向子树为空；若根节点左边和右边都为空，则根节点已经为叶子节点。3、递归求解树。将左子树和右子树分别看成一棵二叉树，重复1、2、3步，直到所有的节点完成定位。举例说明：根据已知求解二叉树中序序列 HLDBEKAFCG后序序列 LHDKEBFGCA1、在后序序列LHDKEBFGCA中最后出现的元素为A，HLDBEK|A|FCG2、在后序序列LHDKEB中最后出现的元素为B，HLD|B|EK|A|FCG3、在后序序列LHD中最后出现的元素为D，HL|D|B|EK|A|FCG4、在后序序列LH中最后出现的元素为H，H|L|D|B|EK|A|FCG5、在后序序列KE中最后出现的元素为E，H|L|D|B|E|K|A|FC