qq_26166073
2018fighting
2015-08-11 13:01
采纳率: 23.1%
浏览 9.6k
已采纳

二叉排序树的中序遍历结果是递增序列?

图片说明

我看书上说“二叉排序树的中序遍历结果是递增序列”,然后我随便写了几个数,生成二叉排序树,对其进行中序遍历,结果如上图,它不是递增序列啊???是我知识上有什么漏洞吗?求教啊~~

  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 邀请回答

4条回答 默认 最新

  • caozhy
    已采纳

    你的图的问题是,你这个不是合法的二叉排序数

    http://baike.baidu.com/link?url=C-X-xagLwE2Otrn-Y3bq3BNbGaJPDTPlB3DHwv7cOLzlmKKAztiwYhxl275ZdZn2wXRlVKxNI7NfKUQJXkUiyq

    二叉排序树或者是一棵空树,或者是具有下列性质的二叉树:
    (1)若左子树不空,则左子树上所有结点的值均小于它的根结点的值;
    (2)若右子树不空,则右子树上所有结点的值均大于或等于它的根结点的值;
    (3)左、右子树也分别为二叉排序树;
    (4)没有键值相等的节点。

    注意:左子树上所有结点的值均小于它的根结点的值

    点赞 评论
  • caozhy

    是的,排序二叉树的左子节点必然小于等于父节点,右子节点必然大于等于父节点,中序遍历先遍历左子,然后是自身,然后是右子,所以肯定是递增。

    点赞 评论
  • lcsawyer
    lcsawyer 2015-08-11 13:14

    7插入的时候叉错了,应先与4比较,比四大插入右子树,再与右子树的第一个节点6比较,比6大插入6的右子树

    点赞 评论
  • u013123021
    earthquake_aaa 2015-08-11 14:05

    你的 7 插入的就有问题,插入任何一个数都要先从树的根节点开始比较起,大右小左,然后依次到叶子节点结束。
    中序遍历就是先访问左子然后再是本身最后才是右子,所以肯定是升序,不然二叉排序树就没啥意义了。

    点赞 评论

相关推荐