中序可以创建二叉树吗

论坛 期权论坛 期权     
baizhengqaun   2018-4-26 13:58   5580   1
中序的递归结束条件是左子树为空,但是当树还没有的时候,怎么知道什么时候左子树为空呢,所以我觉得不可以
分享到 :
0 人收藏

1 个回复

倒序浏览
2#
wqws16623  3级会员 | 2018-4-30 01:56:36 发帖IP地址来自
只有先序、后序、层序可以用来创建二叉树(且要添加虚空节点),中序是不可以的。
原因很简单,因为即使添加了虚空节点,中序序列仍然不可以唯一确定一棵二叉树。(那何来创建二叉树之说?)
如:设一棵带虚空节点(用'#'表示)的二叉树的中序遍历序列为:#B#A#D#C#
我们可以同时找到至少两棵符合条件的二叉树:
(1)
      A
    B         C
#    #   D    #
          #   #
(2)
                 C
            A      #
       B      D
     #  #   #  #
而先序和后序就不同了。
如:第一棵树的先序序列:AB##CD###    //你也找不到另外一棵二叉树的先序序列和这棵树相同
       第二棵树的先序序列:CAB##D###    //同上
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

积分:
帖子:
精华:
期权论坛 期权论坛
发布
内容

下载期权论坛手机APP