Question

给定表（19.14.22.01.66.21.83.27.56.13.10）按元素在表中的次序构造一棵二叉排序树

为什么13是1的右子树而不是27的左子树

Answer 1

二叉排序树具有如下性质:
(1) 若左子树不空，则左子树上所有结点的值均小于或等于它的根结点的值；
(2) 若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值；
(3) 左、右子树也分别为二叉排序树.


元素（19.14.22.01.66.21.83.27.56.13.10）构造二叉排序树的过程如下:

加入19, 这是根结点. 往后但凡数值比19小的都属于左子树, 比19大的都属于右子树.

加入14, 数值比19小, 作为19的左子树.

      19
     /
   14

加入22, 数值比19大, 作为19的右子树.

      19
     /  \
   14   22

加入01, 数值比19, 14都小, 作为14的左子树.

      19
     /  \
   14   22
   /
  1

加入66, 数值比19, 22都大, 作为22的右子树.

      19
     /  \
   14   22
   /      \
  1       66

加入21, 数值比19大, 比22小, 作为22的左子树.

      19
     /   \
   14    22
   /    /  \
  1    21   66

加入83, 数值比19, 22, 66都大, 作为66的右子树.

      19
     /   \
   14    22
   /    /  \
  1    21   66
             \
              83

加入27, 数值比19, 22都大, 但是比66小, 作为66的左子树.

      19
     /   \
   14    22
   /    /  \
  1    21   66
           /  \
          27   83

加入56, 数值比19, 22都大, 比66小, 但是比27大, 作为27的右子树.

      19
     /   \
   14    22
   /    /  \
  1    21   66
           /  \
          27   83
           \
            56

加入13, 数值比19, 14都小, 但是比1大, 作为1的右子树.

      19
     /   \
   14    22
   /    /  \
  1    21   66
   \       /  \
    13    27   83
           \
            56

加入10, 数值比19, 14都小, 比1大, 但是比13小, 作为13的左子树.

      19
     /   \
   14    22
   /    /  \
  1    21   66
   \       /  \
    13    27   83
   /       \
  10        56

因为二叉树排序的根结点是19, 27比19大, 所以27肯定排在根结点19的右子树,
而13比19小, 所以13肯定排在根结点19的左子树, 故此,13不会是27的左子树.
根据二叉排序树的性质, 13是1的右子树.


//C语言测试程序
#include "stdio.h"
#include "stdlib.h"
struct tree
{
    int data;
    struct tree *left;
    struct tree *right;
};
typedef struct tree treenode;
typedef treenode *btree;

btree insertnode(btree root,int value) //插入新结点
{
    btree newnode;
    btree current;
    btree back;
    newnode=(btree)malloc(sizeof(treenode));
    newnode->data=value;
    newnode->left=NULL;
    newnode->right=NULL;
    if(root==NULL)
    {
        return newnode;
    }
    else
    {
        current=root;
        while(current!=NULL)
        {
            back=current;
            if(current->data > value)
               current=current->left;
            else
               current=current->right;
        }
        if(back->data > value)
            back->left=newnode;
        else
            back->right=newnode;
    }
    return root;
}

btree createBtree(int *data,int len) //创建二叉排序树
{
    btree root=NULL;
    int i;
    for(i=0;i<len;i++)
    {
        root=insertnode(root,data[i]);
    }
    return root;
}

void preOrder(btree ptr) //前序遍历
{
    if(ptr!=NULL)
    {
        printf("%d ",ptr->data);
        preOrder(ptr->left);
        preOrder(ptr->right);
    }
}

void inOrder(btree ptr) //中序遍历
{
    if(ptr!=NULL)
    {
        inOrder(ptr->left);
        printf("%d ",ptr->data);
        inOrder(ptr->right);
    }
}

void postOrder(btree ptr) //后序遍历
{
    if(ptr!=NULL)
    {
        postOrder(ptr->left);
        postOrder(ptr->right);
        printf("%d ",ptr->data);
    }
}

int main()
{
    btree root=NULL;

    int data[]={19,14,22,01,66,21,83,27,56,13,10};
    int n;
    int i;
    n=sizeof(data)/sizeof(data[0]);
    printf("原数组数据: ");
    for(i=0;i<n;i++)
    {
        printf("%d ",data[i]);
    }
    root=createBtree(data,n);
    printf("\n前序遍历序列: ");
    preOrder(root);
    printf("\n中序遍历序列: ");
    inOrder(root);
    printf("\n后序遍历序列: ");
    postOrder(root);

    return 0;
}