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

How to search binary tree analysis, I believe that many inexperienced people do not know what to do. Therefore, this paper summarizes the causes and solutions of the problem. Through this article, I hope you can solve this problem.

First, search the binary tree

1. Definition: it is a sorted binary tree, but it can be empty.

2. Nature:

Each node has a key as the basis for searching, and the keys of all nodes are different.

The key of all nodes on the left subtree is less than the key of the root node (key)

The key of all nodes on the right subtree is greater than the key of the root node (key)

The left and right subtrees are binary search trees.

II. Source code

1. Define the node

Templatestruct BSTreeNode {BSTreeNode * _ left;// left node BSTreeNode * _ right;// right node K _ key;// node weight V _ value BSTreeNode (const K & key,const V & value): _ key (key), _ value (value), _ left (NULL), _ right (NULL) {}}

2. Search binary tree and its related implementation.

Templateclass BSTree {typedef BSTreeNode Node;public: BSTree (): _ root (NULL) {} / / non-recursive Node* Find (const K & key) {return _ Find (_ root,key) } bool Insert (const K & key,const V & value) {return _ Insert (_ root,key,value);} bool Remove (const K & key) {return _ Remove (_ root,key) } / / Recursive bool InOrder () / / medium order traversal-- > ordered sequence {return _ InOrder (_ root); cout key) {cur=cur- > _ right;} else if (cur- > _ key)

< key) { cur=cur->

_ left;} else {return cur;} return NULL } bool _ Insert (Node * & root,const K & key,const V & value) {if (root= = NULL) {root=new Node (key,value); return true;} Node * cur=root; Node * parent=NULL While (cur) {if (cur- > _ key)

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

_ right;} else if (cur- > _ key > key) {parent=cur; cur=cur- > _ left } else return false;} if (parent- > _ key

< key) { parent->

_ right=new Node (key,value); parent- > _ right=parent;} else {parent- > _ left=new Node (key,value); parent- > _ left=parent;} return true } bool _ Remove (Node*& root,const K & key) {if (root = = NULL) return false; Node* cur=root; Node* parent=NULL While (cur) / / find the node {if (cur- > _ key > key) {parent=cur; cur=cur- > _ left } else if (cur- > _ key)

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

_ right } else / / find node {if (cur- > _ left = = NULL) / / left empty {if (parent = = NULL) Root=cur- > _ right Else if (parent- > _ left= = cur) parent- > _ left=cur- > _ right; else parent- > _ right=cur- > _ right } else if (cur- > _ right = = NULL) / / right is empty {if (parent = = NULL) root=cur- > _ left Else if (parent- > _ left= = cur) parent- > _ left=cur- > _ left; else parent- > _ right=cur- > _ left } else / / is not empty {Node * parent=cur; Node * left=cur- > _ right / / the leftmost node of the right subtree while (left- > _ left) {left=left- > _ left } cur- > _ key=left- > _ key;// replace node cur- > _ value=left- > _ value If (parent- > _ left= = left) parent- > _ left=left- > _ left; else parent- > _ right=left- > _ right Delete left;}} return true;} return false } / / Recursive bool _ InOrder (Node * root) {if (root = = NULL) return false; _ InOrder (root- > _ left); cout_key > key) return _ FindR (root- > _ left,key) Else return _ FindR (root- > _ right,key);} 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;} 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 / / find the node {Node * del=NULL; if (root- > _ left = = NULL) root=root- > _ right Else if (root- > _ right = = NULL) root=root- > _ left; else {Node * parent=NULL; Node * left=root While (left- > _ left) {parent=left; left=left- > _ left;} root- > _ key=left- > _ key Root- > _ value=left- > _ value; del=left; if (parent- > _ left= = left) parent- > _ left=left- > _ left Else parent- > _ right=left- > _ right; delete del; return true;}} return false } protected: Node * _ root;}

3. Summary:

The search binary tree is a sorted binary tree that can be empty. Every node of it obeys the nature of searching binary tree.

After searching the middle order of the binary tree, it is an ascending sequence; its search is carried out according to the key value and properties; its insertion needs to first find the inserted node according to its key value, and then add the node, in addition, its key value is unique.

When deleting a node, it needs to be divided into three situations:

(1) left is empty only

(2) only the right is empty

(3) the left and right sides of the node are not empty.

To delete the node, you need to find the leftmost node of the right subtree or the rightmost node of the left subtree as the replacement node.

After reading the above, have you mastered the method of how to search binary tree analysis? If you want to learn more skills or want to know more about it, you are welcome to follow the industry information channel, thank you for reading!

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.