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; }