清华大学考研复试上机题之二叉树的遍历

问题描述：

编一个程序，读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树（以指针方式存储）。

例如如下的先序遍历字符串：ABC##DE#G##F### 

其中#表示的是空格，空格字符代表空树。

建立起此二叉树以后，再对二叉树进行中序遍历，输出遍历结果

• 示例 1：

输入：abc##de#g##f###
输出：c b e g d f a 

解题思路：

首先根据前序创建二叉树，再以中序输出。

定义i来当数组的下标，注意对i传参时要传i的地址（每次递归后返回的i不是同一个i）

根据前序，若读到’#‘，则返回NULL，下标++，若读到其他字符，就根据递归创建树的节点，创建的节点先赋给左子树，递归回来后再赋给右子树，以此类推不断递归即可。

接着根据中序输出创建的二叉树

代码如下：

#include<stdio.h>
#include<stdlib.h>
typedef struct TreeNode {struct TreeNode* left;struct TreeNode* right;char val;
}TNode;
TNode* CreateTree(char* a, int* pi)
{if (a[*pi] == '#'){(*pi)++;return NULL;}TNode* root = (TNode*)malloc(sizeof(TNode));if (root == NULL){printf("malloc fail\n");exit(-1);}root->val = a[*pi];(*pi)++;root->left = CreateTree(a, pi);root->right = CreateTree(a, pi);return root;
}
void InOrder(TNode* root)
{if (root == NULL)return;InOrder(root->left);printf("%c ", root->val);InOrder(root->right);
}
int main()
{char  str[100];scanf("%s", str);int i = 0;TNode* root = CreateTree(str, &i);InOrder(root);return 0;
}

小tip:

哈希曼树

贪心算法：将权值小的放在左子树上。

权值越大，路径越短，编码越短

权值越小，路径越长，编码越长