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

1、以数组为存储结构的二叉树     模板+完全二叉树(适合完全二叉树存储)

/*

二叉树的线性存储  ..用数组  作为存储结构 ,需要对二叉树 按照层次进行编号  。适合完全二叉树和满二叉树。

编号就是二叉树数组的值 

这里的节点要按照层次 为二叉树的每个节点编号  

如果节点编号为i  那么父节点   i/2 

子节点  2i   2i+1 

我们在这里操作以数组存储的完全二叉树 就要了解二叉树的概念。

*/

template<class T>

void Array_Tree<T>::GetNodeIndexByValue(T val) //通过值返回节点索引

{

for(int i=1;i<=nCount;i++)

if(val==pRoot[i])

cout<<i<<endl ;

}

void Array_Tree<T>::OutputTree() //显示二叉树 nCount结点个数

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 ;

else

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;