Shulou(Shulou.com)05/31 Report--

This article introduces the relevant knowledge of "how to search binary tree in C++". In the operation of actual cases, many people will encounter such a dilemma, so let the editor lead you to learn how to deal with these situations. I hope you can read it carefully and be able to achieve something!

Binary search tree (English: Binary Search Tree), also known as binary search tree, ordered binary tree (English: ordered binary tree), ordered binary tree (English: sorted binary tree), refers to an empty tree or a binary tree with the following properties:

If the left subtree of any node is not empty, the value of all nodes on the left subtree is less than the value of its root node.

If the right subtree of any node is not empty, the value of all nodes on the right subtree is greater than that of its root node.

The left and right subtrees of any node are also binary search trees, respectively.

There are no nodes with equal key values.

# pragma oncetemplatestruct BSTreeNode {K _ key; V _ value; BSTreeNode* _ left; BSTreeNode* _ right; BSTreeNode (const K & key, const V & value): _ key (key), _ value (value), _ left (NULL), _ right (NULL) {}; templateclass BSTree {typedef BSTreeNode Node Public: BSTree (): _ root (NULL) {} bool Insert (const K & key, const V & value) {if (NULL = = _ root) / / if empty tree {_ root = new Node (key, value); return true } Node* parent = NULL; Node* cur = _ root; / / determine where to insert the node while (cur) {if (key)

_ key) {parent = cur; cur = cur- > _ left;} else if (key > cur- > _ key) {parent = cur Cur = cur- > _ right;} else// already exists key {return false }} / / insert node if (key > parent- > _ key) parent- > _ right = new Node (key, value); else parent- > _ left = new Node (key, value) } / / Insert Recursive bool InsertR (const K & key, const V & value) {return _ InsertR (_ root, key, value) } bool _ InsertR (Node*& root, const K & key, const V & value) {if (NULL = = root) {root = new Node (key, value); return true } if (key > root- > _ key) return _ InsertR (root- > _ right, key, value); else if (key

_ key) return _ InsertR (root- > _ left, key, value); else return false;} Node* Find (const K & key) {Node* cur = _ root While (cur) {if (key > cur- > _ key) cur = cur- > _ right; else if (key

_ key) cur = cur- > _ left; else return cur;} return NULL;} / / Find Recursive Node* FindR (const K & key) {return _ FindR (_ root, key) } Node* _ FindR (Node* root, const K& key) {if (NULL = = root) return NULL; if (key > root- > _ key) return _ FindR (root- > _ right, key); else if (key

_ key) return _ FindR (root- > _ left, key); else return root;} bool Remove (const K & key) {Node* parent = NULL; Node* cur = _ root / / determine the location of the deleted node while (cur) {if (key > cur- > _ key) {parent = cur; cur = cur- > _ right } else if (key

_ key) {parent = cur; cur = cur- > _ left;} else {break }} if (NULL = = cur) / / there is no such node {return false;} Node* del If (NULL = = cur- > _ left) / / the left child of the delete node is empty {del = cur / / the deleted node is the root node if (NULL = = parent) {_ root = _ root- > _ right } else {if (cur = = parent- > _ left) parent- > _ left = cur- > _ right Else parent- > _ right = cur- > _ right;}} else if (NULL = = cur- > _ right) / / the right child of the delete node is empty {del = cur If (NULL = = parent) {_ root = _ root- > _ left } else {if (cur = = parent- > _ left) parent- > _ left = cur- > _ right Else parent- > _ right = cur- > _ left }} else// the left and right children of the deleted node are not empty. Find the leftmost node of the right subtree to replace it and delete {parent = cur; Node* leftmost = cur- > _ right. While (leftmost- > _ left) {parent = leftmost; leftmost = leftmost- > _ left;} del = leftmost; cur- > _ key = leftmost- > _ key Cur- > _ value = leftmost- > _ value; if (leftmost = = parent- > _ left) parent- > _ left = leftmost- > _ right; else parent- > _ right = leftmost- > _ right } return true;} / / Remove Recursive bool RemoveR (const K & key) {return _ RemoveR (_ root, key);} bool _ RemoveR (Node*& root, const K& key) {if (NULL = = root) return false If (key > root- > _ key) {return _ RemoveR (root- > _ right, key);} else if (key

_ key) {return _ RemoveR (root- > _ left, key);} else {Node* del = root If (NULL = = root- > _ left) {root = root- > _ right;} else if (NULL = = root- > _ right) {root = root- > _ left } else {Node* leftmost = root- > _ right While (leftmost- > _ left) {leftmost = leftmost- > _ left;} swap (root- > _ key, leftmost- > _ key) Swap (root- > _ value, leftmost- > _ value); return _ RemoveR (root- > _ right, key);} delete del;} return true } / / void InOrder () {_ InOrder (_ root);} void _ InOrder (Node* root) {if (NULL = = root) return; _ InOrder (root- > _ left); cout

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.