当前位置: 首页 > >

[数据结构]二叉搜索树 / 二叉排序树

发布时间:

概述

二叉搜索树又称二叉排序树,它或者是一棵空树,或者是具有以下性质的二叉树:
① 若它的左子树不为空,则左子树上所有节点的值都小于根节点的值
② 若它的右子树不为空,则右子树上所有节点的值都大于根节点的值
③ 它的左右子树也分别为二叉搜索树


例如:


实现
结点的定义

template //泛型
struct BNode {
T data_;
typedef BNode Node; //别名
Node* left;
Node* right;
BNode(const T&data) :data_(data), left(nullptr), right(nullptr)
{}
};


一个数据成员data_保存数据 ,两个结点指针left和right分别指向该节点的左右孩子



树的定义

template
class BTree {
public:
typedef BNode Node;
BTree():root_(nullptr)
{}
private:
Node* root_;
};


root_是一个结点指针,指向该二叉搜索树的根节点



搜索

思路:根据二叉搜索树的性质,根节点左边的值都小于根节点,右边的值都大于根节点,从根节点开始进行递归地比较,直到找到对应的值。


Node* find(const T& val)
{
Node* cur = root_;
while (cur)
{
if (cur->data_ == val)
return cur;
else if (cur->data_ > val)
cur = cur->left;
else
cur = cur->right;
}
}

插入

思路:二叉搜索树默认不插入重复的值
首先如果树为空,直接在根节点处用要插入的值创建一个结点,然后返回;
如果树不为空就进行搜索,找到合适的位置才能进行插入:从根节点开始递归比较,找到正确的插入位置;搜索完毕后插入结点。


注意:此处在搜索完毕之后要保留其父节点的位置,因为待插入的位置一定会是一个叶子节点,所以需要保留其父节点的位置来添加链接关系;大于父节点就在右边插入,小于父节点就在左边插入。


//不插入重复的值
bool insert(const T&val)
{
if (root_ == nullptr)
{
root_ = new Node(val);
return true;
}

//搜索
Node* cur = root_;
Node* parent = nullptr;
while (cur)
{
parent = cur;
if (cur->data_ == val)
return false;
else if (cur->data_ > val)
cur = cur->left;
else
cur = cur->right;
}
//插入
cur = new Node(val);
if (parent->data_ > val)
parent->left = cur;
else
parent->right = cur;


return true;
}

中序遍历

二叉搜索树的特性:中序遍历必然是有序的


例如:下图的中序遍历为:2、3、4、6、7、9、13、15、17、18、20


代码实现:


void inorder()
{
_inorder(root_);
}

//搜索树中序遍历:有序
void _inorder(Node* root_)
{
if (root_)
{
_inorder(root_->left);
cout << root_->data_ << " ";
_inorder(root_->right);
}
}

销毁和析构

思路:如果该树不为空,开始递归遍历,先释放左节点,再释放右节点,最后释放根节点


void destroy(Node* root)
{
if (root)
{
destroy(root->left);
destroy(root->right);
cout << "destroy:" << root->data_ << " ";
delete root;
}
}

~BTree()
{
if (root_)
{
destroy(root_);
root_ = nullptr;
}
}

拷贝和拷贝构造

思路:这里一定要使用深拷贝,不能只拷贝原树的根节点,要将结构和数据一起拷贝在新开的内存地址中,会带来指针二次释放的问题。


递归遍历,将原树所有的结点先创建出来,然后添加链接关系,返回新创建的树的根节点;在拷贝构造函数中调用即可


//拷贝二叉搜索树的数据和结构
Node* copy(Node* root)
{
if (root == nullptr)
return nullptr;
//拷贝根
Node* newnode = new Node(root->data_);
//拷贝左子树
newnode->left = copy(root->left);
//拷贝右子树
newnode->right = copy(root->right);

return newnode;
}

//在成员初始化列表阶段调用copy()函数进行拷贝构造
BTree(const BTree& btree):root_(copy(btree.root_))
{}

完整代码:

#include

using namespace std;
template
struct BNode {
T data_;
typedef BNode Node;
Node* left;
Node* right;

BNode(const T&data) :data_(data), left(nullptr), right(nullptr)
{}

};

template
class BTree {
public:
typedef BNode Node;
BTree():root_(nullptr)
{}

//不插入重复的值
bool insert(const T&val)
{
if (root_ == nullptr)
{
root_ = new Node(val);
return true;
}

//搜索
Node* cur = root_;
Node* parent = nullptr;
while (cur)
{
parent = cur;
if (cur->data_ == val)
return false;
else if (cur->data_ > val)
cur = cur->left;
else
cur = cur->right;
}
//插入
cur = new Node(val);
if (parent->data_ > val)
parent->left = cur;
else
parent->right = cur;

return true;
}

Node* find(const T& val)
{
Node* cur = root_;
while (cur)
{
if (cur->data_ == val)
return cur;
else if (cur->data_ > val)
cur = cur->left;
else
cur = cur->right;
}
}

void inorder()
{
_inorder(root_);
}

//搜索树中序遍历:有序
void _inorder(Node* root_)
{
if (root_)
{
_inorder(root_->left);
cout << root_->data_ << " ";
_inorder(root_->right);
}
}

//拷贝二叉搜索树的数据和结构
Node* copy(Node* root)
{
if (root == nullptr)
return nullptr;
//拷贝根
Node* newnode = new Node(root->data_);
//拷贝左子树
newnode->left = copy(root->left);
//拷贝右子树
newnode->right = copy(root->right);

return newnode;
}

//在成员初始化列表阶段调用copy()函数进行拷贝构造
BTree(const BTree& btree):root_(copy(btree.root_))
{}


void destroy(Node* root)
{
if (root)
{
destroy(root->left);
destroy(root->right);
//cout << "destroy:" << root->data_ << " ";
delete root;
}
}

~BTree()
{
if (root_)
{
destroy(root_);
root_ = nullptr;
}
}

private:
Node* root_;
};

void test()
{
BTree b;
b.insert(15);
b.insert(6);
b.insert(18);
b.insert(3);
b.insert(7);
b.insert(17);
b.insert(20);
b.insert(2);
b.insert(9);
b.insert(4);
b.insert(13);
BTree a(b);
b.inorder();
cout << endl;
}
int main()
{
test();
return 0;
}



友情链接: