二叉排序树（BST）的判定

Question

【问题描述】试写一个判别给定二叉树是否为二叉排序树的算法。以前序遍历序列和中序遍历序列给出该二叉树的结点，并创建该二叉树。然后再进行判断。请注意，树中结点关键字可能相同。
【样例输入1】
6 4 5 8 6 9 0
4 5 6 6 8 9 0
【样例输出1】
true
【样例输入2】
6 4 7 8 0
4 7 6 8 0
【样例输出2】
false
【提示】若直接根据给定的中序是否有序来进行判断，此种判断方法不得分。务必先创建二叉树的链式存储，再对其进行判断。

#include<iostream>
using namespace std;
#include<cstdlib>
int i=0;
int ret[50];
typedef struct Node
{
    int key;
    struct Node*LChild,*RChild;
}BSTNode,*BSTree;
BSTree build(int pre[],int in[],int length)
{
    if(length==0)
        return NULL;
    int i,leftlength,rightlength;
    int root;
    BSTree T;
    root=pre[0];
    for(i=0;i<length;i++)
    {
        if(in[i]==root)
            break;
    }
    leftlength=i;
    rightlength=length-i-1;
    T=(BSTree)malloc(sizeof(BSTree));
    T->key=root;
    T->LChild=NULL;
    T->RChild=NULL;
    T->LChild=build(&pre[1],&in[0],leftlength);
    T->RChild=build(&pre[i+1],&in[i+1],rightlength);
    return T;
}
bool judge(BSTree bt)
{
    if (bt == NULL) return true;
    if (bt->LChild != NULL && bt->LChild->key >= bt->key) return false;
    if (bt->RChild != NULL && bt->RChild->key <= bt->key) return false;
    return judge(bt->LChild) && judge(bt->RChild);
}
/*void InOrder(BSTree bt, int ret[], int &i)
{
    if(bt==NULL)
        return;
    else
    {
        InOrder(bt->LChild, ret, i);
        ret[i]=bt->key;
        i++;
        InOrder(bt->RChild, ret, i);
    }
}

bool judge(BSTree bt)
{
    int ret[50];
    int i = 0;
    InOrder(bt, ret, i);
    for(int j=1; j<i; j++)
    {
        if(ret[j]<ret[j-1])
            return false;
    }
    return true;
}*/

int main()
{
    int arr1[50],arr2[50];
    int i=0,j=0,cot=0,n;
    BSTree bt;
    bt=(BSTree)malloc(sizeof(BSTNode));
    while(cin>>n&&n!=0)
    {
        arr1[i]=n;
        i++;
        cot++;
    }
    while(cin>>n&&n!=0)
    {
        arr2[j]=n;
        j++;
    };
    bt=build(arr1,arr2,cot);
    if(judge(bt))
        cout<<"true";
    else
        cout<<"false";
    return 0;
}

请问为何用上面递归的judge函数不可行？比方说我说如6 4 7 8 0，4 7 6 8 0时会错误地输出true

Answer 1

• 以下回答由chatgpt基于相关博客总结生成:

  # 二叉排序树的节点类
  class BSTNode(object):
      def __init__(self, data):
          self.left = None
          self.right = None
          self.data = data
  
  # 将数组构建成二叉排序树
  def array_to_bst(array):
      if not array:
          return
      tree = BSTNode(array[0])
      for i in range(1, len(array)):
          node = BSTNode(array[i])
          p = tree
          while True:
              if node.data < p.data:
                  if not p.left:
                      p.left = node
                      break
                  else:
                      p = p.left
              else:
                  if not p.right:
                      p.right = node
                      break
                  else:
                      p = p.right
      return tree
  
  # 中序遍历，生成有序数组
  def inorder_traversal(tree):
      if not tree:
          return []
      res = []
      stack = []
      p = tree
      while p or stack:
          while p:
              stack.append(p)
              p = p.left
          p = stack.pop()
          res.append(p.data)
          p = p.right
      return res
  
  # 判断一棵二叉树是否为二叉排序树
  def is_bst(tree):
      if not tree:
          return True
      last_node = None
      stack = []
      p = tree
      while p or stack:
          while p:
              stack.append(p)
              p = p.left
          p = stack.pop()
          if last_node and p.data <= last_node:
              return False
          last_node = p.data
          p = p.right
      return True
  
  # 给定前序遍历序列和中序遍历序列，判断该二叉树是否为二叉排序树
  def is_bst_preorder_inorder(preorder, inorder):
      # 构建二叉排序树
      tree = array_to_bst(preorder)
      # 中序遍历，生成有序数组
      inorder_array = inorder_traversal(tree)
      # 判断是否为二叉排序树
      return inorder == inorder_array and is_bst(tree)