二叉搜索树的插入与删除(详细解析)

题目:创建一个类,类中的数据成员时一棵二叉搜索树,对外提供的接口有添加结点和删除结点这两种方法。用户不关注二叉树的情况。要求我们给出这个类的结构以及实现类中的方法。

思路
添加结点:
添加结点其实很容易,我们只需要找到结点所行对应的位置就可以了,而且没有要求是平衡的二叉搜索树,因此每次添加结点都是在叶子结点上操作,不需要修改二叉搜索树整体的结构。要找出添加节点在二叉搜索树中的位置,可以用一个循环解决。判断插入结点与当前头结点的大小,如果大于头结点则继续搜索右子树,如果小于头结点则继续搜索左子树。直到搜索到叶子结点,此时进行插入结点操作。如果插入的结点等于二叉搜索树中当前某一结点的值,那么退出插入操作,并告知用户该结点已经存在。

删除结点:
删除结点比较麻烦,因为需要调整树的结构,这是因为删除结点并不一定发生在叶子结点。如果删除的是叶子结点,那么操作非常简单,只是做相应的删除就可以了,但如果删除的是非叶子结点,那么就需要调整二叉搜索树的结构。调整的策略有两个。假设当前需要删除的结点为A,

1.找出A结点左子树中的最大值结点B,将B调整到原先A的位置。
2.找出A结点右子树中的最小值结点C,将C调整到原先A的位置。

这其中涉及到许多复杂的指针操作,在下面的代码示例中并没有完成结点删除操作,等有空再补充研究一下。

代码示例


代码如下:

#include<iostream>
#include<stdlib.h>
#include<cassert>
using namespace std;

//二叉树结点
struct BinaryTreeNode
{
    int m_nValue;
    BinaryTreeNode* m_pLeft;
    BinaryTreeNode* m_pRight;
};

class BST
{
public:
    BST(int value);//构造函数
    ~BST();//析构函数
    void AddNode(int value);//添加结点
    void DeleteNode(int value);//删除结点
    BinaryTreeNode* CreateBinaryTreeNode(int value);//创建一个二叉树结点
    void InOrderPrintTree();//中序遍历
    void InOrderPrintTree(BinaryTreeNode* pRoot);//中序遍历
    BinaryTreeNode* GetMaxNode(BinaryTreeNode* pNode);//求二叉搜索树最大值
    BinaryTreeNode* GetMinNode(BinaryTreeNode* pNode);//求二叉搜索树最小值

private:
    BinaryTreeNode* pRoot;
};

//构造函数
BST::BST(int value)
{
    pRoot=CreateBinaryTreeNode(value);
}

//析构函数
BST::~BST()
{
    delete pRoot;
    pRoot=NULL;
}

//创建二叉树结点
BinaryTreeNode* BST::CreateBinaryTreeNode(int value)
{
    BinaryTreeNode* pNode=new BinaryTreeNode();
    pNode->m_nValue=value;
    pNode->m_pLeft=NULL;
    pNode->m_pRight=NULL;
    return pNode;
}

//求二叉搜索树最大值
BinaryTreeNode* BST::GetMaxNode(BinaryTreeNode* pNode)
{
    assert(pNode!=NULL); // 使用断言,保证传入的头结点不为空
    //最大值在右子树上,因此一直遍历右子树,让pNode等于其右子树;如果只有一个结点则直接返回pNode
    while(pNode->m_pRight!=NULL)
    {
        pNode=pNode->m_pRight;
    }
    return pNode;

}
//求二叉搜索树最小值
BinaryTreeNode* BST::GetMinNode(BinaryTreeNode* pNode)
{
    assert(pNode!=NULL); // 使用断言
    //最小值在左子树上,整体思路跟求最大值相同。
    while(pNode->m_pLeft!=NULL)
    {
        pNode=pNode->m_pLeft;
    }
    return pNode;
}
//二叉搜索树添加结点
void BST::AddNode(int value)
{
    BinaryTreeNode* pInsertNode=CreateBinaryTreeNode(value);//初始化需要创建的结点。
    BinaryTreeNode* pNode=pRoot;
    while(true)
    {
        //如果插入的值在二叉搜索树中已经存在,则不进行插入操作,跳出循环。
        if(pNode->m_nValue==value)
        {
            cout<<"结点值已经存在"<<endl;
            break;
        }

//寻找结点插入的位置,如果待插入结点小于当前头结点,则继续搜索左子树
        else if(pNode->m_nValue > value)
        {
            if(pNode->m_pLeft==NULL)//如果当前头结点是叶子结点了,那么直接将待插入结点插入到左子树中,然后跳出循环
            {
                pNode->m_pLeft=pInsertNode;
                break;
            }
            else//否则继续遍历其左子树
                pNode=pNode->m_pLeft;
        }
        //思路跟上述相同
        else if(pNode->m_nValue < value)
        {
            if(pNode->m_pRight==NULL)
            {
                pNode->m_pRight=pInsertNode;
                break;
            }
            pNode=pNode->m_pRight;
        }
    }

}

//未完成
void BST::DeleteNode(int value)
{
    BinaryTreeNode* pNode=pRoot;
    while(true)
    {
        if(pRoot->m_nValue==value)//如果是头结点
        {
            if(pRoot->m_pLeft!=NULL)
            {
                BinaryTreeNode* pLeftMaxNode=GetMaxNode(pRoot->m_pLeft);
            }
            else if(pRoot->m_pRight!=NULL)
            {

}
            else
            {
                delete pRoot;
                pRoot=NULL;
            }
        }

if(pNode->m_nValue==value)
        {
            if(pNode->m_pLeft!=NULL)
            {

}
            else if(pNode->m_pRight!=NULL)
            {

}
            else
            {

}
        }
    }
}
void BST::InOrderPrintTree(BinaryTreeNode* pRoot)//中序遍历
{
    if(pRoot!=NULL)
    {
        //如果左子树不为空,则遍历左子树
        if(pRoot->m_pLeft!=NULL)
            InOrderPrintTree(pRoot->m_pLeft);
        //遍历左子树的叶子结点
        cout<<"value of this node is "<<pRoot->m_nValue<<endl;
        //如果右子树不为空,遍历右子树
        if(pRoot->m_pRight!=NULL)
            InOrderPrintTree(pRoot->m_pRight);
    }
    else
    {
        cout<<"this node is null."<<endl;
    }
}
//因为需要使用递归来进行中序遍历,所以还需要调用一个带参数的中序遍历函数
void BST::InOrderPrintTree()//中序遍历
{
    InOrderPrintTree(pRoot);
}
void main()
{
    BST* b=new BST(10);//初始化类的时候定义了二叉搜索树的头结点,这样省去了头结点为空的判断
    b->AddNode(6);
    b->AddNode(14);
    b->InOrderPrintTree();
    system("pause");
}

(0)

相关推荐

  • C#二叉搜索树插入算法实例分析

    本文实例讲述了C#二叉搜索树插入算法.分享给大家供大家参考.具体实现方法如下: public class BinaryTreeNode { public BinaryTreeNode Left { get; set; } public BinaryTreeNode Right { get; set; } public int Data { get; set; } public BinaryTreeNode(int data) { this.Data = data; } } public void

  • Java 实现二叉搜索树的查找、插入、删除、遍历

    由于最近想要阅读下JDK1.8 中HashMap的具体实现,但是由于HashMap的实现中用到了红黑树,所以我觉得有必要先复习下红黑树的相关知识,所以写下这篇随笔备忘,有不对的地方请指出- 学习红黑树,我觉得有必要从二叉搜索树开始学起,本篇随笔就主要介绍Java实现二叉搜索树的查找.插入.删除.遍历等内容. 二叉搜索树需满足以下四个条件: 若任意节点的左子树不空,则左子树上所有结点的值均小于它的根结点的值: 若任意节点的右子树不空,则右子树上所有结点的值均大于它的根结点的值: 任意节点的左.右子

  • Python二叉搜索树与双向链表转换实现方法

    本文实例讲述了Python二叉搜索树与双向链表实现方法.分享给大家供大家参考,具体如下: # encoding=utf8 ''' 题目:输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表. 要求不能创建任何新的结点,只能调整树中结点指针的指向. ''' class BinaryTreeNode(): def __init__(self, value, left = None, right = None): self.value = value self.left = left self.

  • C#创建二叉搜索树的方法

    本文实例讲述了C#创建二叉搜索树的方法.分享给大家供大家参考.具体如下: public static BinaryTreeNode BuildBinarySearchTree(int[] sortedArray) { if (sortedArray.Length == 0) return null; int _mid = sortedArray.Length / 2; BinaryTreeNode _root = new BinaryTreeNode(sortedArray[_mid]); in

  • Python实现二叉搜索树

    二叉搜索树 我们已经知道了在一个集合中获取键值对的两种不同的方法.回忆一下这些集合是如何实现ADT(抽象数据类型)MAP的.我们讨论两种ADT MAP的实现方式,基于列表的二分查找和哈希表.在这一节中,我们将要学习二叉搜索树,这是另一种键指向值的Map集合,在这种情况下我们不用考虑元素在树中的实际位置,但要知道使用二叉树来搜索更有效率. 搜索树操作 在我们研究这种实现方式之前,让我们回顾一下ADT MAP提供的接口.我们会注意到,这种接口和Python的字典非常相似. Map() 创建了一个新的

  • 二叉搜索树源码分享

    复制代码 代码如下: #include <iostream>using namespace std; //枚举类,前中后三种遍历方式enum ORDER_MODE{ ORDER_MODE_PREV = 0, ORDER_MODE_MID, ORDER_MODE_POST}; //树节点的结构体template <class T>struct BinaryNode{ T    element; BinaryNode  *left; BinaryNode  *right; Binary

  • javascript数据结构之二叉搜索树实现方法

    本文实例讲述了javascript二叉搜索树实现方法.分享给大家供大家参考,具体如下: 二叉搜索树:顾名思义,树上每个节点最多只有二根分叉:而且左分叉节点的值 < 右分叉节点的值 . 特点:插入节点.找最大/最小节点.节点值排序 非常方便 二叉搜索树-javascript实现 <script type="text/javascript"> // <![CDATA[ //打印输出 function println(msg) { document.write(msg

  • 二叉搜索树实例练习

    一棵二叉查找树是按二叉树结构来组织的.这样的树可以用链表结构表示,其中每一个结点都是一个对象.结点中除了数据外,还包括域left,right和p,它们分别指向结点的左儿子.右儿子,如果结点不存在,则为NULL. 它或者是一棵空树:或者是具有下列性质的二叉树: 1)若左子树不空,则左子树上所有结点的值均小于它的根结点的值: (2)若右子树不空,则右子树上所有结点的值均大于它的根结点的值: (3)左.右子树也分别为二叉查找树: 显然满足了上面的性质,那么二叉查找树按中序遍历就是按从小到大的顺序遍历,

  • 二叉搜索树的插入与删除(详细解析)

    题目:创建一个类,类中的数据成员时一棵二叉搜索树,对外提供的接口有添加结点和删除结点这两种方法.用户不关注二叉树的情况.要求我们给出这个类的结构以及实现类中的方法. 思路添加结点:添加结点其实很容易,我们只需要找到结点所行对应的位置就可以了,而且没有要求是平衡的二叉搜索树,因此每次添加结点都是在叶子结点上操作,不需要修改二叉搜索树整体的结构.要找出添加节点在二叉搜索树中的位置,可以用一个循环解决.判断插入结点与当前头结点的大小,如果大于头结点则继续搜索右子树,如果小于头结点则继续搜索左子树.直到

  • Java实现二叉搜索树的插入、删除功能

    二叉树的结构 public class TreeNode { int val; TreeNode left; TreeNode right; TreeNode() { } TreeNode(int val) { this.val = val; } } 中序遍历 中序遍历:从根节点开始遍历,遍历顺序是:左子树->当前节点->右子树,在中序遍历中,对每个节点来说: 只有当它的左子树都被遍历过了(或者没有左子树),它才会被遍历到.在遍历右子树之前,一定会先遍历当前节点. 中序遍历得到的第一个节点是没

  • 利用java实现二叉搜索树

    二叉搜索树的定义 它是一颗二叉树 任一节点的左子树上的所有节点的值一定小于该节点的值 任一节点的右子树上的所有节点的值一定大于该节点的值 特点: 二叉搜索树的中序遍历结果是有序的(升序)! 实现一颗二叉搜索树 实现二叉搜索树,将实现插入,删除,查找三个方面 二叉搜索树的节点是不可以进行修改的,如果修改,则可能会导致搜索树的错误 二叉搜索树的定义类 二叉搜索树的节点类 -- class Node 二叉搜索树的属性:要找到一颗二叉搜索树只需要知道这颗树的根节点. public class BST {

  • java实现 二叉搜索树功能

    一.概念 二叉搜索树也成二叉排序树,它有这么一个特点,某个节点,若其有两个子节点,则一定满足,左子节点值一定小于该节点值,右子节点值一定大于该节点值,对于非基本类型的比较,可以实现Comparator接口,在本文中为了方便,采用了int类型数据进行操作. 要想实现一颗二叉树,肯定得从它的增加说起,只有把树构建出来了,才能使用其他操作. 二.二叉搜索树构建 谈起二叉树的增加,肯定先得构建一个表示节点的类,该节点的类,有这么几个属性,节点的值,节点的父节点.左节点.右节点这四个属性,代码如下 sta

  • C++深入细致探究二叉搜索树

    目录 1.二叉搜索树的概念 2.二叉搜索树的操作 二叉搜索树的查找 二叉搜索树的插入 二叉搜索树的删除 3.二叉搜索树的实现 4.二叉搜索树的性能分析 1.二叉搜索树的概念  二叉搜索树又称二叉排序树,它可以是一颗空树,亦可以是一颗具有如下性质的二叉树:   ①若根节点的左子树不为空,则左子树上的所有节点的值域都小于根节点的值   ②若根节点的右子树不为空,则右子树上的所有节点的值域都大于根节点的值   ③根节点的左右子树分别也是一颗二叉搜索树 例如下面的这棵二叉树就是一棵二叉搜索树: 注意:判

  • C++数据结构之二叉搜索树的实现详解

    目录 前言 介绍 实现 节点的实现 二叉搜索树的查找 二叉搜索树的插入 二叉搜索树的删除 总结 前言 今天我们来学一个新的数据结构:二叉搜索树. 介绍 二叉搜索树也称作二叉排序树,它具有以下性质: 非空左子树的所有键值小于其根节点的键值 非空右子树的所有键值大于其根节点的键值 左,右子树都是二叉搜索树 那么我先画一个二叉搜索树给大家看看,是不是真的满足上面的性质. 我们就以根节点6为例子来看,我们会发现比6小的都在6的左边,而比6大的都在6的右边.对于6的左右子树来说,所有的节点都遵循这个规则.

  • C++简单实现与分析二叉搜索树流程

    目录 二叉搜索树 二叉搜索树的重要操作 二叉搜索树实现(key模型) 二叉搜索树的应用 二叉搜索树的实现(key/value模型) 二叉搜索树 二叉搜索树又被称为二叉排序树.它可以是一个空树,如果不是空树则满足下列性质: 1.如果它的左子树不为空,那么左子树上的所有节点都小于根. 2.如果它的右子树不为空,那么右子树上的所有节点都大于根 3.它的左子树.右子树也是二叉搜索树. 二叉搜索树的重要操作 二叉搜索树的插入 1.如果树为空,则直接插入 2.如果树不为空,则找到对应的位置插入. 查找办法:

  • Java创建二叉搜索树,实现搜索,插入,删除的操作实例

    Java实现的二叉搜索树,并实现对该树的搜索,插入,删除操作(合并删除,复制删除) 首先我们要有一个编码的思路,大致如下: 1.查找:根据二叉搜索树的数据特点,我们可以根据节点的值得比较来实现查找,查找值大于当前节点时向右走,反之向左走! 2.插入:我们应该知道,插入的全部都是叶子节点,所以我们就需要找到要进行插入的叶子节点的位置,插入的思路与查找的思路一致. 3.删除: 1)合并删除:一般来说会遇到以下几种情况,被删节点有左子树没右子树,此时要让当前节点的父节点指向当前节点的左子树:当被删节点

  • Java数据结构超详细分析二叉搜索树

    目录 1.搜索树的概念 2.二叉搜索树的简单实现 2.1查找 2.2插入 2.3删除 2.4修改 3.二叉搜索树的性能 1.搜索树的概念 二叉搜索树是一种特殊的二叉树,又称二叉查找树,二叉排序树,它有几个特点: 如果左子树存在,则左子树每个结点的值均小于根结点的值. 如果右子树存在,则右子树每个结点的值均大于根结点的值. 中序遍历二叉搜索树,得到的序列是依次递增的. 二叉搜索树的左右子树均为二叉搜索树. 二叉搜索树的结点的值不能发生重复. 2.二叉搜索树的简单实现 我们来简单实现以下搜索树,就不

随机推荐