数据结构-二进制排序树的递归实现

 二叉排序树（简称BST）又称二叉查找（搜索）树，其定义为：二叉排序树或者是空树或者是满足如下性质的二叉树：  
  1.若它的左子树不为空，则左子树上所有的结点的值都小于根结点的值
     2.若它的右子树不为空，则右子树上的所有节点的值都大于跟结点 的值
      3.它的左右子树也分别为二叉搜索树
  二叉排序树还有一个重要的性质：中序遍历二叉排序树所得到的中序序列是一个递增的有序数列

在讨论二叉树之前二叉排序树算法，我们必须首先定义节点:

每个节点包含自己的键控代码，还包含其左子节点和右子节点

typedef char SearchTreeType;
typedef struct SearchTreeNode
{
    SearchTreeType key;//关键码
    SearchTreeNode *lchild;
    SearchTreeNode *rchild;
}SearchTreeNode;

  向二叉树中插入元素，插入元素后要保证得到的二叉树还得保持二叉排序树的性质，插入时，先应该创建一个新结点，这个新节点的码就是要插入的码，用这个结点的码与二叉树进行比较，若key大于二叉树根节点的key，则需要递归调用插入函数，但是插入函数中的参数root变为了root的右子树，直到找到根节点为空时，将新节点插入在这个位置。若key小于二叉树根节点的key，与上面的过程类似，就是递归参数变为了root的左子树。代码如下：

void SearchTreeInsert1(SearchTreeNode **root, SearchTreeType key)
{
    if (root == NULL)
        return;
    SearchTreeNode* newnode = CreateNewNode(key);
    if (*root == NULL)    //空树
    {
        *root = newnode;
        return;
    }
    if ((*root)->key > key)
    {
        SearchTreeInsert1(&(*root)->lchild, key);
        return;
    }
    else if ((*root)->key < key)
    {
        SearchTreeInsert1(&(*root)->rchild, key);
        return;
    }
}

搜索二叉树，因为它是二叉排序树，所以搜索是逐渐缩小范围的过程. 当前的根节点用于继续与要搜索的键进行比较. 如果小于键，则以递归方式调用搜索功能. 继续在右侧子树中搜索. 如果大于key，则继续在左侧子树中搜索. 如果两个值相等，则表示找到了元素. 如果根节点为空二叉排序树算法，则表示不存在此类元素.

SearchTreeNode* SearchTreeFind1(SearchTreeNode *root, SearchTreeType to_find)
{
    if (root == NULL)     //空树
        return 0;
    if (root->key < to_find)
    {
        SearchTreeFind1(root->rchild, to_find);
        return 0;
    }
    else if (root->key>to_find)
    {
        SearchTreeFind1(root->lchild, to_find);
        return 0;
    }
    else
        return root;
}

删除二进制排序树. 删除二叉树中的元素时，您只能删除自己，不能删除其子树，因此不仅需要删除节点，还需要删除子树. 调整必须确保删除节点后的二叉树仍然是二叉排序树. 因此，需要根据要删除节点的子树的情况，在不同情况下进行讨论.

void SearchTreeRemove1(SearchTreeNode **root, SearchTreeType key)
{
    if (NULL == root)
        return;
    if (NULL == *root)
        return;
    if ((*root)->key < key)
    {
        SearchTreeRemove1(&((*root)->rchild), key);
        return;
    }
    if ((*root)->key > key)
    {
        SearchTreeRemove1(&((*root)->lchild), key);
            return;
    }
    if ((*root)->key == key)
    {
        //要删除的结点没有子结点,让其根节点指向空
        if ((*root)->lchild == NULL && (*root)->rchild == NULL)
        {
            (*root) = NULL;
            DestroyNode(*root);
            return;
        }
        //要删除的结点只有右结点，让其根节点指向其右结点
        if ((*root)->lchild == NULL && (*root)->rchild != NULL)
        {
            SearchTreeNode* tmp = *root;
            (*root) = (*root)->rchild;
            DestroyNode(tmp);
            return;
        }
        //要删除的结点只有左结点，让其根节点指向其左节点。
        if ((*root)->lchild != NULL && (*root)->rchild == NULL)
        {
            SearchTreeNode* tmp = *root;
            (*root) = (*root)->lchild;
            DestroyNode(tmp);
            return;
        }
        //要删除的结点有两个结点，
        if ((*root)->lchild != NULL && (*root)->rchild != NULL)
        {
            SearchTreeNode* tmp = (*root)->rchild;
            SearchTreeNode* parent = tmp;
            while (tmp->lchild!= NULL)
            {
                parent = tmp;
                tmp = tmp->lchild;
            }
            (*root)->key = tmp->key;
            parent->lchild = NULL;
            DestroyNode(tmp);
            return;
        }
    }
}

还有一些用于创建节点，删除节点的辅助功能，以及用于遍历二叉树以测试和显示结果的节点功能.

以下是完整的代码和测试功能:

#define _CRT_SECURE_NO_WARNINGS 1
#include "SearchTree.h"
#include<stdio.h>
#include<stdlib.h>
#include<stddef.h>
#include<assert.h>
//初始化二叉树
void SearchTreeInit(SearchTreeNode** root)
{
    if (root == NULL)    //非法输入
        return;
    *root = NULL;
}
SearchTreeNode* CreateNewNode(SearchTreeType key)
{
    SearchTreeNode* newnode = (SearchTreeNode*)malloc(sizeof(SearchTreeNode));
    newnode->key = key;
    newnode->lchild = NULL;
    newnode->rchild = NULL;
    return newnode;
}
void DestroyNode(SearchTreeNode* node)    //销毁结点
{
    free(node);
}
//先序遍历二叉树并打印
void PreOrderPrint(SearchTreeNode* root)
{
    if (root == NULL)   //为空树
        return;
    SearchTreeNode* cur = root;
    printf("%c ", cur->key);
    PreOrderPrint(cur->lchild);
    PreOrderPrint(cur->rchild);
    return;
}
//中序遍历二叉树，并打印
void InOrderPrint(SearchTreeNode* root)
{
    if (root == NULL)   //空树
        return;
    SearchTreeNode* cur = root;
    InOrderPrint(cur->lchild);
    printf("%c ", cur->key);
    InOrderPrint(cur->rchild);
    return;
}
void SearchTreeInsert1(SearchTreeNode **root, SearchTreeType key)
{
    if (root == NULL)
        return;
    SearchTreeNode* newnode = CreateNewNode(key);
    if (*root == NULL)    //空树
    {
        *root = newnode;
        return;
    }
    if ((*root)->key > key)
    {
        SearchTreeInsert1(&(*root)->lchild, key);
        return;
    }
    else if ((*root)->key < key)
    {
        SearchTreeInsert1(&(*root)->rchild, key);
        return;
    }
}
SearchTreeNode* SearchTreeFind1(SearchTreeNode *root, SearchTreeType to_find)
{
    if (root == NULL)     //空树
        return 0;
    if (root->key < to_find)
    {
        SearchTreeFind1(root->rchild, to_find);
        return 0;
    }
    else if (root->key>to_find)
    {
        SearchTreeFind1(root->lchild, to_find);
        return 0;
    }
    else
        return root;
}
void SearchTreeRemove1(SearchTreeNode **root, SearchTreeType key)
{
    if (NULL == root)
        return;
    if (NULL == *root)
        return;
    if ((*root)->key < key)
    {
        SearchTreeRemove1(&((*root)->rchild), key);
        return;
    }
    if ((*root)->key > key)
    {
        SearchTreeRemove1(&((*root)->lchild), key);
            return;
    }
    if ((*root)->key == key)
    {
        //要删除的结点没有子结点,让其根节点指向空
        if ((*root)->lchild == NULL && (*root)->rchild == NULL)
        {
            (*root) = NULL;
            DestroyNode(*root);
            return;
        }
        //要删除的结点只有右结点，让其根节点指向其右结点
        if ((*root)->lchild == NULL && (*root)->rchild != NULL)
        {
            SearchTreeNode* tmp = *root;
            (*root) = (*root)->rchild;
            DestroyNode(tmp);
            return;
        }
        //要删除的结点只有左结点，让其根节点指向其左节点。
        if ((*root)->lchild != NULL && (*root)->rchild == NULL)
        {
            SearchTreeNode* tmp = *root;
            (*root) = (*root)->lchild;
            DestroyNode(tmp);
            return;
        }
        //要删除的结点有两个结点，
        if ((*root)->lchild != NULL && (*root)->rchild != NULL)
        {
            SearchTreeNode* tmp = (*root)->rchild;
            SearchTreeNode* parent = tmp;
            while (tmp->lchild!= NULL)
            {
                parent = tmp;
                tmp = tmp->lchild;
            }
            (*root)->key = tmp->key;
            parent->lchild = NULL;
            DestroyNode(tmp);
            return;
        }
    }
}
////////////////////////////测试代码/////////////////////////////////////////////////
#define __TestHead__ printf("--------------------%s-------------------------\n",__FUNCTION__);
void testSearchTreeInsert(SearchTreeNode* root)
{
    __TestHead__;
    SearchTreeInit(&root);
    SearchTreeInsert(&root, 'c');
    SearchTreeInsert(&root, 'h');
    SearchTreeInsert(&root, 'i');
    SearchTreeInsert(&root, 'a');
    SearchTreeInsert(&root, 'b');
    SearchTreeInsert(&root, 'g');
    PreOrderPrint(root);
    printf("\n");
    InOrderPrint(root);
    printf("\n");
}
void testSearchTreeFind(SearchTreeNode* root)
{
    __TestHead__;
    SearchTreeInit(&root);
    SearchTreeInsert(&root, 'c');
    SearchTrearchTreeRemove(SearchTreeNode* root)
{
    __TestHead__;
    SearchTreeInit(&root);
    SearchTreeInsert(&root, 'd');
    SearchTreeInsert(&root, 'c');
    SearchTreeInsert(&root, 'f');
    SeareOrderPrint(root);
    printf("\n");
}
void test()
{
    SearchTreeNode root;
    testSearchTreeInsert(&root);
    testSearchTreeFind(&root);
        testSearchTreeRemove(&root);
}
int main()
{
    test();
    system("pause");
    return 0;
}

这是测试结果的屏幕截图:

本文来自电脑杂谈，转载请注明本文网址：
https://www.pc-fly.com/a/jisuanjixue/article-248649-1.html