二叉排序树BST 基本操作 二

1.定义

     二叉排序树(Binary Search Tree)又称二叉搜索(查找)树，其定义如下：

    (1)若它的左子树非空，则左子树上所有结点的权值都比根结点的权值小;

    (2)若它的右子数非空，则右子树上所有结点的权值都比根结点的权值大;

    (3)左、右子树本身又是一棵二叉排序树。

以上既是二叉排序树的定义，同时也是它的性质。从定义可以看出，二叉排序树的定义是一个递归的定义。对于一棵二叉排序树的中序遍历则是一个递增有序序列。

2.二叉排序树的插入Insert

   根据二叉排序树的递归定义，进行插入操作的时候可以用递归实现，其插入过程如下：

   (1)如果二叉排序树为空，则创建一个关键字为key的结点，并将其作为根结点;

   (2)否则将key和根结点的key值比较，若相等则返回;

       1)若key值小于根结点的key值，判断根结点的左孩子是否为空，

          如果为空，则创建一个关键字为key的结点，并将该结点作为根结点的左孩子;

          如果不为空，则递归插入到该根结点的左子树当中。

       2)若key值大于根结点的key值，判断根结点的右孩子是否为空，

          如果为空，则创建一个关键字为key的结点，并将该结点作为根结点的右孩子;

          如果不为空，则递归插入到该根结点的右子树当中。

 

 

#include<stdio.h>
#include<malloc.h>
#include<iostream>
#include<string>
using namespace std;
typedef int ElemType;//假定关键字类型为整数
typedef struct node
{
    ElemType key;
    struct node * left,* right;
} BSTNode;

BSTNode * search(BSTNode *root,ElemType key)//查找某个关键字是否存在
{
    if(root==NULL||root->key==key)
        return root;
    else if(key<root->key)
        search(root->left,key);
    else
        search(root->right,key);
}

BSTNode * FindMin(BSTNode *root)//递归查找
{
    if(root==NULL)
    return NULL;
    else if(root->left==NULL)
        return root;
    else
        return FindMin(root->left);
}
BSTNode *FinMax(BSTNode *root)//非递归查找
{
    if(root!=NULL)
        while(root->right!=NULL)
            root=root->right;
    return root;
}

void dfs(BSTNode *root) //else if只是深度搜索一个分支，没有回溯,
//去掉else,深度遍历了一下
/*
5 8 7 9 3 2 4 0
2
9
key=5
key=3
key=2
key=4
key=8
key=7
key=9
*/
{
    printf("key=%d\n",root->key);
    if(root->left)
        dfs(root->left);
    if(root->right)
        dfs(root->right);
}


void insert(BSTNode *&root,ElemType key) //注意这里为什么用指针的引用
{
    if(root==NULL) //如果该树为空
    {
        root=(BSTNode*)malloc(sizeof(BSTNode));
        root->key=key;
        root->left=NULL;
        root->right=NULL;
    }
    else
       {
        if(root->key==key) //1、如果已经存在，则直接返回
            return;
        else if(root->key>key) //2、key小于根结点的权值
             {
                if(root->left==NULL) //root的左孩子为空，则创建一个结点作为root的左孩子
                {
                    BSTNode*p=(BSTNode *)malloc(sizeof(BSTNode));
                    p->key=key;
                    p->left=NULL;
                    p->right=NULL;
                    root->left=p;//直接挂在它的左子树
                }
                else
                    insert(root->left,key); //递归插入到左子树中
            }
        else                    //3、key大于根结点的权值
        {
            if(root->right==NULL) //root的右孩子为空，则创建一个结点作为root的右孩子
            {
                BSTNode*p=(BSTNode *)malloc(sizeof(BSTNode));
                p->key=key;
                p->left=NULL;
                p->right=NULL;
                root->right=p;
            }
            else
                insert(root->right,key); //递归插入到右子树中
        }
    }
}

int main()
{
    BSTNode *root=NULL;
    int key;
    scanf("%d",&key);
    while(key)//假设key=0是输入结束标志
    {
        insert(root,key);
        scanf("%d",&key);
    }

    printf("%d\n",FindMin(root)->key);
    printf("%d\n",FinMax(root)->key);
    dfs(root);
    return 0;
}

/*
5 8 7 9 3 2 4 0
2
9
key=5
key=3
key=2
Press any key to continue
*/