2006年清华大学计算机研究生机试真题

http://ac.jobdu.com/problem.php?pid=1078 二叉树遍历

#include<stdio.h> #include<string.h>//二叉树结点的描述 typedef struct BinaryTreeNode {char data;struct BinaryTreeNode *lchild, *rchild; //左右孩子 }BinaryTreeNode,*BinaryTree;inline BinaryTreeNode* ConstructCore(char *startPreorder, char *endPreorder, char *startInorder, char *endInorder) {//前序遍历序列的第一个字符是根节点的值char rootValue = startPreorder[0];BinaryTreeNode* root = new BinaryTreeNode();root->data = rootValue;root->lchild = root->rchild = NULL;if(startPreorder == endPreorder){if(startInorder == endInorder && *startPreorder== *startInorder)return root;}//在中序遍历中找到根节点的值char *rootInorder = startInorder;while(rootInorder <= endInorder && *rootInorder != rootValue)rootInorder++;int leftLength = rootInorder - startInorder;char *leftPreorderEnd = startPreorder + leftLength;if(leftLength > 0){//构建左子树root->lchild = ConstructCore(startPreorder+1, leftPreorderEnd, startInorder, rootInorder-1);}if(leftLength < endPreorder - startPreorder){//构建右子树root->rchild = ConstructCore(leftPreorderEnd+1, endPreorder, rootInorder+1, endInorder);}return root; }//分别在前序遍历和中序遍历的序列中确定左、右子树的子序列 inline BinaryTreeNode* Construct(char *preorder, char *inorder, int length) {if(preorder == NULL || inorder == NULL || length<=0)return NULL;return ConstructCore(preorder, preorder+length-1, inorder, inorder+length-1); }//后序遍历 inline void PostOrder(BinaryTreeNode *root) {if(root==NULL)return ;PostOrder(root->lchild); //递归调用，前序遍历左子树PostOrder(root->rchild); //递归调用，前序遍历右子树printf("%c", root->data); //输出数据 }//释放二叉树 inline void DeleteBinaryTree(BinaryTree root) {if(root){DeleteBinaryTree(root->lchild); //释放左子树DeleteBinaryTree(root->rchild); //释放右子树delete root; //释放根结点} }int main(void) {int length;char preorder[27],inorder[27];while(scanf("%s",preorder)!=EOF){scanf("%s",inorder);length = strlen(preorder);BinaryTreeNode* root = Construct(preorder, inorder, length);PostOrder(root);printf("\n");DeleteBinaryTree(root);}return 0; }

 

总结

以上是生活随笔为你收集整理的2006年清华大学计算机研究生机试真题的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。