二叉查找樹性質(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)建高效的查找樹尤為重要。
查找樹的遍歷
先序遍歷
查找樹的遍歷可以很簡單的采用遞歸的方法來實(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;}感謝閱讀，希望能幫助到大家，謝謝大家對(duì)本站的支持！
新聞熱點(diǎn)
疑難解答
