您好,登錄后才能下訂單哦!
本文小編為大家詳細(xì)介紹“C語(yǔ)言中二叉查找樹怎么實(shí)現(xiàn)”,內(nèi)容詳細(xì),步驟清晰,細(xì)節(jié)處理妥當(dāng),希望這篇“C語(yǔ)言中二叉查找樹怎么實(shí)現(xiàn)”文章能幫助大家解決疑惑,下面跟著小編的思路慢慢深入,一起來學(xué)習(xí)新知識(shí)吧。
二叉查找樹性質(zhì)
1、二叉樹
每個(gè)樹的節(jié)點(diǎn)最多有兩個(gè)子節(jié)點(diǎn)的樹叫做二叉樹。
2、二叉查找樹
一顆二叉查找樹是按照二叉樹的結(jié)構(gòu)來組織的,并且滿足一下性質(zhì):
一個(gè)節(jié)點(diǎn)所有左子樹上的節(jié)點(diǎn)不大于蓋節(jié)點(diǎn),所有右子樹的節(jié)點(diǎn)不小于該節(jié)點(diǎn)。
對(duì)查找樹的操作查詢,插入,刪除等操作的時(shí)間復(fù)雜度和樹的高度成正比, 因此,構(gòu)建高效的查找樹尤為重要。
查找樹的遍歷
先序遍歷
查找樹的遍歷可以很簡(jiǎn)單的采用遞歸的方法來實(shí)現(xiàn)。
struct list { struct list *left;//左子樹 struct list *right;//右子樹 int a;//結(jié)點(diǎn)的值 }; void preorder(struct list *t)//t為根節(jié)點(diǎn)的指針 { if(t!=NULL) { printf("%d,",t->a); preorder(t->left); perorder(t->right); } }
中序遍歷
struct list { struct list *left;//左子樹 struct list *right;//右子樹 int a;//結(jié)點(diǎn)的值 }; void preorder(struct list *t)//t為根節(jié)點(diǎn)的指針 { if(t!=NULL) { preorder(t->left); printf("%d,",t->a); perorder(t->right); } }
后序遍歷
struct list { struct list *left;//左子樹 struct list *right;//右子樹 int a;//結(jié)點(diǎn)的值 }; void preorder(struct list *t)//t為根節(jié)點(diǎn)的指針 { if(t!=NULL) { preorder(t->left); perorder(t->right); printf("%d,",t->a); } }
查找樹的搜索
給定關(guān)鍵字k,進(jìn)行搜索,返回結(jié)點(diǎn)的指針。
struct list { struct list *left;//左子樹 struct list *right;//右子樹 int a;//結(jié)點(diǎn)的值 }; struct list * search(struct list *t,int k) { if(t==NULL||t->a==k) return t; if(t->a<k) search(t->right); else search(t>left); };
也可以用非遞歸的形式進(jìn)行查找
struct list { struct list *left;//左子樹 struct list *right;//右子樹 int a;//結(jié)點(diǎn)的值 }; struct list * search(struct list *t,int k) { while(true) { if(t==NULL||t->a==k) { return t; break; } if(t->a<k) t=t->rigth; else t=t->left; } };
最大值和最小值查詢
根據(jù)查找樹的性質(zhì),最小值在最左邊的結(jié)點(diǎn),最大值的最右邊的 結(jié)點(diǎn),因此,可以直接找到。
下面是最大值的例子:
{ struct list *left;//左子樹 struct list *right;//右子樹 int a;//結(jié)點(diǎn)的值 }; struct lsit *max_tree(struct lsit *t) { while(t!=NULL) { t=t->right; } return t; };
查找樹的插入和刪除
插入和刪除不能破壞查找樹的性質(zhì),因此只需要根據(jù)性質(zhì),在樹中找到相應(yīng)的位置就可以進(jìn)行插入和刪除操作。
struct list { struct list *left;//左子樹 struct list *right;//右子樹 int a;//結(jié)點(diǎn)的值 }; void insert(struct list *root,struct list * k) { struct list *y,*x; x=root; while(x!=NULL) { y=x; if(k->a<x->a) { x=x->left; } else x=x->right; } if(y==NULL) root=k; else if(k->a<y->a) y->left=k; else y->right=k; }
讀到這里,這篇“C語(yǔ)言中二叉查找樹怎么實(shí)現(xiàn)”文章已經(jīng)介紹完畢,想要掌握這篇文章的知識(shí)點(diǎn)還需要大家自己動(dòng)手實(shí)踐使用過才能領(lǐng)會(huì),如果想了解更多相關(guān)內(nèi)容的文章,歡迎關(guān)注億速云行業(yè)資訊頻道。
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。