Question

这是一道数据结构的题：试写一个判别给定二叉树是否为二叉排序树的算法，设此二叉树以二叉链表作存储结构

树中结点的关键字均不同。

Answer 1

用递归：

a=当前节点是否为排序树，是为1，不是为0

f(x)=1 当x为叶节点 

f(x)= a&&f(x->lchid)&&f(x-rchild)  当x非叶节点

----------------------------------------------------------------------

int IsAVTree(BiTree t)

{

int a=1;

if(t->Child==NULL&&t->Rchild==NULL)  return 1;  //叶子节点判断

if((t->Lchild->data>t->data)||(t->Rchild->datadata)) 

{

a=0;

a=a&&(isAVTree(t->Lchild))&&(IsAVTree(t->Rchild));

}

return a;

}

扩展资料：

构成递归需具备的条件：

一、子问题须与原始问题为同样的事，且更为简单；

二、不能无限制地调用本身，须有个出口，化简为非递归状况处理。

在数学和计算机科学中，递归指由一种（或多种）简单的基本情况定义的一类对象或方法，并规定其他所有情况都能被还原为其基本情况。

例如，下列为某人祖先的递归定义：

某人的双亲是他的祖先（基本情况）。某人祖先的双亲同样是某人的祖先（递归步骤）。斐波纳契数列（Fibonacci Sequence），又称黄金分割数列，指的是这样一个数列：1、1、2、3、5、8。

参考资料来源：百度百科-递归

Answer 2

int IsSearchTree(const BTNode *t){
if(!t) //空二叉树情况
return 1;
else if(!(t->lchild) && !(t->rchild))//左右子树都无情况
return 1;
else if((t->lchild) && !(t->rchild)){//只有左子树情况
if(t->lchild->data>t->data)
return 0;
else
return IsSearchTree(t->lchild);
}
else if((t->rchild) && !(t->lchild)){//只有右子树情况
if(t->rchild->data<t->data)
return 0;
else
return IsSearchTree(t->rchild);
}
else{ //左右子树全有情况
if((t->lchild->data>t->data) ||(t->rchild->data<t->data))
return 0;
else
return IsSearchTree(t->lchild) && IsSearchTree(t->rchild);
}
}

已经上机验证成功，楼上的写的太随意了吧，各种情况都需要考虑地。

Answer 3

小哥哥，用递归：
a=当前节点是否为排序树，是为1，不是为0
f(x)=1 当x为叶节点
f(x)= a&&f(x->lchid)&&f(x-rchild) 当x非叶节点
----------------------------------------------------------------------
int IsAVTree(BiTree t)
{
int a=1;
if(t->Child==NULL&&t->Rchild==NULL) return 1; //叶子节点判断
if((t->Lchild->data>t->data)||(t->Rchild->data<t->data))
{
a=0;
a=a&&(isAVTree(t->Lchild))&&(IsAVTree(t->Rchild));
}
return a;
}

Answer 4

递归方法
void alvtree(bittree *t)
{
int if(!t) return 1;
else if(t->lchild!=null&&t->rchild!=null)
{ if(t->lchild->data<=t->data&&t->rchild->data>=t->data)

{ alvtree(t->lchild);
alvtree(t->rchild);

}

else return 0;

}

else if (t->lchild!=null&&t->rchild==null)
{ if(t->lchild->data<=t->data)

alvtree(t->lchild);

else return 0;

}
else if (t->rchild!=null&&t->lchild==null)
{
if (t->rchild->data>=t->data)

alvtree(t->rchild);

else return 0;

}

}

自己写的情况应该都考虑到了，采用的是递归算法。