二叉排序树的建立

二叉 排序 树

二叉排序树（Binary Sort Tree）又称二叉查找树（Binary Search Tree），亦称二叉搜索树。

性质

二叉排序树或者是一棵空树，是具有下列性质的二叉树：

（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；

（2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值；

（3）左、右子树也分别为二叉排序树；

（4）没有键值相等的节点。

可以看出，二叉查找树是一个 递归 的数据结构，且对二叉查找树进行中序遍历，可以得到一个递增的有序序列。

首先，我们来定义一下 BST 的结点结构体：

//树的定义
typedef struct TreeNode
{
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

插入

//二叉排序树的插入【递归】
int BST_insert(struct TreeNode *p,int k)
{
    //二叉树中插入一个关键字为k的结点
    if(p == NULL)
    {
        p = (struct TreeNode*)malloc(sizeof(struct TreeNode));
        p ->val = k;
        p ->left = p ->right = NULL;
        return 1;  //返回1表示成功
    }
    //树中存在相同的结点
    else if(k == p ->val)
        return 0;
    //插入到左子树中
    else if(k < p ->val)
        return BST_insert(p ->left,k);
    //插入到右子树中
    else
        return BST_insert(p ->right ,k);
}

注意，插入的新结点一定是某个叶结点。另外，插入操作既可以递归实现，也可以使用 非递归（迭代 ）实现。通常来说非递归的效率会更高。 

/**
 * 非递归插入：将关键字k插入到二叉查找树
 */
int BST_Insert_NonRecur(BSTree &T, int k)
{
    Node* pre = NULL;  // 记录上一个结点
    Node* t = T;
    while(t != NULL)
    {
        pre = t;
        if(k < t->key)
            t = t->left;
        else if(k > t->key)
            t = t->right;
        else
            return 0;
    }
 
    Node* node = (Node*)malloc(sizeof(Node));
    node->key = k;
    node->left = NULL;
    node->right = NULL;
    node->parent = pre;
 
    if(pre == NULL)
        T = node;
    else
    {
        if(k < pre->key)
            pre->left = node;
        else
            pre->right = node;
    }
    return 1;
}

创建

//二叉树的构建
void BST_create(struct TreeNode *T,int *str,int n)
{
    //用关键字数组建立一个二叉排序树
    T = NULL; //初始时为空树
    int i = 0;
    //依次将每个元素插入
    while(i < n)
    {
        BST_insert(T,str[i]);
        i++;
    }
}

遍历

//【前序遍历】
void preorder(struct TreeNode *T)
{
    if(T != NULL)
    {
        printf("%d\t",T ->val); //打印根结点
        inorder(T ->left);  //递归遍历左子树
        inorder(T ->right); //递归遍历右子树
    }
}
//【后序遍历】
void inorder(struct TreeNode *T)
{
    if(T != NULL)
    {
        inorder(T ->left);  //递归遍历左子树
        inorder(T ->right); //递归遍历右子树
        printf("%d\t",T ->val); //打印根结点
    }
}
//【中序遍历】
void postorder(struct TreeNode *T)
{
    if(T != NULL)
    {
        inorder(T ->left);  //递归遍历左子树
        printf("%d\t",T ->val); //打印根结点
        inorder(T ->right); //递归遍历右子树
    }
}

完整代码

#include <stdio.h>
#include <stdlib.h>

//树的定义
typedef struct TreeNode
{
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};
struct TreeNode *T;
//二叉排序树的插入
int BST_insert(struct TreeNode *p,int k)
{
    //二叉树中插入一个关键字为k的结点
    if(p == NULL)
    {
        p = (struct TreeNode*)malloc(sizeof(struct TreeNode));
        p ->val = k;
        p ->left = p ->right = NULL;
        return 1;  //返回1表示成功
    }
    //树中存在相同的结点
    else if(k == p->val)
        return 0;
    //插入到左子树中
    else if(k < p ->val)
        return BST_insert(p ->left,k);
    //插入到右子树中
    else
        return BST_insert(p ->right ,k);
}
//二叉树的构建
void BST_create(struct TreeNode *T,int *str,int n)
{
    //用关键字数组建立一个二叉排序树
	T = NULL;//初始时为空树
    int i;
    //依次将每个元素插入
    for(i = 0;i < n;i++)
    {
        BST_insert(T,str[i]);
    }
}
//【前序遍历】
void preorder(struct TreeNode *T)
{
    if(T != NULL)
    {
        printf("%d\t",T ->val); //打印根结点
        inorder(T ->left);  //递归遍历左子树
        inorder(T ->right); //递归遍历右子树
    }
}
//【中序遍历】
void inorder(struct TreeNode *T)
{
    if(T != NULL)
    {
        inorder(T ->left);  //递归遍历左子树
        inorder(T ->right); //递归遍历右子树
        printf("%d\t",T ->val); //打印根结点
    }
}
//【后序遍历】
void postorder(struct TreeNode *T)
{
    if(T != NULL)
    {
        inorder(T ->left);  //递归遍历左子树
        printf("%d\t",T ->val); //打印根结点
        inorder(T ->right); //递归遍历右子树
    }
}
int main()
{
    int length,str[] = {3,1,4,NULL,2};
    struct TreeNode *root;
    length = sizeof(str) / sizeof(str[0]);
    BST_create(root,str,length);
    printf("前序遍历：");
    preorder(root);
    printf("\n中序遍历：");
    inorder(root);
    printf("\n后序遍历：");
    postorder(root);
    return 0;
}

疑问

BST_insert(T,str[i]);每次调用时，传进去的 T 为什么都是 NULL ？