V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
bigshot
V2EX  ›  程序员

[数据结构] ——搜索二叉树的插入,查找和删除(递归&非递归)

  •  
  •   bigshot · 2018-02-26 21:47:06 +08:00 · 2431 次点击
    这是一个创建于 2447 天前的主题,其中的信息可能已经有所发展或是发生改变。

    一、搜索二叉树的插入,查找,删除 简单说说搜索二叉树概念: 二叉搜索树又称二叉排序树,它或者是一棵空树,或者是具有以下性质的二叉树 若它的左子树不为空,则左子树上所有节点的值都小于根节点的值 若它的右子树不为空,则右子树上所有节点的值都大于根节点的值 它的左右子树也分别为二叉搜索树 例如:int a [] = {5,3,4,1,7,8,2,6,0,9}; 搜索二叉树 二叉树结构

    typedef struct BSTreeNode 
    {
        struct BSTreeNode *_left;
        struct BSTreeNode *_right;
        DataType _data;
    }BSTreeNode;
    

    二叉树节点创建

    BSTreeNode *BuyTreeNode(DataType x) //创建节点
    {
        BSTreeNode *node = (BSTreeNode*)malloc(sizeof(BSTreeNode));
        assert(node);
    
        node->_data = x;
        node->_left = NULL;
        node->_right = NULL;
    
        return node;
    }
    
    

    二叉搜索树操作: 1、搜索二叉树的插入:在二叉搜索树中插入新元素时,必须先检测该元素是否在树中已经存在。如果已经存在,则不进行插入;否则将新元素加入到搜索停止的地方。 搜索二叉树插入具体过程 非递归代码

    int BSTreeNodeInsert(BSTreeNode **pptree,DataType x) //搜索树的插入
    {
        BSTreeNode *parent = NULL;
        BSTreeNode *cur = *pptree;
        if (*pptree == NULL)
        {
            *pptree = BuyTreeNode(x);
            return 0;
        }
        while (cur)
        {
          parent = cur;
          if (cur->_data > x)
              cur = cur->_left;
          else if (cur->_data < x)
              cur = cur->_right;
          else
              return -1;
        }
    
        if (parent->_data > x)
            parent->_left = BuyTreeNode(x);
        else 
            parent->_right = BuyTreeNode(x);
    
        return 0;
    }
    
    

    递归代码 :

    int BSTreeNodeInsertR(BSTreeNode **tree,DataType x) //搜索树的插入
    {
        if(*tree == NULL)
        {
            *tree = BuyTreeNode(x);
            return 0;
        }
    
        if ((*tree)->_data > x)
            return BSTreeNodeInsertR(&(*tree)->_left,x);
        else if ((*tree)->_data < x)
            return BSTreeNodeInsertR(&(*tree)->_right,x);
        else
            return -1;
    }
    
    

    2、搜索二叉树的查找这里写图片描述

    非递归代码

    BSTreeNode *BSTreeNodeFind(BSTreeNode *tree,DataType x) //查找
    {
        while (tree)
        {
            if (tree->_data == x)
                return tree;
            else if (tree->_data < x)
                tree = tree->_right;
            else 
                tree = tree->_left;
        }
    
        return NULL;
    }
    

    递归代码

    BSTreeNode *BSTreeNodeFindR(BSTreeNode *tree,DataType x) //查找
    {
        if (!tree)
            return NULL;
    
        if (tree->_data > x)
            BSTreeNodeFindR(tree->_left,x);
        else if (tree->_data < x)
            BSTreeNodeFindR(tree->_right,x);
        else
            return tree;
    }
    

    3、搜索二叉树的删除: 首先查找元素是否在二叉搜索树中,如果不存在,则返回, 否则要删除的结点可能分下面四种情况: a. 要删除的结点无孩子结点 b. 要删除的结点只有左孩子结点 c. 要删除的结点只有右孩子结点 d. 要删除的结点有左、右孩子结点 情况 1 可以归类到 2 或者 3 对于上述情况,相应的删除方法如下: a. 直接删除该结点 b. 删除该结点且使被删除节点的双亲结点指向被删除节点的左孩子结点 c. 删除该结点且使被删除节点的双亲结点指向被删除结点的右孩子结点 d. 在它的右子树中寻找中序下的第一个结点(关键码最小),用它的值填补到被删除节点中,在来处理该结点的删除问题 代码实现:

    int BSTreeNodeDel(BSTreeNode **tree,DataType x) //删除
    {
    
        BSTreeNode *cur = *tree;
        BSTreeNode *parent = *tree;
        BSTreeNode *del = NULL;
        
        while (cur)
        {
            if (cur->_data > x)
            {
                parent = cur;
                cur = cur->_left;
            }
            else if (cur->_data < x)
            {
                parent = cur;
                cur = cur->_right;
            }
            else
            {
                del = cur;
    
                if (cur->_left == NULL) //1、左孩子为空
                {
                    if (parent->_left == cur)
                        parent->_left = cur->_right;
                    else if (parent->_right == cur)
                        parent->_right = cur->_right;
                    else if (parent == cur) //没有父亲节点时
                       *tree = parent->_right;
                }
                else if (cur->_right == NULL) //2、右孩子为空
                {
                    if (parent->_left == cur)
                        parent->_left = cur->_left;
                    else if (parent->_right == cur)
                        parent->_right = cur->_left;
                    else if (parent == cur) //没有父亲节点时
                        *tree = parent->_left;
                }
                else//3、左右孩子都不为空
                {
                    BSTreeNode *sub = cur->_right;
                    while (sub->_left)
                    {
                        parent = sub;
                        sub = sub->_left;
                    }
                       
                    del = sub;
                    cur->_data = sub->_data;
    
                    if (parent->_left == sub)
                        parent->_left = sub->_right;
                    else 
                        parent->_right = sub->_right;
                }
    
                free(del);
                del = NULL;
                return 0;
    
            }
        }
    
        return -1;
    }
    

    完整代码请私信或者点此链接下载 [数据结构] ——搜索二叉树的插入,查找和删除(递归&非递归)

    目前尚无回复
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   2886 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 22ms · UTC 02:35 · PVG 10:35 · LAX 18:35 · JFK 21:35
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.