赞
踩
首先,想要确定唯一的二叉树,就需要知道二叉树的前序,中序或者二叉树的中序,后序。只有知道这两种其中的一种,就可确定唯一的二叉树。
//前序:根--左--右
//中序:左--根--右
//后序:左--右--根
特点可以总结为3条:
1.前序的开头第一个元素一定是根节点。
2.中序的根节点的左边是其左子树,右边是其右子树。
3.后序的最后一个元素一定是根节点。
举个例子说明一下:
前序:DBACEFGH
中序:ABCDFGHE
后序:ACBHGFED
二叉树图是如下的样式:
现在我们通过前序和中序进行二叉树的画法的讲解:
1.先观察前序,前序的第一个元素是D并根据特点1可知这个D一定是根节点。
2.在中序中找到D的位置并根据特点2可知D元素左边的所有元素属于左子树,右边的所有元素属于右子树。
3.先看左子树并在前序中找到相应的元素为BAC并结合特点1可知,B又是一个根节点。
4.在中序中找到B的位置,并结合特点2可知A是左子树,C是右子树。
5.同理,再分析右子树,在前序中找到相对应的元素EFGH并结合特点1可知E是一个根节点。
6.并在中序中找到相应的元素,并结合特点2可知FGH都为左子树。
7.同理,在前序中找到相对应的元素FHG并结合特点1可知F是一个根节点。
8.并在中序中找到相应的元素,并结合特点2可知HG都为右子树。
9.同理,在前序中找到相对应的元素HG并结合特点1可知G是一个根节点。
10.并在中序中找到相应的元素,并结合特点2可知H都为右子树。
通过这样的方法,我们可以准确的画出二叉树。
注:通过中序和后序并结合特点2和3也可以画出唯一的二叉树。
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。