C++数据结构与算法------------二叉树的2种创建

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