数据结构——二叉搜索树（BST）（建立、插入、查找、删除）及遍历

一 、二叉搜索树

1 二叉搜索树的性质

对于树中的每个结点，左子树中所有相的值小于跟根节点的值，右子树中所有相的值大于根节点的值

2 二叉树搜索树的建立

类似于二叉树的建立，再建立左右子树之前需要判断输入值的相对于根节点的大小

创建二叉搜索树

struct BinaryTree { int data; BinaryTree* left; BinaryTree* right; } BinaryTree* CreatBST (BinaryTree* Root , int val) { if (root == nullptr)//如果为空的二叉树,便将新的节点设定为根节点 { root = new Binarytree; root->data = val; root->left = nullptr; root->right = nullptr; } else if (root->data < val)//如果新值比节点值大，递归地建立右子树 root->right = CreatBST(root->right, val); else if (root->data > val)//如果新值比节点值小，递归地建立左子树 root->left = CreatBST(root->left, val); else exit(-1); return root; }

2 二叉树搜索树的查找

1 找到 二叉搜索树中的某个值。或者是判断二叉搜索树中是否存在某个值，若存在，返回true,不存在，返回false.

BinaryTree* FindBST (BinaryTree* Root , int val) { if(Root == nullptr) return nullptr; if (val == Root->data) return Root; if(val > Root->data) return FindBST ( Root->right, int val); if(val < Root->data) return FindBST ( Root->left, int val); } // bool FindBST (BinaryTree* Root , int val) { if(Root == nullptr) return false; if(val > Root->data) return FindBST ( Root->right, int val); if(val < Root->data) return FindBST ( Root->left, int val); else return true; }

2 找到最大的节点，或者找到最小的节点

//现在返回的是节点，看清楚是要求返回节点或者值 BinaryTree* FindminBST (BinaryTree* Root ) { if(Root == nullptr) return nullptr; if ( Root-> left == null) return Root; else return FindminBST ( Root->left); } // BinaryTree* FindmaxBST (BinaryTree* Root ) { if(Root == nullptr) return nullptr; if ( Root-> right == null) return Root; else return FindmaxBST ( Root->right); }

3 二叉搜索树插入节点

搜索树的插入相比于二叉树的插入 需要判断相对于根节点的大小

 

//若是空树，就先创建一个，否则进行递归，直到找到符合判断条件后，以该值创建节点。 void BinaryTree* Insert (BinaryTree* Root , int val) { if(Root == null) { BinaryTree* Root == new BinaryTree(); Root->data = val; Root->left = null; Root->right = null; } if(Root->data > val) Insert ( Root->left , int val); else if Root->data < val) Insert ( Root->right , int val); }

4 二叉搜索树删除节点（最难懂的一点）

分为以下三种情况：

1. 若删除的节点没有孩子的时候，直接删除此节点，然后将父节点NULL；

2.若删除的节点有一个孩子的时候，直接将父节点连接到其孩子节点，然后删除此节点。

3.若有两个节点的时候，这时候就要找个节点代替它了，因为二叉搜索树具有左子树比此节点的值都小，右子树比此节点的值大，所以（1）可以找左子树中节点最大的元素，也就是左子树中最右端的元素，（2）也可以找右子树中节点最小的元素，也就是右子树中最左端的节点。让此节点的值等于子树中选出的值，然后删除子树中的节点，因为被删除的节点不是在最右端就是在最左端，所以可知此节点只有一个孩子。。。。然后转到第二种情况。。。

具体参考博客：https://blog.csdn.net/qq_41410799/article/details/80903484