Shulou(Shulou.com)06/02 Report--

What this article shares with you is about how to add, delete, check and modify the binary search tree. The editor thinks it is very practical, so I share it with you. I hope you can get something after reading this article. Let's take a look at it with the editor.

The properties of binary search tree:

1. Each node has a key (key) that is used as a search basis, and all nodes have different keys.

two。 The key of the left subtree is smaller than that of the root node.

3. The key of the right subtree is greater than that of the root node.

4. Both left and right subtrees are binary search trees.

# include

Using namespace std

Template

Struct BSTreeNode

{

BSTreeNode* _ left

BSTreeNode* _ right

K _ key

V _ value

BSTreeNode (const K & key, const V & value)

: _ left (NULL)

, _ right (NULL)

, _ key (key)

, _ value (value)

{}

}

Template

< class K, class V>

Class BSTree

{

Typedef BSTreeNode Node

Public:

BSTree ()

: _ root (NULL)

{}

/ * bool Insert (const K & key, const V & value)

{

If (_ root = = NULL)

{

_ root = new Node (key, value)

Return true

}

Node* parent = NULL

Node* cur = _ root

While (cur)

{

If (cur- > _ key > key)

{

Parent = cur

Cur = cur- > _ left

}

Else if (cur- > _ key

< key) { parent = cur; cur = cur->

_ right

}

Else

{

Return false

}

}

If (parent- > _ key > key)

{

Parent- > _ left = new Node (key, value)

}

Else

{

Parent- > _ right = new Node (key, value)

}

Return true

}

Node* Find (const K & key)

{

Node* cur = _ root

While (cur)

{

If (cur- > _ key > key)

{

Cur = cur- > _ left

}

Else if (cur- > _ key

< key) { cur = cur->

_ right

}

Else

{

Return cur

}

}

Return NULL

}

Bool Remove (const K & key)

{

If (_ root = = NULL)

{

Return false

}

Node* parent = NULL

Node* cur = _ root

While (cur)

{

If (cur- > _ key

< key) { parent = cur; cur = cur->

_ right

}

Else if (cur- > _ key > key)

{

Parent = cur

Cur = cur- > _ left

}

Else

{

If (cur- > _ left = = NULL) / / left is empty

{

If (cur = = _ root)

{

_ root = cur- > _ right

}

Else

{

If (parent- > _ left = = cur)

{

Parent- > _ left = cur- > _ right

}

Else

{

Parent- > _ right = cur- > _ right

}

}

Delete cur

}

Else if (cur- > _ right = = NULL) / / right is empty

{

If (parent = = NULL)

{

_ root = cur

}

Else

{

If (parent- > _ left = = cur)

{

Parent- > _ left = cur- > _ left

}

Else

{

Parent- > _ right = cur- > _ left

}

}

Delete cur

}

Both sides of else// are not empty.

{

Node* parent = cur

Node* left = cur- > _ right

While (left- > _ left)

{

Parent = left

Left = left- > _ left

}

Cur- > _ key = left- > _ key

Cur- > _ value = left- > _ value

If (parent- > _ left = = left)

{

Parent- > _ left = left- > _ right

}

Else

{

Parent- > _ right = left- > _ right

}

Delete left

}

Return true

}

}

Return false

} * /

Void Inorder ()

{

Node* root = _ root

_ Inorder (root)

Cout _ left)

Cout _ key _ right)

}

Bool InsertR (const K & key, const V & value)

{

Return _ InsertR (_ root, key, value)

}

Node* FindR (const K & key)

{

Return _ FindR (_ root, key)

}

Bool RemoveR (const K & key)

{

Return _ RemoveR (_ root, key)

}

Protected:

Bool _ InsertR (Node*& root, const K & key, const V & value)

{

If (root = = NULL)

{

Root = new Node (key, value)

Return true

}

If (root- > _ key > key)

{

Return _ InsertR (root- > _ left, key, value)

}

Else if (root- > _ key

< key) { return _InsertR(root->

_ right, key, value)

}

Else

{

Return false

}

}

Node* _ FindR (Node* root, const K& key)

{

If (root = = NULL)

{

Return NULL

}

If (root- > _ key = = key)

{

Return root

}

If (root- > _ key > key)

{

Return _ FindR (root- > _ left, key)

}

Else if (root- > _ key

< key) { return _FindR(root->

_ right, key)

}

}

Bool _ RemoveR (Node*& root, const K& key)

{

If (root = = NULL)

{

Return false

}

If (root- > _ key > key)

{

Return _ RemoveR (root- > _ left, key)

}

Else if (root- > _ key

< key) { return _RemoveR(root->

_ right, key)

}

Else

{

Node* del = root

If (root- > _ left = = NULL) / / left is empty

{

Root = root- > _ right;// there is no need to consider the parent node of the deleted node, because the reference used recursively, the passed parameter is actually the left or right child of the father node.

}

Else if (root- > _ right = = NULL) / / right is empty

{

Root = root- > _ left

}

Both sides of else// are not empty.

{

Node* parent = root

Node* left = root- > _ right

While (left- > _ left)

{

Parent = left

Left = left- > _ left

}

Del = left

Root- > _ key = left- > _ key

Root- > _ value = left- > _ value

If (parent- > _ left = = left)

{

Parent- > _ left = left- > _ right

}

Else

{

Parent- > _ right = left- > _ right

}

}

Delete del

}

Return true

}

Protected:

Node* _ root

}

The above is how to add, delete, check and modify the binary search tree. The editor believes that there are some knowledge points that we may see or use in our daily work. I hope you can learn more from this article. For more details, please follow the industry information channel.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.