第41题
(13 分)已知非空二叉树 T 的结点值均为正整数，采用顺序存储方式保存，数据结构定义如下：
1 2 3 4 | typedef struct {
int SqBiTNode[MAX_SIZE];
int ElemNum;
} SqBiTree;
|
T 中不存在的结点在数组 SqBiTNode 中用-1 表示。例如，对于下图所示的两棵非空二叉树 T1
和 T2，
T1 的储存结果如下：
T1.SqBiTNode
T2.ElemNum=10
T2 的储存结果如下：
T2.SqBiTNode
T2.ElemNum=11
请设计一个尽可能高效的算法，判定一棵采用这种方式存储的二叉树是否为二叉搜索树，若
是，则返回 true，否则，返回 false。要求：
（1）给出算法的基本设计思想。
（2）根据设计思想，采用 C 或 C++语言描述算法，关键之处给出注释。
【答案解析】
【答案一】
（1）算法的基本设计思想
对于采用顺序存储方式保存的二叉树，根结点保存在 SqBiTNode[0]中；当某结点保存在
SqBiTNode[i]中时，若有左孩子，则其值保存在 SqBiTNode[2i+1]；若有右孩子，则其值保
存在 SqBiTNode[2i+2]中；若有双亲结点，则其值保存在 SqBiTNode[(i-1)/2]中。
二叉搜索树需要满足的条件是：任一结点值大于其左子树中的全部结点值，小于其右子
树中的全部结点值。中序遍历二叉搜索树得到一个升序序列。
使用整型变量 val 记录中序遍历过程中已遍历结点的最大值，初值为一个负整数。若当
前遍历的结点值小于等于 val，则算法返回 false，否则，将 val 的值更新为当前结点的值。
（2）算法实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | #define false 0
#define ture 1
typedef int bool ;
bool judgeInOrderBST( SqBiTree bt , int k , int * val )
{ if ( k < bt.ElemNum && bt.SqBiTNode [k] ! = -1 )
{
if ( !judgeInOrderBST ( bt , 2 * k+1 , val ) ) return false;
if ( bt.SqBiTNode [k] <= * val ) return false;
* val = bt.SqBiTNode [k] ;
if ( !judgeInOrderBST ( bt , 2 * k+1 , val ) ) return false;
}
return ture;
}
|
【答案二】
（1）算法的基本设计思想
对于采用顺序存储方式保存的二叉树，根结点保存在 SqBiTNode[0]中；当某结点保存在
SqBiTNode[i]中时，若有左孩子，则其值保存在 SqBiTNode[2i+1]中；若有右孩子，则其值
保存在 SqBiTNode[2i+2]中；若有双亲结点，则其值保存在 SqBiTNode[(i-1)/2]中。
二叉搜索树需要满足的条件是：任一结点值大于其左子树中的全部结点值，小于其右子
树中的全部结点值。设置两个数组 pmax 和 pmin。根据二叉搜索树的定义，SqBiTNode[i]中
的值应该大于以 SqBiTNode[2i+1]为根的子树中的最大值（保存在 pmax[2i+1]中），小于以
SqBiTNode[2i+2]为根的子树中的最小值（保存在 pmin[2i+1] 中）。初 始 时， 用数 组
SqBiTNode 中前 ElemNum 个元素的值对数组 pmax 和 pmin 初始化。
在数组 SqBiTNode 中从后向前扫描，扫描过程中逐一验证结点与子树之间是否满足上述
的大小关系。
（2）算法实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 | #define false 0
#define ture 1
typedef int bool ;
bool judgeBST( SqBiTree bt )
{ int k , m , * pmin , * pmax ;
pmin = ( int * ) malloc ( sizeof ( int ) * ( bt.ElemNum ) ) ;
pmax = ( int * ) malloc ( sizeof ( int ) * ( bt.ElemNum ) ) ;
for ( k = 0 ; k < bt.ElemNum ; k++ )
pmin [k] = pmax [k] = bt.SqBiTNode [k] ;
for ( k = bt.ElemNum - 1 ; k > 0 ; k - - )
{ if ( bt.SqBiTNode [k] ! = -1 )
{ m = ( k - 1 ) / 2 ;
if ( k % 2 = = 1 && bt.SqBiTNode [m] > pmax [k] )
pmin [m] = pmin [k] ;
else if ( k % 2 = = 0 && bt.SqBiTNode [m] < pmin
[k] )
pmax [m] = pmax [k] ;
else return false ;
}
}
return ture ;
}
|