~~~ #include "stdio.h" typedef struct node { int data ; node*lChild ; node*rChild ; }TreeNode ; void Insert(TreeNode**root,int data) //向二叉查找樹中插入元素 采用非遞歸思想 { TreeNode * p=*root ;//獲得根結點 TreeNode*q=new TreeNode ;//分配一個要插入的新節點 q->lChild=q->rChild=NULL ; //新分配節點的左節點=右節點等于NULL q->data=data ; //保存數據到節點 TreeNode *parent =p ; //用于保存父節點 while(p!=NULL) //循環搜索節點 { parent=p ; //首先parent指向root節點 if(p->data>data) //如果節點數據大于當前節點 p=p->lChild ;//如果插入數據小于 節點數據那么指向左節點 我么最終是要找到一個NULL節點 else p=p->rChild ; } //如果因為parent總是指向NULL節點的父節點 ,所以parent指向的節點不會為空,如果為空那么說明該樹是一顆空的樹。 if(parent==NULL) *root=q ; //將分配的節點作為根節點 else if(parent->data>data) parent->lChild=q ; //<root左插 else parent->rChild=q ; //>root右插 } void InOrder(TreeNode*root) { if(root!=NULL) { InOrder(root->lChild) ; printf("%d",root->data) ; InOrder(root->rChild) ; } } bool Find(TreeNode*root,int fData) //非遞歸方法查詢 { if(root==NULL) return false ; //搜索樹為空返回false while(root!=NULL) { if(root->data==fData) return true ; if(root->data>fData) root=root->lChild ; else root=root->rChild ; } return false ; } int main(int argc,char*argv[]) { TreeNode *root=NULL; //如果根節點指針在局部那么一定要初始化NULL否則程序崩潰 ,如果我們的指針是在全局定義的可以不初始化NULL全局變量放在靜態存儲區 int a[]={2,3,6,8,0,9,3,1,5,7} ; for(int i=0;i<10;i++) Insert(&root,a[i]) ; InOrder(root) ; printf("\n") ; if(Find(root,0)) printf("數據0找到\n") ; else printf("沒有0數據\n") ; return 1 ; } ~~~ 二叉搜索樹又稱二叉查找樹? , 他有這樣的特點,根節點 的數據比他的左子樹大.? 比右節點小 ,中序遍歷可以得到一棵升序的 序列 。 二叉搜索樹可以采用遞歸和非遞歸方式建立 ,由于遞歸消耗內存較大 ,所以采用非遞歸方式 。