一个判别给定二叉树是否为二叉排序树的算法，设此二叉树以二叉链表作存储结构。且树中结点的关键字均不同。
注意仔细研究二叉排序树的定义。易犯的典型错误是按下述思路进行判别：“若一棵非空的二叉树其左、右子树均为二叉排序树，且左子树的根的值小于根结点的值，又根结点的值不大于右子树的根的值，则是二叉排序树” （刘注：即不能只判断左右孩子的情况，还要判断左右孩子与双亲甚至根结点的比值也要遵循（左小右大）原则）。 若要采用递归算法，建议您采用如下的函数首部： bool BisortTree(BiTree T, BiTree&PRE) ，其中 PRE 为指向当前访问结点的前驱的指针。 （或者直接存储前驱的数值，随时与当前根结点比较） 一个漂亮的算法设计如下： int last=0 , flag=1 ; // last 是全局变量， 用来记录前驱结点值，只要每个结点都比前驱大就行。 int Is_BSTree(Bitree T) // 判断二叉树 T 是否二叉排序树，是则返回 1 ，否则返回 0 { if(T->lchild&&flag) Is_BSTree(T->lchild); if(T->data
data; if(T->rchild&&flag) Is_BSTree(T->rchild); return flag; }//Is_BSTree
举一反三
内容
- 0
在任意一棵非空二叉排序树中,删除某结点后又将其插入,则所得二排序叉树与原二排序叉树相同。[br][/br] [br][/br](判断题)
- 1
给定一棵树的二叉链表存储结构，把这棵树转换为二叉树后，这棵二叉树的形态是 。
- 2
某个二叉查找树（即二叉排序树）中进行查找时，效率最差的情形是该二叉查找树是（）。 A: 完全二叉树 B: 平衡二叉树 C: 单枝树 D: 满二叉树
- 3
下列关于树的表述正确的是__________。 A: 树不能采用顺序结构存储 B: 在树的二叉链表存储结构中，树的叶子结点对应的链表结点左右指针一定为NULL C: 在树的二叉链表存储结构中，易于求树中给点结点的全部孩子 D: 树与其对应的二叉树结点个数可能不同 E: 树的后根遍历序列与其对应的二叉树的后序遍历序列一定一致
- 4
完全二叉树一定是二叉平衡树