How to realize BST binary sort Tree in C language
This article mainly introduces the C language how to achieve BST binary sort tree, has a certain reference value, interested friends can refer to, I hope you can learn a lot after reading this article, let the editor take you to understand it.
The details are as follows
Several basic operations of BST- binary sort tree.
Header file declaration and function definition
# include # include typedef int ElemType;/*** definition node * / typedef struct BSTNode {ElemType data;// data field struct BSTNode* lchild,// left child * rchild;// right child} BSTNode;/*** insert node * / int BST_InsertNode (BSTNode** bstNode,ElemType e); / * * create BST tree * / void BST_Create (BSTNode** bstTree,ElemType* dataSet,int n) / * find BST tree node * / BSTNode* BST_SearchNode (BSTNode** bstNode,ElemType e); / * traverse BST tree node * / void BST_PrintNodes (BSTNode* bstNode)
Function writing
# include "BSTree.h" / * insert node * / int BST_InsertNode (BSTNode** bstNode,ElemType e) {/ / if the BST tree is empty, directly create the root node if (* bstNode==NULL) {* bstNode= (BSTNode*) malloc (sizeof (BSTNode)); (* bstNode)-> data=e; (* bstNode)-> lchild=NULL; (* bstNode)-> rchild=NULL; return 1 } / / if the BST tree is not empty, the size relationship between the insertion value and the root node value if ((* bstNode)-> data==e) return 0 is the same as the key value, then the insertion fails else if ((* bstNode)-> data > e) return BST_InsertNode (& (* bstNode)-> lchild,e); / / is greater than the insertion value and takes it as the left subtree node else if ((* bstNode)-> datarchild,e) / / less than the insertion value, use it as the right subtree node} / * create BST tree * / void BST_Create (BSTNode** bstTree,ElemType* dataSet,int n) {int itree 0; * bstTree=NULL;//BST tree initializes to empty while (idata==e) / / verify whether it is the root node return * bstNode; else if ((* bstNode)-> data > e) {return BST_SearchNode (& (* bstNode)-> lchild,e) / / if the value of the root node is less than the value of the root node, look for the left subtree} else {return BST_SearchNode (& (* bstNode)-> rchild,e); / / if it is greater than the value of the root node, find the right subtree}} / * traverse the BST tree node * / void BST_PrintNodes (BSTNode* bstNode) {if (bstNode==NULL) / / the root node determines that {return;} / / prints the value of the root node printf ("% d\ t", (bstNode)-> data) / / traversing if (bstNode- > lchildchildbirth null) BST_PrintNodes ((bstNode)-> lchild) from the root node; / / traversing the left subtree if (bstNode- > rchildbirth null) BST_PrintNodes (bstNode- > rchild); / / traversing the right subtree}
test
# include "BSTree.h" int main (int argc,char** argv) {int i; ElemType arr [] = {45pyrre 24pyrus 53pyrus 2468pyrus 26pyrus 36pyrus 96pyrmus 100pyrus 25pyrus 64pr 78}; / / there are only 4 elements because repeated keywords cannot be inserted into the BSTNode* bstNode=NULL; BSTNode* bstTemp=NULL; / / create BST tree BST_Create (& bstNode,arr,sizeof (arr) / sizeof (ElemType)); printf ("% d\ t% d\ n", bstNode,bstNode- > data); printf ("% d\ t% d\ n", bstNode,bstNode- > lchild- > data) / / find node bstTemp=BST_SearchNode (& bstNode,53); printf ("the aimed node is% d,\ n", bstNode- > data); / / traverse all nodes of the BST tree BST_PrintNodes (bstNode); printf ("\ n");}
Paste the test results as follows: [the number of nodes inserted and traversed is inconsistent because-if the key values of the nodes in the BST tree are the same, the insert operation is terminated]
Thank you for reading this article carefully. I hope the article "how to realize BST binary sort Tree in C language" shared by the editor will be helpful to everyone. At the same time, I also hope that you will support and pay attention to the industry information channel. More related knowledge is waiting for you to learn!
