二叉树2（二叉查找树的插入、查找、删除、遍历）

单纯想用类把它给封装起来
BinarySearchTree.h

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<queue>
using namespace std;
const int MAX = 1000000000;
typedef struct BSTNode
{
int data;
//数据
int num;
//数量
BSTNode* left;
BSTNode* right;
}Node,*pointer;
//
const修饰的函数 函数体内不能对成员数据做任何改动
class BinarySearchTree
{
private:
pointer Root;
pointer Empty(pointer node);
pointer Search(pointer node, int key) const; //内部查找
pointer SearchMin(pointer node) const; //内部查找
pointer Insert(pointer node, int key);
//内部插入
pointer Delete(pointer node, int key); //内部删除
pointer DeleteMin(pointer node);
//删除最小值
void PreOrder(pointer node) const;
//先序
void InOrder(pointer node) const;
//中序
void PostOrder(pointer node) const; //后序
void PrintNode(pointer node) const; //输出节点信息
public:
BinarySearchTree();
~BinarySearchTree();
bool Search(int key) const;
//外部查找
int SearchMin() const;
//查找最小值
bool Insert(int key);
//外部插入
bool Delete(int key);
//删除
void PreOrder() const;
//先序
void InOrder() const;
//中序
void PostOrder() const; //后序
void LeverOrder() const; //层次 宽度优先
void DepthOrder() const; //深度优先 先序的非递归
};
BinarySearchTree::BinarySearchTree()
{
Root = NULL;
}
BinarySearchTree::~BinarySearchTree()
//析构函数在对象作用域结束后调用 如在函数fun内创建node，则A结束就调用
{
Empty(Root);
}
//清空
pointer BinarySearchTree::Empty(pointer node)
{
if (node)
{
Empty(node->left);
Empty(node->right);
free(node);
}
return NULL;
}
//查找 存在返回T 否则返回F
bool BinarySearchTree::Search(int key) const
{
if (Search(Root, key))
return true;
return false;
}
pointer BinarySearchTree::Search(pointer node, int key) const
{
if (node == NULL)
return NULL;
if (key < node->data)
return Search(node->left, key);
else if (key > node->data)
return Search(node->right, key);
else
return node;
}
//查找最小值 若为空树 返回 MAX
int BinarySearchTree::SearchMin() const
{
pointer T = Root;
if (T != NULL)
while (T->left != NULL)
T = T->left;
if (T)
return T->data;
else
return MAX;
}
pointer BinarySearchTree::SearchMin(pointer node) const
{
if (node == NULL)
return NULL;
else if (node->left == NULL)
return node;
else
return SearchMin(node->left);
}
//插入 
bool BinarySearchTree::Insert(int key)
{
if (Insert(Root, key))
return true;
return false;
}
pointer BinarySearchTree::Insert(pointer node, int key)
{
if (node == NULL)
{
node = (pointer)malloc(sizeof(Node));
if (node == NULL)
{
perror("Allocate dynamic memory");
//错误输出语句
return node;
}
node->data = key;
node->num = 1;
node->left = node->right = NULL;
if (Root == NULL)
//这一步必须有 传入的指针仅仅是一个拷贝，方法不会改变原指针的地址、值，但是可能会改变原指针所指向内存块的数据
Root = node;
}
else if (key < node->data)
node->left = Insert(node->left, key);
else if (key > node->data)
node->right = Insert(node->right, key);
else
node->num++;
return node;
}
//删除
bool BinarySearchTree::Delete(int key)
{
if (Delete(Root, key))
return true;
return false;
}
pointer BinarySearchTree::DeleteMin(pointer node)
{
pointer current = node;
pointer parent = node;
node = node->right;
if (node->left == NULL)
//如果右子树没有左子树 那么它直接替代
{
current->data = node->data;
current->right = node->right;
//就算右子树为空也可以直接NULL
}
else
{
while (node->left != NULL)
//找到右子树的最小子树
{
parent = node;
node = node->left;
}
current->data = node->data;
parent->left = node->right;
}
free(node);
return current;
}
pointer BinarySearchTree::Delete(pointer node, int key)
{
if (node == NULL)
return NULL;
else if (key < node->data)
node->left = Delete(node->left, key);
else if (key > node->data)
node->right = Delete(node->right, key);
else if (node->left && node->right)
//2个儿子都有
{
//直接在查找的时候就删除了
node = DeleteMin(node);
}
else
//一个或者0个儿子
{
pointer temp = node;
if (node->left == NULL)
node = node->right;
else if (node->right == NULL)
node = node->left;
if (temp->data == Root->data)
//如果是删除根 Root要重定向一下
Root = node;
free(temp);
}
return node;
}
//遍历
void BinarySearchTree::PrintNode(pointer node) const
{
printf("%d ", node->data);
//printf("data: %d num: %dn", node->data, node->num);
}
//先序
void BinarySearchTree::PreOrder() const
{
if (Root)
{
printf("PreOrder: ");
PreOrder(Root);
printf("n");
}
else
printf("Empty Treen");
}
void BinarySearchTree::PreOrder(pointer node) const
{
if (node != NULL)
{
PrintNode(node);
PreOrder(node->left);
PreOrder(node->right);
}
}
//中序
void BinarySearchTree::InOrder() const
{
if (Root)
{
printf("InOrder: ");
InOrder(Root);
printf("n");
}
else
printf("Empty Treen");
}
void BinarySearchTree::InOrder(pointer node) const
{
if (node != NULL)
{
InOrder(node->left);
PrintNode(node);
InOrder(node->right);
}
}
//后序
void BinarySearchTree::PostOrder() const
{
if (Root)
{
printf("PostOrder: ");
PostOrder(Root);
printf("n");
}
else
printf("Empty Treen");
}
void BinarySearchTree::PostOrder(pointer node) const
{
if (node != NULL)
{
PostOrder(node->left);
PostOrder(node->right);
PrintNode(node);
}
}
//层次遍历 用队列
void BinarySearchTree::LeverOrder() const
{
if (Root == NULL)
{
printf("Empty Treen");
return;
}
printf("LevelOrder: ");
pointer temp;
queue<pointer> q;
q.push(Root);
while (!q.empty())
{
temp = q.front();
q.pop();
PrintNode(temp);
if (temp->left)
q.push(temp->left);
if (temp->right)
q.push(temp->right);
}
printf("n");
}
//深度优先 用栈 先序的非递归实现
void BinarySearchTree::DepthOrder() const
{
if (Root == NULL)
{
printf("Empty Treen");
return;
}
printf("DepthOrder: ");
pointer temp;
stack<pointer> s;
s.push(Root);
while (!s.empty())
{
temp = s.top();
s.pop();
PrintNode(temp);
if (temp->right)
s.push(temp->right);
if (temp->left)
s.push(temp->left);
}
printf("n");
}

使用：

#include<iostream>
#include"BinarySearchTree.h"
using namespace std;
int main()
{
BinarySearchTree Tree;
Tree.Insert(12);
Tree.Insert(6);
Tree.Insert(2);
Tree.Insert(10);
Tree.Insert(11);
Tree.Insert(9);
Tree.Insert(7);
Tree.Insert(8);
Tree.Insert(14);
Tree.Delete(6);
Tree.Delete(2);
Tree.PreOrder();
Tree.InOrder();
Tree.PostOrder();
Tree.LeverOrder();
return 0;
}

最后

以上就是隐形手链为你收集整理的二叉树2（二叉查找树的插入、查找、删除、遍历）的全部内容，希望文章能够帮你解决二叉树2（二叉查找树的插入、查找、删除、遍历）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。