1、以數組為存儲結構的二叉樹???? 模板+完全二叉樹(適合完全二叉樹存儲) /* 二叉樹的線性存儲? ..用數組? 作為存儲結構 ,需要對二叉樹 按照層次進行編號? 。適合完全二叉樹和滿二叉樹。 編號就是二叉樹數組的值? 這里的節點要按照層次 為二叉樹的每個節點編號?? 如果節點編號為i? 那么父節點?? i/2? 子節點? 2i?? 2i+1? 我們在這里操作以數組存儲的完全二叉樹 就要了解二叉樹的概念。 */ ~~~ #include <iostream> using namespace std ; template <class T> class Array_Tree { public : Array_Tree() ; ~Array_Tree(); void GetNodeValueByIndex(int index) ;//返回指定節點的值; void GetNodeIndexByValue(T val) ;//通過值返回節點索引 void OutputTree() ; void CreateTree() ; //返回樹根節點指針 private : T *pRoot ; int nCount ; }; template<class T> Array_Tree<T>::Array_Tree() { this->nCount= 0; this->pRoot=NULL ; } template<class T> Array_Tree<T>:: ~Array_Tree() { delete []this->pRoot ; } template<class T> void Array_Tree<T>::CreateTree() //返回樹根節點指針 { T *pRoot=NULL ; //數組指針 int count; //二叉樹節點個數 cout<<"輸入二叉樹節點的個數:"<<endl ; cin>>count ; //輸入結點個數 pRoot=new T[count+1] ;//分配存儲空間也可以是用malloc this->pRoot=pRoot; this->nCount=count ; for(int i=1;i<=count;i++) { cin>>pRoot[i] ;//輸入每個節點的數據 } } template<class T> void Array_Tree<T>::GetNodeValueByIndex(int index)//返回指定節點的值 { return this->pRoot[index] ; }template<class T> void Array_Tree<T>::GetNodeIndexByValue(T val) //通過值返回節點索引 { for(int i=1;i<=nCount;i++) { if(val==pRoot[i]) { cout<<i<<endl ; } } } template<class T> void Array_Tree<T>::OutputTree() //顯示二叉樹 nCount結點個數 { for(int i=1;i<=nCount;i++) { if(2*i<=nCount&&2*i+1<=nCount) { if(1==i) //如果是根節點 { cout<<"Root1:"<<pRoot[1]<<endl ; cout<<"無雙親節點"<<endl ; cout<<"lChild:"<<pRoot[i*2]<<"\t"<<"rChild:"<<pRoot[i*2+1]<<endl<<endl ; continue ; } cout<<"節點"<<i<<":"<<pRoot[i]<<endl ; cout<<"雙親節點:"<<pRoot[i/2]<<endl ; cout<<"lChild:"<<pRoot[i*2]<<"\t"<<"rChild:"<<pRoot[i*2+1]<<endl<<endl ; } else { cout<<"節點"<<i<<":"<<pRoot[i]<<endl ; cout<<"雙親節點:"<<pRoot[i/2]<<endl ; cout<<"無孩子節點"<<endl<<endl ; } } } void main() { Array_Tree<char> tree ; tree.CreateTree() ; tree.GetNodeIndexByValue('a') ; tree.OutputTree() ; } ~~~ 2、以鏈表為存儲結構建立二叉鏈表 /* 二叉鏈表就是以鏈表為存儲結構存儲二叉樹 ,我么要像編號 完全二叉樹一樣 存儲 普通的二叉樹 。 節點的聲明如下 node???? */ #include <iostream> using namespace std ; typedef struct node {? int data ; node* lChild ; node* rChild ; }BTreeNode,*LinkTree ;?? void CreateTree(LinkTree*pTree,int nIndex[],char ch[])?? //nIndex是二叉樹的節點編號數組? ch是節點數據 每個編號對應一個字符? nIndex 等于0時候結束?? ch='#'結束 {? int?? i =1 ;//用作下標? int?? j ;//當前雙親節點的下標? LinkTree temNode[50] ;//輔助建立二叉鏈表 BTreeNode *newNode =NULL;//用來指向新分配的節點空間 while(nIndex[i]!=0&&ch[i]!='#')? //如果沒有到達最后一個節點 { ?newNode=new BTreeNode ; ?newNode->data=ch[i]? ;? //為節點賦值 ?newNode->lChild=newNode->rChild=NULL ;//lChild=rChild=NULL ?temNode[nIndex[i]]=newNode ;//將這個新節點保存在輔助節點數組的指定編號為下標的元素中。 ?if(nIndex[i]==1)? //如果是根節點的話那么我們將這個節點的地址保存在pTree中。 ?{ ??*pTree=newNode? ; ?} ?else ?{??? ???????? j=nIndex[i]/2 ;//獲得雙親節點的編號 也就是數組下標 、 ?? if(nIndex[i]%2==0)??? ??? temNode[j]->lChild=newNode ;? //編號基數那么是左子樹 ?? else ??? temNode[j]->rChild=newNode ;? //編號是偶數那么是右子樹 ?} ?i++ ;?? //索引自加1 } } void main() { ?? LinkTree pTree ; ?? int? nIndex[]={9999,1,2,3,4,5,6,0} ; ????? char ch[]={'?',1,5,3,5,8,9,'#'}; ?? CreateTree(&pTree,nIndex,ch);? ?? cout<<pTree->rChild->lChild->data; }