两个二叉树相关的常见题目 - 数据结构 - 机器学习
1208 人阅读 | 时间：2021年01月15日 01:07
去获取百度分享代码
数据结构 - 机器学习
深度学习
当前位置：首页 » 数据结构精品文章 » 正文
两个二叉树相关的常见题目
1278 人参与 2018年09月03日 23:05 分类 : 数据结构精品文章 评论
前记：这一章课件里主要讲了树和二叉树的属性和一些常用的操作。下面针对二叉树的遍历举一个具体的例子，这个题目在等级考试或者面试中都经常出现，大家多思考一下。
一 题目描述：已知二叉树前序遍历和中序遍历分别为：ABDEGCFH和DBGEACHF，则该二叉树的后序遍历为？
答案：DGEBHFCA
解题思路：
先序遍历的第一个结点是根结点，所以A是根；
然后在中序遍历中找到A，（DBGE）A（CHF）；
由中序遍历的定义知（DBGE）是左子树的中序遍历，（CHF）是右子树的中序遍历。
然后在先序遍历中把左子树和右子树划开，A（BDEG）（CHF），所以B是左子树根，C是右子树根。
然后继续在中序遍历中找到B和C，（（D）B（GE））A（C（HF））。
对于DBEG，B是根，D是左子树，EG是右子树的中序遍历，对于CHF，C是根，HF是右子树的中序遍历。因为仍然有没划分完的部分，所以继续看先序。
对于BDEG，B是根已知，D是整个左子树已知，所以EG是右子树的先序遍历，E是右根，再对照中序可知G是E的左子树，CHF同理。
所以树的结构是A（B（D，E（G，）），C（，F（H，）））
把它画成图，后序遍历就是DGEBHFCA
总之先序序列是用来确定根结点，中序序列是用来划分出左右子树。
二 题目：建立一棵二叉树，并对其进行遍历（先序、中序、后序），打印输出遍历结果
[基本要求]
从键盘接受输入（先序），以二叉链表作为存储结构，建立二叉树（以先序来建立），并采用递归算法对其进行遍历（先序、中序、后序），将遍历结果打印输出。
[测试数据]
ABC DE G F （其中 表示空格字符）
则输出结果为 先序：ABCDEGF
中序：CBEGDFA
后序：CGBFDBA
C语言描述的方法：
//示例的是先序遍历，其它的可以在这个基础上改。
#include<stdio.h>
#include<stdlib.h>
typedef struct tnode
{ char data;
struct tnode *lchild;
struct tnode *rchild;
}tnode;
tnode *Tree_creat(tnode *t)
{ char ch;
ch=getchar();
if(ch==' ')
t=NULL;
else
{
if(!(t=(tnode *)malloc(sizeof(tnode))))
printf("Error!");
t->data=ch;//printf("[%c]",t->data);
t->lchild=Tree_creat(t->lchild);
t->rchild=Tree_creat(t->rchild);
}
return t;
}
void preorder(tnode *t)
{ if(t!=NULL)
{ printf("%c ",t->data);
preorder(t->lchild);
preorder(t->rchild);
}
}
void main()
{
tnode *t=NULL;
t=Tree_creat(t);
preorder(t);
}来源：我是码农，转载请保留出处和链接！
本文链接：http://www.54manong.com/?id=207
(function() {
var s = "_" + Math.random().toString(36).slice(2);
document.write('');
(window.slotbydup = window.slotbydup || []).push({
id: "u3646208",
container: s
});
})();
(function() {
var s = "_" + Math.random().toString(36).slice(2);
document.write('');
(window.slotbydup = window.slotbydup || []).push({
id: "u3646147",
container: s
});
})();
window._bd_share_config={"common":{"bdSnsKey":{},"bdText":"","bdMini":"2","bdPic":"","bdStyle":"0","bdSize":"16"},"share":{},"image":{"viewList":["qzone","tsina","tqq","renren","weixin"],"viewText":"分享到：","viewSize":"16"},"selectShare":{"bdContainerClass":null,"bdSelectMiniList":["qzone","tsina","tqq","renren","weixin"]}};with(document)0[(getElementsByTagName('head')[0]||body).appendChild(createElement('script')).src='http://bdimg.share.baidu.com/static/api/js/share.js?v=89860593.js?cdnversion='+~(-new Date()/36e5)];
数据结构 微信号：qq444848023 QQ号：444848023
加入【我是码农】QQ群：864689844（加群验证：我是码农）
- 有哪些研究数据结构的好的方法？2018-08-18 09:05
- 栈的相关定义2018-09-03 22:34
- 几种查找方法的介绍与比较2018-09-03 23:13
- 数据结构之栈和队列-基本概念和术语汇总2018-08-18 08:59
(function() {
var s = "_" + Math.random().toString(36).slice(2);
document.write('');
(window.slotbydup = window.slotbydup || []).push({
id: "u3646186",
container: s
});
})();
(function() {
var s = "_" + Math.random().toString(36).slice(2);
document.write('');
(window.slotbydup = window.slotbydup || []).push({
id: "u3646175",
container: s
});
})();
搜索
网站分类
- 数据结构
- 数据结构视频教程
- 数据结构练习题
- 数据结构试卷
- 数据结构习题解析
- 数据结构电子书
- 数据结构精品文章
- 区块链
- 区块链精品文章
- 区块链电子书
- 大数据
- 大数据精品文章
- 大数据电子书
- 机器学习
- 机器学习精品文章
- 机器学习电子书
- 面试笔试
- 物联网/云计算
标签列表
- 数据结构 (39)
- 数据结构电子书 (20)
- 数据结构习题解析 (8)
- 数据结构试卷 (10)
- 区块链是什么 (261)
- 数据结构视频教程 (31)
- 大数据技术与应用 (12)
- 百面机器学习 (14)
- 机器学电子书 (29)
- 大数据电子书 (37)
- 程序员面试 (10)
- RFID (21)
最近发表
- 找出数组中有3个出现一次的数字
- 《百面机器学习》电子书下载
- 区块链精品电子书《深度探索区块链：Hyperledger技术与应用_区块链技术丛书》张增骏
- 区块链精品电子书《比特币：一个虚幻而真实的金融世界》
- 区块链精品电子书《图说区块链》-徐明星 & 田颖 & 李霁月
- 区块链精品电子书《是非区块链：技术、投机与泡沫》-英国《金融时报》
- 区块链精品电子书《商业区块链：开启加密经济新时代》-威廉·穆贾雅
- 区块链精品电子书《人工智能时代，一本书读懂区块链金融 (互联网_时代企业管理实战系列)》-马兆林
-
(function(){
var bp = document.createElement('script');
var curProtocol = window.location.protocol.split(':')[0];
if (curProtocol === 'https'){
bp.src = 'https://zz.bdstatic.com/linksubmit/push.js';
}
else{
bp.src = 'http://push.zhanzhang.baidu.com/push.js';
}
var s = document.getElementsByTagName("script")[0];
s.parentNode.insertBefore(bp, s);
})();
全站首页 | 数据结构 | 区块链| 大数据 | 机器学习 | 物联网和云计算 | 面试笔试
var cnzz_protocol = (("https:" == document.location.protocol) ? "https://" : "http://");document.write(unescape("%3Cspan id='cnzz_stat_icon_1276413723'%3E%3C/span%3E%3Cscript src='" + cnzz_protocol + "s23.cnzz.com/z_stat.php%3Fid%3D1276413723%26show%3Dpic1' type='text/javascript'%3E%3C/script%3E"));本站资源大部分来自互联网，版权归原作者所有！
©著作权归作者所有：来自ZhiKuGroup博客作者没文化的原创作品，如需转载，请注明出处，否则将追究法律责任
来源：ZhiKuGroup博客，欢迎分享。
评论专区