首页 > 代码库 > 二叉搜索树建立、插入、删除、前继节点、后继节点之c++实现
二叉搜索树建立、插入、删除、前继节点、后继节点之c++实现
一、前言
一直以来，都对树有关的东西望而却步。以前每次说要看一看，都因为惰性，时间就那么荒废掉了。今天下个决心，决定好好的数据结构中的东西看一下。不知道看这篇文章的你，是不是和我有同样的感受，空有一颗努力的心，却迟迟没有付出行动。如果是的话，如果也想好好的把树的知识巩固一下的话，就让我们一起好好儿地把知识点过一遍吧。本文争取让看完的每一个没有基础的同学，都能有所收获。在正文开始前，先给自己加个油。加油↖(^ω^)↗
二、二叉搜索树的定义
二叉搜索树是指，对于某一个节点而言，它左边的节点都小于或等于它。而它右边的节点都大于或等于它。借用一下网上的图片（懒得自己画图了，请见谅）。如下图所示，是一个二叉搜索树，大家可以自己找几个节点试一试验证一下这个定义。
三、二叉搜索树有关的常见的操作
1、建立；
2、插入一个节点；
3、删除一个节点；
4、找出最小和最大的节点；
5、找出某个节点的前继节点和后继节点。
前面4条所做的工作比较好理解，但要理解第一条所做的工作，则需要明白什么是前继节点和后继节点。下面我们就一起回顾一下什么是前继节点，什么是后继节点把。\(^o^)/~，加油！
前继节点：某个节点的前继节点，是指比该节点小的所有节点中的最大的一个节点。如在上图中，比节点“8”小的节点有很多个，但是最大的一个节点为“7”，那么节点“7”则为节点“8”的前继节点；
后继节点：某个节点的后继节点，是指比该节点大的所有节点中的最小的一个节点。如在上如中，比节点“1”大的节点有很多歌，但是最小的一个节点为“3”，那么节点“3”则为节点“1”的后继节点。
【插入】下面我们来分别理解一下，每种操作实现的具体步骤。建立一个二叉搜索树，其实是插入n个节点。而插入一个节点，我们是这么做的：
- 如果一个节点小于根节点，且根节点的左孩子为空的话，那么直接将该节点作为根节点的左孩子；
- 如果一个节点小于根节点，但是根节点的左孩子不为的话，那么我们将根节点的左孩子作为新的根节点，递归进行1、2两步。
- 同理，我们可以知道该怎么处理一个节点大于根节点的情况。
- 在这里有一个特殊的情况需要说明一下，那就是如果碰到重复的节点，本文采用软插入和软删除的办法。即我们设置一个变量用来表示该节点出现的次数，如果要插入的节点已经在二叉搜索树中存在的话，那么我们只需要把这个节点出现的次数变量加1。
如下图所示
【最大值&最小值】
找一个二叉树的最大值和最小值比较简单，因为二叉树的最小值肯定在二叉树的最左边，最大值肯定在二叉树的最右边。我们只需要使用一个循环，一直分别循环到节点的左节点或右节点为空，则可以得到二叉树的最大值和最小值了。
如上图中，最小节点为2，最大节点为18.
【前继节点】找一个节点的前继节点，我们分为两种情况
- 若该节点有左孩子，那么前继节点则为以该节点的左孩子为根节点所寻找到的最大值；
- 若该节点没有左孩子，那么前继节点需要往上寻找节点为右孩子。
如上图中，12的前继节点为10。
【后继节点】找一个节点的后继节点，我们分为两种情况
- 若该节点有右孩子，那么前继节点则为以该节点的左孩子为根节点所寻找到的最小值；
- 若该节点没有右孩子，那么前继节点需要往上寻找节点为左孩子。
如上图中，3的后继节点为4。
【删除】删除一个节点，我们也分为三种情况
- 如果待删除的节点即没有左孩子，也没有右孩子的话，则直接删除该节点，但是请注意需要将相应的父节点的修改。如：如果待删除的节点是父节点的左孩子的话，那么需要将父节点的左孩子节点置为空；
- 如果待删除的节点只有一个孩子，那么直接用该孩子代替这个节点。这里，同样需要注意修改父节点。即，如果待删除是父节点的左孩子，且它只有一个右孩子，那么删除这个节点需要将父节点的左节点指向待删除节点的右孩子；
- 如果待删除的节点有两个孩子的话，我们可以选择使用该节点的前继节点或者后继节点来代替该节点。大家可以在笔下试一试，就会发现两种替代方式，都能保证更新之后的二叉树依然满足二叉搜索树的定义。
如下图所示
完整代码
#include "stdafx.h"
#include <string>
#include <stdlib.h>
#include <iostream>
using namespace std;
typedef struct Node
{
int key; //键值
struct Node *left; //左节点
struct Node *right; //右节点
struct Node *father; //父节点
int times; //节点出现的次数
} Node, *pNode;
void creatBinarySearchTree(pNode &pBSTTree, int *ptr, int len);
void insertNode(pNode &pBSTTree, int value);
void mallocInitNode(pNode &pInsertNode, int value);
pNode findMinNode(pNode &pTree);
pNode findMaxNode(pNode &pTree);
pNode findPredecessor(pNode &pSearchNode);
pNode findSuccessor(pNode &pSearchNode);
void deleteNode(pNode& pdeleteNode);
void changeFatherChildNode(pNode& pdeleteNode, pNode& pNewChildNode);
int main()
{
int a[] = {15,15, 6, 18, 3, 7, 17, 20, 2, 4, 13, 9};
int len = sizeof(a) / sizeof(int);
pNode pBSTTree = NULL;
pNode pPreNode = NULL;
pNode pSuccessor = NULL;
/* 创建二叉查找树 */
creatBinarySearchTree(pBSTTree, a, len);
/* 寻找二叉查找树中的最大值 */
cout << "最小值的节点为:" << findMinNode(pBSTTree)->key << endl;
cout << "最大值的节点为:" << findMaxNode(pBSTTree)->key << endl;
/* 寻找某个节点的前驱节点 */
pPreNode = findPredecessor(pBSTTree->left->right);
if (NULL != pPreNode)
{
cout << "该节点的前驱节点为:" << pPreNode->key << endl;
}
else
{
cout << "该节点无前驱节点" << endl;
}
/* 寻找某个节点的后继节点 */
pSuccessor = findSuccessor(pBSTTree->left->left->left);
if (NULL != pPreNode)
{
cout << "该节点的后继节点为:" << pSuccessor->key << endl;
}
else
{
cout << "该节点无后继节点" << endl;
}
/* 删除某个节点 */
deleteNode(pBSTTree->right->right);
deleteNode(pBSTTree->left->left);
cout << "最小值的节点为:" << findMinNode(pBSTTree)->key << endl;
pSuccessor = findSuccessor(pBSTTree->left->left);
if (NULL != pPreNode)
{
cout << "该节点的后继节点为:" << pSuccessor->key << endl;
}
else
{
cout << "该节点无后继节点" << endl;
}
free(pBSTTree);
pBSTTree = NULL;
return 0;
}
/* 创建一个二叉查找树 */
void creatBinarySearchTree(pNode &pBSTTree, int *ptr, int len)
{
for (int i = 0; i < len; i++)
{
insertNode(pBSTTree, *(ptr + i));
}
}
/* 插入一个节点，复杂度为O(nlogn) */
void insertNode(pNode &pBSTTree, int value)
{
pNode pInsertNode;
/* 第一个节点，直接插入 */
if (NULL == pBSTTree)
{
mallocInitNode(pInsertNode, value);
pBSTTree = pInsertNode;
return;
}
/* 如果键值已经存在的话，只需要times++ */
if (value =http://www.mamicode.com/= pBSTTree->key)>代码运行结果：
二叉搜索树建立、插入、删除、前继节点、后继节点之c++实现
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。