西西软件下载最安全的下载网站、值得信赖的软件下载站！
→ 二叉树前序、中序、后序遍历相互求法
v1.14 中文绿色版
类型：FTP 工具大小：106KB语言：中文 评分：5.0
今天来总结下二叉树前序、中序、后序遍历相互求法，即如果知道两个的遍历，如何求第三种遍历方法，比较笨的方法是画出来二叉树，然后根据各种遍历不同的特性来求，也可以编程求出，下面我们分别说明。首先，我们看看前序、中序、后序遍历的特性：&前序遍历：&&&& 1.访问根节点&&&& 2.前序遍历左子树&&&& 3.前序遍历右子树&中序遍历：&&&& 1.中序遍历左子树&&&& 2.访问根节点&&&& 3.中序遍历右子树&后序遍历：&&&& 1.后序遍历左子树&&&& 2.后序遍历右子树&&&& 3.访问根节点一、已知前序、中序遍历，求后序遍历例：前序遍历: & & & & GDAFEMHZ中序遍历: & & & & ADEFGHMZ画树求法：第一步，根据前序遍历的特点，我们知道根结点为G第二步，观察中序遍历ADEFGHMZ。其中root节点G左侧的ADEF必然是root的左子树，G右侧的HMZ必然是root的右子树。&第三步，观察左子树ADEF，左子树的中的根节点必然是大树的root的leftchild。在前序遍历中，大树的root的leftchild位于root之后，所以左子树的根节点为D。第四步，同样的道理，root的右子树节点HMZ中的根节点也可以通过前序遍历求得。在前序遍历中，一定是先把root和root的所有左子树节点遍历完之后才会遍历右子树，并且遍历的左子树的第一个节点就是左子树的根节点。同理，遍历的右子树的第一个节点就是右子树的根节点。第五步，观察发现，上面的过程是递归的。先找到当前树的根节点，然后划分为左子树，右子树，然后进入左子树重复上面的过程，然后进入右子树重复上面的过程。最后就可以还原一棵树了。该步递归的过程可以简洁表达如下：1 确定根,确定左子树，确定右子树。2 在左子树中递归。3 在右子树中递归。4 打印当前根。那么，我们可以画出这个二叉树的形状：那么，根据后序的遍历规则，我们可以知道，后序遍历顺序为：AEFDHZMG编程求法：（依据上面的思路，写递归程序） 1 #include &iostream&
2 #include &fstream&
3 #include &string&
5 struct TreeNode
struct TreeNode*
struct TreeNode*
12 void BinaryTreeFromOrderings(char* inorder, char* preorder, int length)
if(length == 0)
//cout&&&invalid length&;
TreeNode* node = new TreeN//Noice that [new] should be written out.
node-&elem = *
int rootIndex = 0;
for(;rootIndex & rootIndex++)
if(inorder[rootIndex] == *preorder)
BinaryTreeFromOrderings(inorder, preorder +1, rootIndex);
BinaryTreeFromOrderings(inorder + rootIndex + 1, preorder + rootIndex + 1, length - (rootIndex + 1));
cout&&node-&elem&&
36 int main(int argc, char* argv[])
printf(&Hello World!\n&);
char* pr=&GDAFEMHZ&;
char* in=&ADEFGHMZ&;
BinaryTreeFromOrderings(in, pr, 8);
printf(&\n&);
46 }输出的结果为：AEFDHZMG二、已知中序和后序遍历，求前序遍历依然是上面的题，这次我们只给出中序和后序遍历：中序遍历: & & & ADEFGHMZ后序遍历:&&&&&& AEFDHZMG画树求法：第一步，根据后序遍历的特点，我们知道后序遍历最后一个结点即为根结点，即根结点为G。第二步，观察中序遍历ADEFGHMZ。其中root节点G左侧的ADEF必然是root的左子树，G右侧的HMZ必然是root的右子树。第三步，观察左子树ADEF，左子树的中的根节点必然是大树的root的leftchild。在前序遍历中，大树的root的leftchild位于root之后，所以左子树的根节点为D。第四步，同样的道理，root的右子树节点HMZ中的根节点也可以通过前序遍历求得。在前后序遍历中，一定是先把root和root的所有左子树节点遍历完之后才会遍历右子树，并且遍历的左子树的第一个节点就是左子树的根节点。同理，遍历的右子树的第一个节点就是右子树的根节点。第五步，观察发现，上面的过程是递归的。先找到当前树的根节点，然后划分为左子树，右子树，然后进入左子树重复上面的过程，然后进入右子树重复上面的过程。最后就可以还原一棵树了。该步递归的过程可以简洁表达如下：1 确定根,确定左子树，确定右子树。2 在左子树中递归。3 在右子树中递归。4 打印当前根。这样，我们就可以画出二叉树的形状，如上图所示，这里就不再赘述。那么，前序遍历: & & & & GDAFEMHZ编程求法：（并且验证我们的结果是否正确）#include &iostream&
#include &fstream&
#include &string&
struct TreeNode
struct TreeNode*
struct TreeNode*
TreeNode* BinaryTreeFromOrderings(char* inorder, char* aftorder, int length)
if(length == 0)
return NULL;
TreeNode* node = new TreeN//Noice that [new] should be written out.
node-&elem = *(aftorder+length-1);
std::cout&&node-&elem&&std::
int rootIndex = 0;
for(;rootIndex & rootIndex++)//a variation of the loop
if(inorder[rootIndex] ==
*(aftorder+length-1))
node-&left = BinaryTreeFromOrderings(inorder, aftorder , rootIndex);
node-&right = BinaryTreeFromOrderings(inorder + rootIndex + 1, aftorder + rootIndex , length - (rootIndex + 1));
int main(int argc, char** argv)
char* af=&AEFDHZMG&;
char* in=&ADEFGHMZ&;
BinaryTreeFromOrderings(in, af, 8);
printf(&\n&);
}输出结果：GDAFEMHZ
08-2404-0411-0610-1410-1109-2509-2506-0108-0303-20
阅读本文后您有什么感想? 已有23人给出评价!
名称大小下载这篇文章用来回顾二叉搜索数的以下操作:
查找最大值
查找最小值
查找指定值
获取指定属性
获取总节点/叶节点数量
获取二叉树的高度(根的高度为1)
二叉树的结构定义:
1 struct TreeNode{
TreeNode():data(),left(nullptr),right(nullptr){}
这是一些typedef,一般传参的时候用SearchTree,声明变量的时候用Position,避免混之.
1 struct TreeN
2 typedef int ELEMENT;
3 typedef TreeNode *
4 typedef TreeNode *
0.类中提供的API
1 class CBinTree
CBinTree(void);
~CBinTree(void);
// Return true when it's empty
bool isEmpty() ;
// Insert a element.
size_t _insert_(ELEMENT &_data);
// Delete a element.
size_t _delete_(ELEMENT &_data);
// Traversal of preorder/inorder/postorder/sequence order.
void traversalPre();
void traversalIn();
void traversalPos();
void traversalSeq();
// Find something.
Position findMin();
Position findMax();
Position find(ELEMENT &_data);
// Get the number of node/leafnode.
void getNodeNum(int * _nodenum,int * _leafnodenum);
// Get the height of tree
int getTreeHeight();
// Show this tree
void showThisTree();
37 private:
// Record the size of nodes
// The root of binary tree
SearchTree stR
42 private:
SearchTree insert_specific(ELEMENT &_data,SearchTree & _T);
SearchTree delete_specific(ELEMENT &_data,SearchTree &_T);
void traversalPre_specific(SearchTree _T);
void traversalIn_specific(SearchTree _T);
void traversalPos_specific(SearchTree _T);
void traversalSeq_specific(SearchTree _T);
Position findMin_specific(SearchTree _T);
Position findMax_specific(SearchTree _T);
Position find_specific(SearchTree _T,ELEMENT &_data);
int getTreeHeight_specific(SearchTree _T);
void getNodeNum_specific(SearchTree _T,int * _nodenum,int * _leafnodenum);
void showThisTree_specific(SearchTree _T);
　　具体实现都在对应的*_specific函数中;
　　因为二叉查找树的平均深度是O(logN),所以一般不用担心栈空间会被用尽.
　　由于前/中/后序遍历只是把输出函数换了个位置,故这里只放出中序遍历的代码:
1 void CBinTree::traversalIn_specific(SearchTree _T){
traversalIn_specific(_T-&left);
printf(&%d &,_T-&data);
traversalIn_specific(_T-&right);
　　层序遍历:
　　　　利用了STL的队列.
1 void CBinTree::traversalSeq_specific(SearchTree _T){
// Remember the first node
std::queue&Position& QN
QNode.push(_T);
// Save the dequeued node
Position popN
while (!QNode.empty())
// DeQueue
popNode = QNode.front();
QNode.pop();
// Output the first node of QNode
printf(&%d &,popNode-&data);
// EnQueue
if (popNode-&left)
QNode.push(popNode-&left);
if (popNode-&right)
QNode.push(popNode-&right);
　　这里我是用循环实现的,如此类似于链表的操作,简单易懂.
　　基于搜索二叉树的定义出发,代码如下:
1 Position CBinTree::findMin_specific(SearchTree _T){
Position minNodePos = _T;
while (minNodePos-&left)
minNodePos = minNodePos-&
return minNodeP
10 Position CBinTree::findMax_specific(SearchTree _T){
Position minNodePos = _T;
while (minNodePos-&right)
minNodePos = minNodePos-&
return minNodeP
19 Position CBinTree::find_specific(SearchTree _T,ELEMENT &_data){
Position foundNode = _T;
while (foundNode)
if (_data & foundNode-&data)
foundNode = foundNode-&
else if (_data & foundNode-&data)
foundNode = foundNode-&
return foundN
3.获取指定属性:
　获取总结点和叶子节点的数量&&&&&&&&&&&&&&&&&&&&
　　　　利用层序遍历的方式可以直接解决这两个问题.
　　　　_nodenum是总结点的数量,_leafnodenum是叶节点的数量.调用者需要传递其指针以便计算.
1 void CBinTree::getNodeNum_specific(SearchTree _T,int * _nodenum,int * _leafnodenum){
Position T = _T;
*_nodenum = 0;
*_leafnodenum = 0;
// Remember the first node
std::queue&Position& QN
QNode.push(T);
(*_nodenum) ++ ;
// Save the dequeued node
Position popN
while (!QNode.empty())
// DeQueue
popNode = QNode.front();
QNode.pop();
// Output the first node of QNode
// printf(&%d\n&,popNode-&data);
// EnQueue
if (popNode-&left)
QNode.push(popNode-&left);
(*_nodenum) ++ ;
if (popNode-&right)
QNode.push(popNode-&right);
(*_nodenum) ++ ;
// To determine whether the leafnode
if (!popNode-&left && !popNode-&right)
(*_leafnodenum) ++;
&获取二叉树的高度(根的高度为1)
这里的递归很奇妙:),递归都很有魔法不是么?
思路是递归计算每条分支的高度,相比较取最大的那个,听起来很简单.具体的实现方式居然是从叶子节点开始返回1,然后递归向上不断的加1,这一点很有趣.
这也是在最后&+1&的原因(魔法).
可以将这八行代码缩短为三行.但我认为这样阅读起来很舒服.
1 int CBinTree::getTreeHeight_specific(SearchTree _T){
lh = getTreeHeight_specific(_T-&left),
rh = getTreeHeight_specific(_T-&right);
return (lh & rh)?lh+1:rh+1;
&4.行为操作:
　　插入操作是利用二叉树天生的递归特性一个典例.
　　我以前一直不太理解递归如何保持新创建节点与其父节点的关联性.
　　后来发现漂亮的地方在与利用递归的返回值,与即将开始递归前的等待被赋值(&_T-&left =&),正是此赋值语句保持了节点之间的关系.
　　但是这也是一个问题,因为对于已经确定关系的节点而言岂不是要多次赋值(建立连接),即新节点加入之后,以上的节点还要继续赋值以再建立已经存在的连接.
　　而使用循环的话解可以避免这样的问题,只需新建立一个节点,与其父节点连接就大功告成,但是我试过,代码写起来没有递归的好看 :)
　　太漂亮了,献上代码敬之.
1 SearchTree CBinTree::insert_specific(ELEMENT &_data,SearchTree & _T){
if (_T == nullptr)
// Create a new node
_T = new TreeN
_T-&data = _
// Return to the father node ,tell him this node be created already.
// return T;
else if (_data & _T-&data)
_T-&left = insert_specific(_data,_T-&left);
else if (_data & _T-&data)
_T-&right = insert_specific(_data,_T-&right);
// Back to the above node,remain their linear relation.
return _T;
　　花点时间总结删除操作.我确实花了点时间理解 :(
　　这里的递归也是太漂亮了.
　　删除节点的情况可以分为三种,即节点间的连接方式种类.
　　有2个子节点
　　有1个子节点
　　有0个子节点
　　最困难的莫过于删除第一种情况的节点了.在此之前复习一下后两种的删除方法:
　　对于2.当前节点直接被非空的子节点替换即可,注意释放原先节点.
　　对于3.删除就好,在利用魔法的递归,将此节点(已经被置为nullptr)返回给他的父节点.
　　好了那么对于1.的解决办法如下:
　　将被删除的节点与右子树中最小值或者左子树中最大值替换(从比它小的中找个最大的,比它大的中找个最小的).
　　可行的理由是:对于一棵二叉树来说,最大值或最小值所在的节点的子节点数量是一个或两个.这不就转换为了2./3.种情况了嘛.
　　再调用处理2./3.的函数即可.
　　[8-15]行很像insert的查找过程.
　　[22-24]行是替换当前节点的值,再把那个用来替换的节点删除.
　　[30-40]行是在处理2./3.种情况,保存当前节点.在被替换后,释放保存节点,此处是任何删除操作的必经之处.很漂亮的处理.
1 SearchTree CBinTree::delete_specific(ELEMENT &_data,SearchTree &_T){
// Search node to delete
if (_data & _T-&data)
_T-&left = delete_specific(_data,_T-&left);
else if (_data & _T-&data)
_T-&right = delete_specific(_data,_T-&right);
// Search Done!
// Two chidren.
else if (_T-&left && _T-&right)
// Replace with smallest in right subtree.
// Or tmp = findMin_specific(_T-&left);
tmp = findMin_specific(_T-&right);
_T-&data = tmp-&
_T-&right = delete_specific(tmp-&data,_T-&right);
// One or zero chidren.
if (!_T-&left)
else if (!_T-&right)
return _T;
5.showThisTree()
　　正如名字那样,他的功能是把二叉树显示出来.
　　像这样:
　　虽然没有连线,但是看看二叉树长什么样子也挺有趣的.
　　代码敬上,主要用于后面AVL树的检验,见笑了.
1 void CBinTree::showThisTree_specific(SearchTree _T){
std::ofstream treeShow(&treeShow.txt&,std::ios::out);
if (!treeShow.is_open())
int treeHeight = getTreeHeight();
int showRootBlank = (int)pow(2,treeHeight);
// Remember the first node
std::queue&Position& QN
QNode.push(_T);
// 当前层显示出节点的数量
levelShowSize
// 所有显示节点的数量
totalShowSize
// 当前层数
// Save the dequeued node.
Position popN
// Size is the num of nodes.
while (totalShowSize != size)
// DeQueue
popNode = QNode.front();
QNode.pop();
// 节点已经输出,对输出的节点进行计数
levelShowSize ++;
// 对有效节点的进行计数,用于循环退出
if (popNode-&data != 666666)
totalShowSize ++;
// 判断空格的输出数量 第一次输出需要/2,后面的不需要,具体请画图会意.
int blankSize = (levelShowSize == 1)?showRootBlank/2:showRootB
for (int i = 0;i & blankSize-1;i++)
printf(& &);
treeShow&&& &;
// 显示节点值
// 显示一个假节点
if (popNode-&data == 666666)
printf(& &);
treeShow&&& &;
// 显示一个真节点
printf(&%d&,popNode-&data);
treeShow&&popNode-&
// 判断这层是否已经完结
if (levelShowSize == pow(2,levelSize))
levelSize ++;
levelShowSize = 0;
showRootBlank = showRootBlank / 2 ;
printf(&\n&);
treeShow&&&\n&;
// EnQueue operation
// 假节点 or 叶子节点
if ((!popNode-&left) && (!popNode-&right))
Position fakeNode = new TreeN
fakeNode-&data = 666666;
QNode.push(fakeNode);
QNode.push(fakeNode);
// 只含有左节点
else if (popNode-&left && !popNode-&right)
QNode.push(popNode-&left);
// As a right node push to qeueu
Position fakeNode = new TreeN
fakeNode-&data = 666666;
QNode.push(fakeNode);
// 只含有右节点
else if (popNode-&right && !popNode-&left)
// As a left node push to qeueu
Position fakeNode = new TreeN
fakeNode-&data = 666666;
QNode.push(fakeNode);
// Can't swap.
QNode.push(popNode-&right);
// 含有左右节点
else if (popNode-&left && popNode-&right)
QNode.push(popNode-&left);
QNode.push(popNode-&right);
printf(&\nwrite done!!\n&);
treeShow.close();
　　发现二叉树是一个递归的世界,这点从树的结构上就可以看出来.
　　其相关的算法用来学习递归的好工具,若自己去想真的得花点功夫.
　　递归很漂亮.
相关文章列表:用python来图形化显示C++代码中的二叉树
层次遍历的缺点，如果某一层两个节点之间存在NULL，那么层次遍历将无法显示他的清晰结构。
除非使用字符树，用#之类的去表示空节点，显然不适用于int树
下面分类两方面：1，搜索树的图形化显示；2、非搜索树的图形化显示
提供前序序列即可
from&drawtree&import&draw_bst
nums&=&[55,&30,&10,&5,&2,&20,&15,&25,&40,&35,&70,&60,&80,&75,&95]
draw_bst(nums)
&&&&&&&&&&&&&55
&&&&&&&&&&&&&/
&&&&&&&&&&&&/&&&\
&&&&&&&&&&&/&&&&&\
&&&&&&&&&&/&&&&&&&\
&&&&&&&&&30&&&&&&&70
&&&&&&&/&&&\&&&&&/&&&\
&&&&&&/&&&&&\&&&60&&&80
&&&&&10&&&&&40&&&&&&&/
\&&&&&/&&&&&&&/&&&\
&&&/&&&\&&&35&&&&&&75&&&95
2&&&&&/&&&\
&&&&&15&&&25
对于非搜索树，由C++代码提供前序和中序序列，这个时候如果想看二叉树长什么样子，用层次遍历会得到如下结果：
而把C++代码生成的前序
1，5，3，6，8，7
5，1，6，8，3，7
输入python，即可得到清晰地二叉树的图
from&binarytree&import&tree, bst, heap, pprint, Node
class&MyNode(Node):def&__init__(self, value, left=None, right=None):super(MyNode,&self).__init__(value)self.__setattr__('left', left)self.__setattr__('right', right)def&construct_tree(pre_order, mid_order):if&len(pre_order)&==&0:return&Noneroot_data&=&pre_order[0]for&i&in&range(0,&len(mid_order)):if&mid_order[i] ==&root_data:breakleft&=&construct_tree(pre_order[1:&1&+&i], mid_order[:i])right&=&construct_tree(pre_order[1&+&i:], mid_order[i&+&1:])return&MyNode(root_data, left, right)if&__name__&==&'__main__':pre_order&= [1,5,3,6,8,7]mid_order&= [5,1,6,8,3,7]my_tree&=&construct_tree(pre_order, mid_order)pprint(my_tree)
pycharm输出
注意：目前网上不存在生成扩展序列的C++代码，也就是说生成用#来表示NULL节点的序列，故采用上面的方法。
已投稿到：
以上网友发言只代表其个人观点，不代表新浪网的观点或立场。工具类服务
编辑部专用服务
作者专用服务
二叉树结构的文本模式显示
二叉树在数据结构的教学中是非常重要的一类非线性结构,在上机编程和调试的过程中如何快速有效直观地显示这类非线性结构直接影响着教与学的效率,为此提出了一种文本模式的二叉树结构显示方法;该方法利用’-’、’/’和’\’三种特殊字符把子结点和父结点连接起来,使用队列对二叉树进行层序输出.在队列中采用空指针NULL代表空结点,同时用一个新结点end表示每一层的结束.该方法不仅适用于顺序存储的二叉树也适用于链式存储的二叉树,进行适当修改也可顺利地显示3阶B_树,因此可以作为数据结构教与学的有效手段之一.
JIANG Shun-liang
作者单位：
南昌大学计算机系,江西南昌,330029
年，卷(期)：
机标分类号：
在线出版日期：
基金项目：
国家自然科学基金
本文读者也读过
相关检索词
万方数据知识服务平台--国家科技支撑计划资助项目（编号：2006BAH03B01）(C)北京万方数据股份有限公司
万方数据电子出版社