C++ binary search tree how to use
This article introduces the knowledge of "how to use C++ binary search tree". 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!
If the data is stored sequentially, we use sequential search, and when ordered, we use half-and-half search, interpolation search, Fibonacci search. But when you need to insert and delete
When you need to use the chain type.
In this case, we introduce a binary sort tree (binary search tree).
Threaded binary tree node- > left .data
< node.data < node->Right.data
The ergodic time of the middle order is the increasing sequence InOrderTraverse.
Pay attention to the deletion of nodes; there are 4 types
1. Find the maximum value to replace node from node- > left
two。 Find the minimum value to replace node from node- > right
3. Move node- > right as a whole to the right of the maximum value of node- > left
4. Move node- > left as a whole to the left of the minimum node- > right
However, considering the depth of the tree, it is best to use the first two, so it is designed to balance the left and right nodes of the tree, the AVL tree.
# include # include using namespace std; typedef struct treenode {int data; struct treenode * left; struct treenode * right;} TREE_NODE;// node typedef struct Bstree {TREE_NODE* root; int size;} BSTREE;// binary tree BSTREE* create_tree () / / create {BSTREE* tree = new (BSTREE); tree- > root = NULL Tree- > size = 0; return tree;} TREE_NODE* create_node (int data) / / create node {TREE_NODE* node = new (TREE_NODE); node- > data = data; node- > left = NULL; node- > right = NULL } void insert (TREE_NODE* node, TREE_NODE** root) / / insert a node to that location {if (NULL = * root) {* root = node;} else {if (node- > data > (* root)-> data) {insert (node, & (* root)-> right) } else {insert (node, & (* root)-> left);}} void PreOrderTraverse (TREE_NODE* root) / / preorder traversal {if (root) {cout data right) }} void InOrderTraverse (TREE_NODE* root) / / Central order traversal {if (root) {InOrderTraverse (root- > left); cout data left); PostOrderTraverse (root- > right); cout data size) + + } TREE_NODE** bstree_find (int data, TREE_NODE** root) / / find the location corresponding to DATA {if (NULL==*root) {return root;} if (data > (* root)-> data) {return bstree_find (data,& (* root)-> right);} else if (data)
< (*root)->Data) {return bstree_find (data, & (* root)-> left);} else {return root;} / / below is a non-recursive lookup * root if (NULL==*root) {return root;} TREE_NODE* temp = * root While (temp & & (temp- > data! = data) {if (data > temp- > data) {temp = temp- > right;} else if (data
< temp->Data) {temp = temp- > left;} if (temp) {return & temp;} else {return & temp } void del_node (TREE_NODE* node) / / Delete the node {delete (node) } bool bstree_erase (int data, BSTREE* tree) / / insert the incoming address into the tree. If you want to modify this address variable, modify {TREE_NODE** node = bstree_find (data, & tree- > root); if (* node) {TREE_NODE* temp = * node If ((* node)-> right==NULL) & & ((* node)-> left==NULL)) / / if it is a leaf node {* node = NULL; del_node (temp);-- tree- > size } right of if ((* node)-> right==NULL) & & (* node)-> leftkeeper null) / / node is empty {* node = (* node)-> left; del_node (temp);-- tree- > size } left of else if ((* node)-> rightlighting null) & & ((* node)-> left==NULL)) / / node is empty {* node = (* node)-> right; del_node (temp);-- tree- > size } / / if the left and right subtrees are not deleted, it is best to replace the deleted node if (* node)-> left! = NULL) & ((* node)-> right! = NULL) with the maximum number of 12 / / left when the left and right subtrees are not empty. {TREE_NODE* s = (* node)-> left While (s-> right) {temp=s; slots-> right;} (* node)-> data = s-> data If (temp! = * node) {temp- > righ = s-> left;} else {temp- > left = s-> left / / similar to left subtree} del_node (s);-- tree- > size } / / the left and right sides of node are not empty to replace the deleted node if (* node)-> left! = NULL) & & ((* node)-> right! = NULL)) {TREE_NODE* s = (* node)-> right While (s-> left) {temp=s; slots-> left;} (* node)-> data = s-> data If (temp! = * node) {temp- > left = s-> right;} else {temp- > right = s-> right / / similar to right subtree} del_node (s);-- tree- > size } / / the left and right sides of node are not empty, move the whole right side directly below the left maximum if (* node)-> left! = NULL) & & ((* node)-> right! = NULL)) {TREE_NODE* s = (* node)-> left While (s-> right) {swatches-> right;} s-> right = (* node)-> right; * node = (* node)-> left; del_node (s) -- the left and right sides of tree- > size;} / / node are not empty. Move the left side as a whole under the right minimum if (* node)-> left! = NULL) & & (* node)-> right! = NULL) {TREE_NODE* s = (* node)-> right While (s-> left) {swatches-> left;} s-> left = (* node)-> left; * node = (* node)-> right; del_node (s) -- tree- > size;} return true;} return false;} void bstree_updata (BSTREE* tree,int old,int now) / / replacement and update {while (bstree_erase (old,tree)) {bstree_insert (now,tree) }} void clear_node (TREE_NODE** root) / / clear node {if (* root) {clear_node (& (* root)-> left); clear_node (& (* root)-> right); del_node (* root); * root = NULL }} void clear_tree (BSTREE* tree) / / clear_tree {clear_node (& tree- > root); tree- > size = 0;} void bstree_destroy (BSTREE* tree) / / bstree_destroy {clear_tree (tree); delete (tree);} int bstree_size (BSTREE* tree) / / size {return tree- > size } int bstree_deep (TREE_NODE* root) / / Deep DEPTH {if (root) {int Hleft = bstree_deep (root- > left); int Hright = bstree_deep (root- > right); return Hleft > Hright? Hleft+1: Hright+1;} return 0;} void printNodeByLevel (TREE_NODE* root) / / sequence traversal {if (root = = NULL) {return;} vectorvec; vec.push_back (root); int cur=0; int last = 1; while (cur)
