天之道

享受编程的乐趣。
posts - 118, comments - 7, trackbacks - 0, articles - 0
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

二叉树之数组存储

Posted on 2012-10-16 23:47 hoshelly 阅读(1275) 评论(0)  编辑 收藏 引用 所属分类: ProgrammingDS && Algorithm
二叉树可以采用数组的方法进行存储,把数组中的数据依次自上而下,自左至右存储到二叉树结点中,一般二叉树与完全二叉树对比,比完全二叉树缺少的结点就在数组中用0来表示

结点存储的数据均为非负整数

Input

第一行输入一个整数t,表示有t个二叉树

第二行起,每行输入一个数组,先输入数组长度,再输入数组内数据,每个数据之间用空格隔开,输入的数据都是非负整数

连续输入t行

Output

每行输出一个示例的先序遍历结果,每个结点之间用空格隔开

Sample Input

3
3 1 2 3
5 1 2 3 0 4
13 1 2 3 4 0 5 6 7 8 0 0 9 10
Sample Output

1 2 3 
1 2 4 3 
1 2 4 7 8 3 5 9 10 6 

分析:
这道题的关键在于:设定数组位置从1开始编号,那么位置为i的结点,它的左孩子在数组的位置是2i,右孩子在数组的位置是2i+1

这道题的难点在把树建立起来,其他都容易。

代码:

#include <iostream> 
using namespace std;

class BiTreeNode
{

private:

 BiTreeNode  *leftChild;      //左子树指针

 BiTreeNode  *rightChild;      //右子树指针

public:

 int  data;           //数据域


 
//构造函数和析构函数

 BiTreeNode():leftChild(NULL), rightChild(NULL){}

 BiTreeNode(int  item, BiTreeNode  *left = NULL, 

    BiTreeNode  *right = NULL):

    data(item), leftChild(left), rightChild(right){}

 ~BiTreeNode(){}


 BiTreeNode  * &Left(void//注意返回值类型为指针的引用类型

  {return leftChild;}

 BiTreeNode  * &Right(void//注意返回值类型为指针的引用类型

  {return rightChild;}

};




class BiTree

{

private:

 BiTreeNode  *root;       //根结点指针

    int i,len; //len是树结点的数量

 void Destroy(BiTreeNode  * &t);

 void PreOrder(BiTreeNode  * &t);

 void  CreateBiTree(BiTreeNode * &T,const int arrTree[],int pos);

public:

 //构造函数和析构函数

 BiTree(void):root(NULL),i(0){};     //构造函数

 ~BiTree(void){};        //析构函数


 
//构造二叉树

   void MakeTree(const int arrTree[],int num); //构造二叉树,利用先序遍历结果建树

   void Destroy(void);        //销毁二叉树


 void PreOrder();  //前序遍历 

};


//2、定义销毁函数

void BiTree ::Destroy(void)       //销毁二叉树,公有函数

{

 Destroy(root);

}


void BiTree ::Destroy(BiTreeNode  * &t)             

//销毁二叉树,私有函数供共有函数调用

{

 if(t != NULL && t->Left() != NULL)

  Destroy(t->Left());


 if(t != NULL && t->Right() != NULL)

  Destroy(t->Right());


 if(t != NULL)

 {
  delete t;
 }

}


//3、定义建树函数

void BiTree::MakeTree(const int arrTree[],int num)

//构造二叉树,利用先序遍历结果建树,公有函数

{

   i=0;
   len = num;

   CreateBiTree(root,arrTree,1);//数组位置从1开始

}


void BiTree::CreateBiTree(BiTreeNode * &T, const int arrTree[],int pos)   //递归建树私有函数

{

 int ch;

 ch=arrTree[pos]; 

 if (ch == 0 || pos > len) T = NULL;

 else 

 {

  T=new BiTreeNode();

  T->data = ch;              // 生成根结点
  i++;
  if(i>len) return;

  CreateBiTree(T->Left(), arrTree,2*pos);   // 构造左子树

  CreateBiTree(T->Right(), arrTree,2*pos+1);   // 构造右子树

   } 

}

//4、定义先序遍历函数

void BiTree::PreOrder()

//前序遍历访问二叉树,公有函数

{

 PreOrder(root);

}


void BiTree::PreOrder(BiTreeNode* &t)

//前序遍历访问二叉树,私有函数t

{


  if(t!=NULL)//若二叉树结点不为空,执行如下操作:
  {
      cout<<t->data<<" ";//1、输出当前结点的数据,表示该结点被访问了

      PreOrder(t->Left());//2、先序遍历该结点的左孩子

      PreOrder(t->Right());//3、先序遍历该结点的右孩子
  }


}

int main()
{
    int m,i,j,k;
    int *arrTree;
    BiTree myTree;
    cin>>m;
    for(i=0;i<m;i++)
    {
        arrTree = new int[800];
        cin>>k;
        for(j=1;j<=k;j++)
            cin>>arrTree[j];
        myTree.MakeTree(arrTree,k);
        myTree.PreOrder();
        cout<<endl;
        
        delete []arrTree;
        myTree.Destroy();
    }
    return 0;
}

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理