济南便宜企业网站建设费用,竹业网站建设,网页在线小游戏,公众平台的微信网站开发问题描述#xff1a;
编一个程序#xff0c;读入用户输入的一串先序遍历字符串#xff0c;根据此字符串建立一个二叉树#xff08;以指针方式存储#xff09;。
例如如下的先序遍历字符串#xff1a;ABC##DE#G##F###
其中#表示的是空格#xff0c;空格字符代表空树。…问题描述
编一个程序读入用户输入的一串先序遍历字符串根据此字符串建立一个二叉树以指针方式存储。
例如如下的先序遍历字符串ABC##DE#G##F###
其中#表示的是空格空格字符代表空树。
建立起此二叉树以后再对二叉树进行中序遍历输出遍历结果
示例 1
输入abc##de#g##f###
输出c b e g d f a 解题思路
首先根据前序创建二叉树再以中序输出。
定义i来当数组的下标注意对i传参时要传i的地址每次递归后返回的i不是同一个i
根据前序若读到’#‘则返回NULL下标若读到其他字符就根据递归创建树的节点创建的节点先赋给左子树递归回来后再赋给右子树以此类推不断递归即可。
接着根据中序输出创建的二叉树
代码如下
#includestdio.h
#includestdlib.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: 哈希曼树 贪心算法将权值小的放在左子树上。 权值越大路径越短编码越短 权值越小路径越长编码越长
