二叉搜索树（二叉排序树）及其基本操作(查找，插入，删除）C++代码表示（含递归与非递归）看完别告诉我你还不会！

约定不等于承诺〃 2023-02-28 04:08 8阅读 0赞

## 前言 ##

查找问题：

1.  静态查找：我们要找的元素是不动的，我们要做的只有 find 操作，没有 delete 和 insert 操作
2.  动态查找：我们要找的集合会发生动态的变化，不仅有 find 操作，还有delete、find操作

针对静态问题，除了O（n）的顺序查找，还有O(nlogn)的二分查找，为什么二分查找效率这么高，是因为我们事先对数据进行了有效的组织，变成有序化，这样我们可以形成一个叫做判定树的这样一种结构，把线性的查找过程，转化成在树上的查找过程，查找效率，就是树的高度，所以我们就想，能不能把数据直接放到树里面，树的动态性比较强，方便进行插入删除操作，这就引出了一个叫做**二叉搜索树，也叫二叉排序树**

## 什么是二叉搜索树 ##

二叉搜索树又称之为二叉排序树，它不为空树时，它左子树上所有的元素都小于根节点的元素，而根节点右子树上所有的元素都大于根节点的元素。左右子树都是二叉搜索树  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlb3dhaGFoYQ_size_16_color_FFFFFF_t_70]  
二叉搜索树中序遍历为有序数组

## 二叉搜索树的基本操作 ##

查找  
插入  
删除

struct BinTree
    {
        
    	int Data;
    	BinTree* Left;
    	BinTree* Right;
    };

### 查找 ###

思路：

1.  查找最小值的思路即一路向左
2.  查找最大值的思路即一路向右
3.  查找某个数的的位置的思路  
    若根节点不为空  
    如果根节点key==查找key，返回true  
    如查找key<根节点key，在左子树查找  
    如查找key>根节点key，在右子树查找

查找效率和树的高度有关

#### 递归表示 ####

BinTree* FindMin(BinTree * BST) {
        
    	BinTree* Node = BST;
    	if (Node->Left) 
    		return FindMin(Node->Left);
    	return Node;
    }//递归法找最小值节点
    
    BinTree* FindMax(BinTree* BST) {
        
    	BinTree* Node = BST;
    	if (Node->Right)
    		return FindMax(Node->Right);
    	return Node;
    }//递归法找最大值节点
    
    BinTree* Find(BinTree* BST, int key) {
        
    	BinTree* Node = BST;
    	if (!Node)
    		return NULL;
    	if (Node->Data == key)
    		return Node;
    	else if (Node->Data > key)
    		return Find(Node->Left,key);
    	else
    		return Find(Node->Right,key);
    }//递归法找对应key值节点

#### 非递归表示 ####

BinTree* FindMin(BinTree * BST) {
        
    	BinTree* Node = BST;
    	while (Node->Left)
    		Node = Node->Left;
    	return Node;
    }//非递归法找最小值节点
    
    BinTree* FindMax(BinTree* BST) {
        
    	BinTree* Node = BST;
    	while (Node->Right)
    		Node = Node->Right;
    	return Node;
    }//非递归法找最大值节点
    
    BinTree* Find(BinTree* BST, int key) {
        
    	BinTree* Node = BST;
    	if (!Node)
    		return NULL;
    	while (Node)
    	{
        
    		if (Node->Data == key)
    			return Node;
    		else if (Node->Data > key)
    			Node = Node->Left;
    		else
    			Node = Node->Right;
    	}
    }//非递归法找对应key值节点

### 插入 ###

思路：

1.  如果树为空的话，直接插入该元素。
2.  若节点不为空，按照查找的方式，查找应该插入的位置

#### 递归 ####

BinTree* Insert(int key,BinTree *BST) {
        
    	if (!BST) {
        
    		BST->Data = key;
    		BST->Left = NULL;
    		BST->Right = NULL;
    	}
    	else {
        
    		if (key > BST->Data)
    			BST->Right = Insert(key, BST->Right);
    		else if (key < BST->Data)
    			BST->Left = Insert(key, BST->Left);
    	}
    	return BST;
    
    }

#### 非递归 ####

BinTree* Insert(int key,BinTree *BST) {
        
    	BinTree* Node = BST, * parent = NULL;
    	BinTree* T;
    	T->Data = key;
    	T->Left = NULL;
    	T->Right = NULL;
    	if (!BST) {
        //根节点为空，直接插入
    		BST = T;
    		return BST;
    	}
    	while (Node) {
        //遍历查找空位置
    		if (key < Node->Data) {
        //应该插入左子树
    			parent = Node;
    			Node = Node->Left;
    		}
    		else if (key > Node->Data) {
        //插入右子树中
    			parent = Node;
    			Node = Node->Right;
    		}
    		else//待插入元素已存在
    			return BST;
    	}
    	if (key > parent->Data)
    		parent->Right = T;
    	else if (key < parent->Data)
    		parent->Left = T;
    	else//待插入元素已存在
    		return BST;
    	return BST;
    }

### 删除 ###

考虑三种情况：

1.  要删除的是叶节点：直接删除，再修改其父节点指向叶节点的指针，置为NULL
2.  要删除的节点只有一个子节点：将其父节点指向待删除节点的指针指向待删除节点的子节点
3.  要删除的节点有左右节点：用另一个节点替代被删除节点，如左边树的最大元素，或者右边树的最小元素。而且替代节点是一定没有两个子节点的，所以可以将问题简单化

#### 递归 ####

BinTree* Delete(int key, BinTree* BST) {
        
    	BinTree* Node = NULL;
    	if (!BST)
    		return BST;//如果未找到空，返回NULL
    	else if (key < BST->Data)
    		BST->Left = Delete(key, BST->Left);
    	else if (key > BST->Data)
    		BST->Right = Delete(key, BST->Right);
    	else {
        //找到待删除的节点了
    		if (BST->Left && BST->Right) {
        //待删除的节点有两个子结点
    			Node = FindMin(BST->Right);
    			BST->Data = Node->Data;
    			BST->Right = Delete(BST->Data, BST->Right);
    		}
    		else {
        //待删除的节点只有一个或者没有子节点
    			if (!BST->Left)//有右节点或者无子节点
    				BST = BST->Right;
    			else if (!BST->Right)//有左节点或者无子结点
    				BST = BST->Left;
    		}
    	}
    	return BST;
    }

#### 非递归 ####

BinTree* Delete(int key, BinTree* BST) {
        
    	if (!BST)
    		return NULL;
    	BinTree* parent = NULL, * Node = BST;//parent 表示待删除节点的父节点，Node表示待删除节点
    	while (Node && Node->Data != key){
        
    		parent = Node;
    		if (Node->Data > key)
    			Node = Node->Left;
    		else
    			Node = Node->Right;
    	}
    	if (!Node)//如果没找到，返回根节点
    		return BST;
    	BinTree* DelNode = Node;
    	if (Node->Right && Node->Left){
        
    		parent = DelNode;
    		DelNode = Node->Left;
    		while (DelNode->Right) {
        
    			parent = DelNode;
    			DelNode = DelNode->Right;
    		}
    	}
    
    	if (!DelNode->Left && !DelNode->Right) {
        //DelNode没有子结点
    		if (parent) {
        
    			if (DelNode->Data < parent->Data)
    				parent->Left = NULL;
    			else
    				parent->Right = NULL;
    		}
    		if (!parent)
    			BST = NULL;
    	}
    	else {
        //有一个子结点
    		BinTree* child;
    		if (DelNode->Left)
    			child = DelNode->Left;
    		if (DelNode->Right)
    			child = DelNode->Right;
    		if (parent) {
        //确定child是parent的哪个子结点
    			if (parent->Data < child->Data)
    				parent->Right = child;
    			else
    				parent->Left = child;
    		}
    		if (!parent) BST = child;//parent为NULL，说明删除的是根节点，那么child成为新的根节点
    		if (DelNode != Node)//DelNode是Node的前驱节点
    			Node->Data = DelNode->Data;
    		delete DelNode;
    		return BST;
    	}
    }

若有错误，欢迎指出

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xlb3dhaGFoYQ_size_16_color_FFFFFF_t_70]: /images/20230209/26506d34e6ff472a866081500cce72a2.png