二叉排序树的中序遍历必然递增

题目引出的思考:

前面学习中,一般都是需要前序+中序或者后序+中序才能构建出一颗二叉树,故本道题中一开始并未给出中序遍历,心中疑惑便出,是否该二叉树不唯一?再细看是二叉排序树,仔细分析显然可得二叉排序树中的中序遍历必然是递增的,故排除自己的错误想法。

证明:

如果一棵非空二叉树(所有结点值均不相同)的中序遍历序列是从小到大有序 的,则该二叉树是一棵二叉排序树。

对于关键字为k的任一结点a,由中序遍历过程可知,在中序遍历序列中,它的左子树的所有结点的关键字排在k的左边,它的右子树的所有结点的关键字排在k的右边, 由于中序序列是从小到大排列的,所以结点a的左子树中所有结点的关键字小于k,结点a的右子树中所有结点的关键字大于k,这满足二叉排序树的性质,所以该二叉树是一棵二叉排序树。

原文地址:https://www.cnblogs.com/wangzheming35/p/13403025.html