数据结构与算法参考答案(第十四周)

一、试写一个判别给定二叉树是否为二叉排序树的算法,设此二叉树以二叉链表作存储结构,且树中结点的关键字均不同。

答:

由分析可以知道,通过教材所学的知识我们很容易知道二叉排序树的特点。按照中序遍历的顺序,应当符合当前遍历到的节点值大于前一个遍历到的节点值,所以我们最终得到的中序遍历序列是一个有序序列,对于该题我们在遍历的过程中采用递归的方式进行判断。

该算法实现的伪代码如下:

/*

函数名称:判断是否为二叉排序树

传入参数:树的根节点tree

返回值:如果是返回true,否则返回false

*/

bool isBinaryTree(node tree){//判断是否二叉排序树

if(tree != NULL){

//如果左右孩子均为空

if(tree -> lchild == NULL && tree -> rchild == NULL) {

return true;  

}

else if(tree -> lchild == NULL)  {

if(tree -> info < tree -> rchild -> info){

return isBinaryTree(t->rchild);

}

else return false;

}

else if(tree -> rchild == NULL)  {

if(tree -> info > tree -> lchild -> info) {

return isBinaryTree(tree -> lchild);

}

else {

return false;

}

}

else{

if(tree -> info > tree -> lchild -> info && tree -> info < tree -> rchild -> info) {

return isBinaryTree(tree -> rchild) && isBinaryTree(tree -> lchild);

}

else {

return false;

}

}

}

}

算法分析:该算法通过递归的方式实现。思路简单,算法高效,这是解决判断是否是二叉排序树的较好的方法。

 

二、编写递归算法,从大到小输出给定二叉排序树中所有关键字不小于x的数据元素。

答:

由分析可以知道,本题需要在二叉排序树中输出不小于x的数据元素。由所学的知识很容易知道:从大到小输出二叉排序树中不小于x的元素,通过从右子树到左子树的递归实现。

该算法实现的伪代码如下:

/*

函数名称:输出不小于x的元素

函数传入参数:树的根节点T,需要比较的值x

返回值:void

*/

void Print(BiTree &T, int x)

{

    if(T != NULL) { //判断树是否为空

     return;

    }

    PrintBSTLx(T->rchild, x);

    if (T -> data < x) {

     return;

    }

    cout << T->data << "  ";

    PrintBSTLx(T->lchild, x);

}

算法分析:该算法通过递归的方式实现。思路简单,算法高效,利用二叉排序树所具有的独特性质用递归的方式进行输出。综上,这是解决该类问题的较好的算法。

上一篇:2020-11-29


下一篇:数据结构------树非递归遍历