Question

请编写一个判别给定二叉树是否为二叉排序树的算法

请编写一个判别给定二叉树是否为二叉排序树的算法请编写一个判别给定二叉树是否为二叉排序树的算法，设二叉树的结点为（lChild，data，rChild），其中data为二叉排序树的关键字

Answer 1

1、首先打开VC++6.0。

2、选择文件，新建。

3、选择C++ source file 新建一个空白文档。

4、首先声明头文件。

5、定义树的结点结构typedef struct TreeNode{ char data;/*树中结点的数据是一个字符*/ struct TreeNode *lchild; struct TreeNode *rchild;}TREENODE;。

6、声明变量，int NodeNum = 0;/*统计数的结点数*/int LeafNum = 0;/*统计数的叶子结点数*/char ch[] = {'a', 'b', 'c', ' ', ' ', 'd', ' ', ' ', 'e',  'f', ' ', ' ', 'g', ' ', ' '};int inc = 0;。

7、运行得到结果。

Answer 2

二叉排序树的特点:
若根结点的左子树不空,则左子树上所有结点的值均小于它的根结点的值.
若根结点的右子树不空,则右子树上所有结点的值均大于它的根结点的值

如果左子树结点的值比根结点的大,或者右子树结点的值比根结点的小,
则不是二叉排序树.

测试结果1:
创建二叉树,输入先序遍历序列 (0是空结点):5 3 1 0 0 0 7 6 0 0 0

(非递归)判定: 是 二叉排序树
(递归法)判定: 是 二叉排序树

扩展二叉树示意图:
          5
      /      \
     3        7
    / \      / \
   1   0    6   0
  / \      / \ 
 0   0    0   0


测试结果2:
创建二叉树,输入先序遍历序列 (0是空结点):5 1 3 0 0 0 7 6 0 0 0

-----结点 1 有错误.
(非递归)判定: 不是 二叉排序树
(递归法)判定: 不是 二叉排序树

扩展二叉树示意图:
          5
      /      \
     1        7
    / \      / \
   3   0    6   0
  / \      / \ 
 0   0    0   0


//C语言测试程序
#include<stdio.h>
#include<stdlib.h>
struct Bitree
{
    int data;
    struct Bitree *lChild;
    struct Bitree *rChild;
};

//用"先序遍历"算法创建二叉树
void CreateBiTree(struct Bitree **bt)
{
    int s;
    scanf("%d",&s); //输入数据
    if(s==0)        //0是空节点
    {
        *bt=NULL;
    }
    else
    {
        *bt=(struct Bitree *)malloc(sizeof(struct Bitree));
        (*bt)->data=s;
        CreateBiTree(&((*bt)->lChild));
        CreateBiTree(&((*bt)->rChild));
    }
}

//判别是否为二叉排序树(非递归)
int checkTreeByStack(struct Bitree *root)
{
    struct stack_node //栈的结构体
    {
        struct Bitree *bt;
    };
    struct stack_node stack[100]; //栈
    int top=0;                    //栈顶, 从top=1开始存放数据
    struct Bitree *p;             //当前二叉树结点

    if(root==NULL)
    {
        printf("\n-----这是空树\n");
        return 1;
    }

    p=root;
    top++;
    stack[top].bt=p;  //根结点入栈
    while(top != 0)
    {
        p=stack[top].bt;
        top--;
        if(p->rChild != NULL)
        {
            if(p->rChild->data < p->data)
            {
                printf("\n-----结点 %d 有错误.\n",p->data);
                return 0;  // 0:不是二叉排序树
            }
            top++;
            stack[top].bt=p->rChild;  //右分支入栈
        }
        if(p->lChild != NULL)
        {
            if(p->lChild->data > p->data)
            {
                printf("\n-----结点 %d 有错误.",p->data);
                return 0;  // 0:不是二叉排序树
            }
            top++;
            stack[top].bt=p->lChild;  //左分支入栈
        }
    }
    return 1; // 1:是二叉排序树
}

//判别是否为二叉排序树(递归法)
int IsSearchTree(struct Bitree *root)
{
    if(!root)
    {
        return 1;
    }
    else if(!(root->lChild) && !(root->rChild))   //左,右子树都没有
    {
        return 1;
    }
    else if((root->lChild) && !(root->rChild))    //只有左子树
    {
        if(root->lChild->data > root->data)
        {
            return 0;  // 0:不是二叉排序树
        }
        else
        {
            return IsSearchTree(root->lChild);
        }
    }
    else if((root->rChild) && !(root->lChild))   //只有右子树
    {
        if(root->rChild->data < root->data)
        {
            return 0;  // 0:不是二叉排序树
        }
        else
        {
            return IsSearchTree(root->rChild);
        }
    }
    else    //左,右子树都有
    {
        if((root->lChild->data > root->data) || (root->rChild->data < root->data))
        {
            return 0;  // 0:不是二叉排序树
        }
        else
        {
            return ( IsSearchTree(root->lChild) && IsSearchTree(root->rChild) );
        }
    }
}

int main()
{
    struct Bitree *root;
    int result;
    int retOther;

    printf("创建二叉树,输入先序遍历序列 (0是空结点): ");
    CreateBiTree(&root);

    //判别是否为二叉排序树(非递归)
    result = checkTreeByStack(root);
    printf("\n(非递归)判定: ");
    if(result==0)
    {
        printf("不是 二叉排序树\n");
    }
    else
    {
        printf("是 二叉排序树\n");
    }

    //判别是否为二叉排序树(递归法)
    retOther = IsSearchTree(root);
    printf("(递归法)判定: ");
    if(retOther == 0)
    {
        printf("不是 二叉排序树\n");
    }
    else
    {
        printf("是 二叉排序树\n");
    }

    printf("\n");
    return 0;
}