二叉查找樹性質
1、二叉樹
每個樹的節點最多有兩個子節點的樹叫做二叉樹。
2、二叉查找樹
一顆二叉查找樹是按照二叉樹的結構來組織的，并且滿足一下性質：
一個節點所有左子樹上的節點不大于蓋節點，所有右子樹的節點不小于該節點。
對查找樹的操作查詢，插入，刪除等操作的時間復雜度和樹的高度成正比， 因此，構建高效的查找樹尤為重要。
查找樹的遍歷
先序遍歷
查找樹的遍歷可以很簡單的采用遞歸的方法來實現。
struct list{ struct list *left;//左子樹 struct list *right;//右子樹 int a;//結點的值};void preorder(struct list *t)//t為根節點的指針{ if(t!=NULL) { printf("%d,",t->a); preorder(t->left); perorder(t->right); }}中序遍歷
struct list{ struct list *left;//左子樹 struct list *right;//右子樹 int a;//結點的值};void preorder(struct list *t)//t為根節點的指針{ if(t!=NULL) { preorder(t->left); printf("%d,",t->a); perorder(t->right); }}后序遍歷
struct list{ struct list *left;//左子樹 struct list *right;//右子樹 int a;//結點的值};void preorder(struct list *t)//t為根節點的指針{ if(t!=NULL) { preorder(t->left); perorder(t->right); printf("%d,",t->a); }}查找樹的搜索
給定關鍵字k，進行搜索，返回結點的指針。
struct list{ struct list *left;//左子樹 struct list *right;//右子樹 int a;//結點的值};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);};也可以用非遞歸的形式進行查找
struct list{ struct list *left;//左子樹 struct list *right;//右子樹 int a;//結點的值};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; }};最大值和最小值查詢
根據查找樹的性質，最小值在最左邊的結點，最大值的最右邊的 結點，因此，可以直接找到。
下面是最大值的例子：
{ struct list *left;//左子樹 struct list *right;//右子樹 int a;//結點的值};struct lsit *max_tree(struct lsit *t){ while(t!=NULL) { t=t->right; } return t;};查找樹的插入和刪除
插入和刪除不能破壞查找樹的性質，因此只需要根據性質，在樹中找到相應的位置就可以進行插入和刪除操作。
struct list{ struct list *left;//左子樹 struct list *right;//右子樹 int a;//結點的值};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;}感謝閱讀，希望能幫助到大家，謝謝大家對本站的支持！
新聞熱點
疑難解答
圖片精選
