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

Editor to share with you how to achieve binary search tree, I believe that most people do not know much about it, so share this article for your reference, I hope you can learn a lot after reading this article, let's learn about it!

Binary search tree, also known as binary sort tree, has the following characteristics:

For each subtree, if the left subtree is not NULL, then all nodes of the left subtree are less than its root node value.

For each subtree, if the right subtree is not NULL, then all nodes of the left subtree are greater than its root node value.

There are no nodes with equal key values.

The basic operations to complete the binary search tree are:

Insert a node.

Find the node.

Find the smallest keyword: according to the characteristics of the binary search tree, it should be the leftmost node

Find the largest keyword: according to the characteristics of the binary search tree, it should be the rightmost node

Delete the node.

In the above operations, the difficulty lies in inserting and deleting. The main ideas are as follows:

Insert: according to the comparison between the insertion data and the node, find its insertion position. If it is larger than the node value, continue to look for the right subtree of the node until the right child of the node is empty, and take the new node as its right child; if it is smaller than the node value, then continue to look for the left subtree of the node until the left child of the node is empty, and take the new node as its left child.

Delete: set the node to be found as d

If d has a left subtree, replace it with the left child of d, find the rightmost node r of the left subtree, and take the right child of f as the right subtree of r.

If d has no left subtree, replace it with its right child directly.

However, when performing the delete operation, we should pay attention to whether the node to be deleted is several special nodes: empty node, root node, leaf node.

Code example:

/ / insert node / / find element / / find minimum keyword / / find maximum keyword / / delete node # include # include typedef struct Node {int data; struct Node* lchild; struct Node* rchild; struct Node* parent;} Node / / if you insert a node / / into the binary search tree, you may want to change the address of the root node, so the secondary pointer void insert_node (Node** root,int _ data) {Node* newnode= (Node*) malloc (1*sizeof (Node)); newnode- > data=_data; newnode- > lchild=NULL; newnode- > rchild=NULL; newnode- > parent=NULL; if (* root==NULL) {* root=newnode; return } if ((* root)-> lchild==NULL & & _ data

Data) {(* root)-> lchild=newnode; newnode- > parent=*root; return;} if ((* root)-> rchild==NULL & & _ data > (* root)-> data) {(* root)-> rchild=newnode; newnode- > parent=*root; return;} if (_ data)

Data) {insert_node (& (* root)-> lchild,_data);} else {if (_ data > (* root)-> data) {insert_node (& (* root)-> rchild,_data);} else {return Output Node element void print_tree (Node* root) {if (root==NULL) return; printf ("% d\ t", root- > data); print_tree (root- > lchild); print_tree (root- > rchild) } / / find the element, find the node pointer that returns the keyword, and cannot find the return NULL Node* find_node (Node* root,int _ data) {if (root==NULL | | (_ data = = root- > data)) {return root;} if (_ data)

Data) {return find_node (root- > lchild,_data);} if (_ data > root- > data) {return find_node (root- > rchild,_data);}} / / find the minimum keyword, and return NULL Node* search_min (Node* root) {if (root==NULL) {return NULL;} if (root- > lchild==NULL) {return root if the tree is empty } search_min (root- > lchild);} / / find the maximum keyword Node* search_max (Node* root) {if (root==NULL) {return NULL;} if (root- > rchild==NULL) {return root;} search_max (root- > rchild) } / / Delete a node according to the keyword, and the deletion returns 1 successfully, otherwise 0 is returned. If the root node is deleted, the address of the root node should be changed, so the second-level pointer / * thought is passed: 1. If p has a left subtree, the left child of p replaces it; find the rightmost leaf node r of the left subtree, and take the right subtree of p as the right subtree of r. two. If p does not have a left subtree, replace it with the right child of p. * / void delete_node (Node** root,int _ data) {if (root==NULL) return; Node* dnode=find_node (* root,_data); if (dnode==NULL) {return;} if (dnode- > lchild==NULL & & dnode- > rchild==NULL & & dnodekeeper root) {if (dnode- > parent- > lchild==dnode) {dnode- > parent- > lchild=NULL } if (dnode- > parent- > rchild==dnode) {dnode- > parent- > rchild=NULL;} free (dnode); dnode=NULL; return;} / if there is no left subtree if (dnode- > lchild==NULL) {/ / if this node is the root node if (dnode==*root) {* root= (* root)-> rchild (* root)-> parent=NULL; free (dnode); return;} / / if this node is the parent's left child if (dnode- > parent- > lchild==dnode) {dnode- > parent- > lchild=dnode- > rchild; dnode- > rchild- > parent=dnode- > parent; free (dnode); return } / / if this node is the right child of the parent, if (dnode- > parent- > rchild==dnode) {dnode- > parent- > rchild=dnode- > rchild; dnode- > rchild- > parent=dnode- > parent; free (dnode); return }} if (dnode- > lchildchild trees null) {/ / find the rightmost leaf node r of its left subtree, and take the right subtree of p as the right subtree of r. Node* rnsdnode-> lchild; while (r-> rchildbirth null) {rsqur-> rchild;} r-> rchild=dnode- > rchild; dnode- > rchild- > parent=r- > rchild; / / replace ta if (dnode==*root) {* root=dnode- > lchild; (* root)-> parent=NULL with the left node of dnode } else {if (dnode- > parent- > lchild==dnode) {dnode- > parent- > lchild=dnode- > lchild; dnode- > lchild- > parent=dnode- > parent;} if (dnode- > parent- > rchild==dnode) {dnode- > parent- > rchild=dnode- > lchild; dnode- > lchild- > parent=dnode- > parent }} free (dnode); dnode=NULL;}} int main (int argc, char const * argv []) {Node* root=NULL; insert_node (& root,15); insert_node (& root,6); insert_node (& root,18); insert_node (& root,3); insert_node (& root,7); insert_node (& root,17) Insert_node (& root,20); print_tree (root); printf ("\ n"); Node* f=find_node (root,6); if (favored null) {printf ("% d\ n", f-> parent- > data);} delete_node (& root,3); print_tree (root); printf ("\ n"); return 0 } these are all the contents of the article "how to achieve a binary search Tree". Thank you for reading! I believe we all have a certain understanding, hope to share the content to help you, if you want to learn more knowledge, welcome to 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.