碳之狼

用户名：1024650038

访问量：8491

签　名：

现在的我什么都做不到

等　　级
排　　名	664
经　　验	4015
参赛次数	0
文章发表	17
年　　龄	18
在职情况	学生
学　　校	东莞理工学院
专　　业	计算机类

　　自我简介：

TA的其他文章

蓝桥杯2019年第十届真题-完全二叉树的权值-题解（C++代码）
浏览：324

蓝桥杯2019年第十届真题-等差数列-题解（C++代码）辗转相除求最大公约数
浏览：382

蓝桥杯2019年第十届真题-外卖店优先级-题解（C++代码）时间复杂度不高
浏览：526

你可能喜欢

2006年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C语言程序设计教程（第三版）课后习题6.7 （C++代码）（经常这样写会不会被打死）

二叉树遍历-题解(C语言代码)

　　作者: 碳之狼　　　　发表时间：2020-01-17 19:41:26 浏览：1303　|　评论：1　

原题链接：二叉树遍历

**已知二叉树的前序遍历和中序遍历，如何得到它的后序遍历？**
我们以一个例子做一下这个过程，假设：
前序遍历的顺序是: ABCDEFG
中序遍历的顺序是: DCBAEFG
1. 对于前序遍历，第一个肯定是根结点（对于后序遍历，则最后一个是根结点）
2. 确定根节点，在中序遍历中，根结点的两边就可以分出其左子树和右子树

step1.易知根结点为A，在中序遍历中以A为分界点可得左子树:DCB，右子树:EFG
如:　　　A
　　　/　　＼
　　DCB　　EFG
step2.前序遍历此时：~~A~~BCDEFG,取出左子树，左子树的前序遍历是：BCD，中序遍历是：DCB,则当前结点为Ｂ，其左子树为DC,无右子树
如:　　　A
　　　/　　＼
　　 B　　EFG
　　/
　DC
step3.前序遍历此时：~~AB~~CDEFG,取出左子树，左子树的前序遍历是：CD，中序遍历是：DC,则当前结点为Ｃ，其左子树为D,无右子树
如:　　　A
　　　/　　＼
　　 B　　EFG
　　/
　 C
　/
D
step４.前序遍历此时：~~ABCD~~EFG,取出A结点的右子树，右子树的前序遍历是：EFG，中序遍历是：EFG,则当前结点为E，无左子树,其右子树为FG
如:　　　A
　　　/　　＼
　　 B　　　E
　　/　　　　＼
　 C　　　　　FG
　/
D
step5.前序遍历此时：~~ABCDEFG~~,取出A结点的右子树，右子树的前序遍历是：FG，中序遍历是：FG,则当前结点为F，无左子树,其右子树为G
如:　　　A
　　　/　　＼
　　 B　　　E
　　/　　　　＼
　 C　　　　　F
　/　　　　　　＼
D　　　　　　　　G
对左子树和右子树做拆分可用**strtok()**，再做递归，我们就可以重建出完整的二叉树
	#include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    int cnt;
    struct TreeNode {
    	char s[30];
    	struct TreeNode* left;
    	struct TreeNode* right;
    };
    typedef struct TreeNode* Tree;
    
    Tree CreateTree(char* s1, char* s2) {
    	char* p, * q;									//p保存左子树,q保存右子树
    	Tree root = (Tree)malloc(sizeof(struct TreeNode));
    	if (s2 == NULL) return NULL;
    	else {
    		root->s[0] = s1[cnt++];
    		root->s[1] = '\0';
    		p = strtok(s2, root->s);
    		q = strtok(NULL, root->s);
    		root->left = CreateTree(s1, p);
    		root->right = CreateTree(s1, q);
    	}
    	return root;
    }
    
    void PostOrderTraversal(Tree root)
    {
    	if (root) {
    		PostOrderTraversal(root->left);
    		PostOrderTraversal(root->right);
    		putchar(root->s[0]);
    	}
    }
    
    int main()
    {
    	Tree root;
    	char s1[30], s2[30];
    	while (scanf("%s%s", s1, s2) != EOF) {
    		root = CreateTree(s1, s2);
    		PostOrderTraversal(root);
    		printf("\n");
    		free(root);
    		cnt = 0;
    	}
    	return 0;
    }

0.0分

10 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

　　评论区

火狐狸

大神，请问free是只需要将root释放就行了吗？需不需要一个一个节点释放

2022-10-10 21:26:02

碳之狼

TA的其他文章

你可能喜欢

2006年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

文件应用-fwrite函数

C语言程序设计教程（第三版）课后习题5.6 （C语言代码）

C语言程序设计教程（第三版）课后习题6.7 （C++代码）（经常这样写会不会被打死）

众数问题（C++代码）

二叉树遍历-题解(C语言代码)

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题7.1 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C语言程序设计教程（第三版）课后习题8.9 （C语言代码）

【亲和数】（C语言代码）

C语言程序设计教程（第三版）课后习题5.8 （C语言代码）

C语言程序设计教程（第三版）课后习题6.10 （C语言代码）

简单的a+b （C语言代码）

简单的a+b （C语言代码）

1642题解

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

碳之狼

TA的其他文章

你可能喜欢

2006年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

文件应用-fwrite函数

C语言程序设计教程（第三版）课后习题5.6 （C语言代码）

C语言程序设计教程（第三版）课后习题6.7 （C++代码）（经常这样写会不会被打死）

众数问题 （C++代码）

二叉树遍历-题解(C语言代码)

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题7.1 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C语言程序设计教程（第三版）课后习题8.9 （C语言代码）

【亲和数】 （C语言代码）

C语言程序设计教程（第三版）课后习题5.8 （C语言代码）

C语言程序设计教程（第三版）课后习题6.10 （C语言代码）

简单的a+b （C语言代码）

简单的a+b （C语言代码）

1642题解

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

众数问题（C++代码）

　　评论区

【亲和数】（C语言代码）