您好,登錄后才能下訂單哦!
這篇文章主要介紹了C語言如何實(shí)現(xiàn)BST二叉排序樹,具有一定借鑒價值,感興趣的朋友可以參考下,希望大家閱讀完這篇文章之后大有收獲,下面讓小編帶著大家一起了解一下。
具體內(nèi)容如下
BST-二叉排序樹的幾個基本操作。
頭文件聲明與函數(shù)定義
#include <stdio.h> #include <stdlib.h> typedef int ElemType; /** * 定義節(jié)點(diǎn) */ typedef struct BSTNode{ ElemType data;//數(shù)據(jù)域 struct BSTNode *lchild,//左孩子 *rchild;//右孩子 }BSTNode; /** * 插入節(jié)點(diǎn) */ int BST_InsertNode(BSTNode** bstNode,ElemType e); /** * 創(chuàng)建BST樹 */ void BST_Create(BSTNode** bstTree,ElemType* dataSet,int n); /** * 查找BST樹節(jié)點(diǎn) */ BSTNode* BST_SearchNode(BSTNode** bstNode,ElemType e); /** * 遍歷BST樹節(jié)點(diǎn) */ void BST_PrintNodes(BSTNode* bstNode);
函數(shù)編寫
#include "BSTree.h" /** * 插入節(jié)點(diǎn) */ int BST_InsertNode(BSTNode** bstNode,ElemType e){ //如果BST樹為空,直接創(chuàng)建根節(jié)點(diǎn) if (*bstNode==NULL) { *bstNode=(BSTNode*)malloc(sizeof(BSTNode)); (*bstNode)->data=e; (*bstNode)->lchild=NULL; (*bstNode)->rchild=NULL; return 1; } //如果BST樹不為空,則比較插入值與根節(jié)點(diǎn)值的大小關(guān)系 if ((*bstNode)->data==e) return 0;//關(guān)鍵值相同,則插入失敗 else if ((*bstNode)->data>e) return BST_InsertNode(&(*bstNode)->lchild,e);//大于插入值,將其作為左子樹節(jié)點(diǎn) else if ((*bstNode)->data<e) return BST_InsertNode(&(*bstNode)->rchild,e);//小于插入值,將其作為右子樹節(jié)點(diǎn) } /** * 創(chuàng)建BST樹 */ void BST_Create(BSTNode** bstTree,ElemType* dataSet,int n){ int i=0; *bstTree=NULL;//BST樹初始化為空 while (i<n) { printf("%d\t",dataSet[i]); BST_InsertNode(bstTree,dataSet[i++]); } printf("\n"); } /** * 查找BST樹節(jié)點(diǎn) */ BSTNode* BST_SearchNode(BSTNode** bstNode,ElemType e){ if (*bstNode==NULL)//判空 return *bstNode; //查找結(jié)點(diǎn) if ((*bstNode)->data==e)//驗(yàn)證是否為根節(jié)點(diǎn) return *bstNode; else if ((*bstNode)->data>e) { return BST_SearchNode(&(*bstNode)->lchild,e);//如果小于根節(jié)點(diǎn)的值,查找左子樹 }else { return BST_SearchNode(&(*bstNode)->rchild,e);//如果大于根節(jié)點(diǎn)的值,查找右子樹 } } /** * 遍歷BST樹節(jié)點(diǎn) */ void BST_PrintNodes(BSTNode* bstNode){ if (bstNode==NULL)//根節(jié)點(diǎn)判空 { return; } //打印根節(jié)點(diǎn)的值 printf("%d\t",(bstNode)->data); //從根節(jié)點(diǎn)開始遍歷 if (bstNode->lchild!=NULL) BST_PrintNodes((bstNode)->lchild);//遍歷左子樹 if (bstNode->rchild!=NULL) BST_PrintNodes(bstNode->rchild);//遍歷右子樹 }
測試
#include "BSTree.h" int main(int argc,char** argv){ int i; ElemType arr[]={45,24,53,45,12,24,68,25,36,96,100,25,64,78};//只有4個元素,因?yàn)殛P(guān)鍵字重復(fù)的元素不能被插入 BSTNode* bstNode=NULL; BSTNode* bstTemp=NULL; //創(chuàng)建BST樹 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); //查找結(jié)點(diǎn) bstTemp=BST_SearchNode(&bstNode,53); printf("the aimed node is %d,\n",bstNode->data); //遍歷BST樹的所有節(jié)點(diǎn) BST_PrintNodes(bstNode); printf("\n"); }
貼上測試結(jié)果如下,【插入和遍歷的節(jié)點(diǎn)數(shù)量不一致是因?yàn)?如果BST樹中的節(jié)點(diǎn)關(guān)鍵值相同,就終止插入操作】
感謝你能夠認(rèn)真閱讀完這篇文章,希望小編分享的“C語言如何實(shí)現(xiàn)BST二叉排序樹”這篇文章對大家有幫助,同時也希望大家多多支持億速云,關(guān)注億速云行業(yè)資訊頻道,更多相關(guān)知識等著你來學(xué)習(xí)!
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。