天之道

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

二叉树之父子结点

Posted on 2012-10-16 23:54 hoshelly 阅读(961) 评论(0)  编辑 收藏 引用
给定一颗二叉树的逻辑结构如下图,(先序遍历的结果,空树用字符‘0’表示,例如AB0C00D00),建立该二叉树的二叉链式存储结构。

编写程序输出该树的所有叶子结点和它们的父亲结点



Input

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

第二行起,按照题目表示的输入方法,输入每个二叉树的先序遍历,连续输入t行

Output

第一行按先序遍历,输出第1个示例的叶子节点

第二行输出第1个示例中与叶子相对应的父亲节点

以此类推输出其它示例的结果

 

Sample Input

3
AB0C00D00
AB00C00
ABCD0000EF000
Sample Output

C D 
B A 
B C 
A A 
D F 
C E 


代码:

#include <iostream> 
using namespace std;

class BiTreeNode

{

private:

 BiTreeNode  *leftChild;      //左子树指针

 BiTreeNode  *rightChild;      //右子树指针

public:

 char  data;           //数据域
 char  father;


 //构造函数和析构函数

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

 BiTreeNode(char  item, char  father, BiTreeNode  *left = NULL, 

    BiTreeNode  *right = NULL):

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

 ~BiTreeNode(){}


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

  {return leftChild;}

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

  {return rightChild;}
};




class BiTree

{

private:

 BiTreeNode  *root;       //根结点指针

    int i; 

 void Destroy(BiTreeNode  * &t);
 
 void PreLeave(BiTreeNode  * &t);

 void Prefather(BiTreeNode  * &t);

 void CreateBiTree(BiTreeNode * &T,const char strTree[],char father);

public:

 //构造函数和析构函数

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

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


 
//构造二叉树

   void MakeTree(const char item,char father, BiTree  &left, BiTree  &right); //构造二叉树

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

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


 void PreLeave();  //前序遍历 
 
 void Prefather();

};

//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)

 {

 // cout << t->data << "   ";    //此语句只是为了方便测试

  delete t;

 }

}


//3、定义建树函数

void BiTree::MakeTree(const char item, char father,BiTree  &left, BiTree  &right)

//构造数据域为item,左子树为left,右子树为right的二叉树

{

 root = new BiTreeNode(item,father, left.root, right.root);

}


void BiTree::MakeTree(const char strTree[])

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

{

   i=0;
   char rootfather = '0';
   CreateBiTree(root,strTree,rootfather);

}


void BiTree::CreateBiTree(BiTreeNode * &T, const char strTree[],char father)   //递归建树私有函数

{

 char ch;

 ch=strTree[i++];

    if (ch=='0') T = NULL;

 else 

 {

  T=new BiTreeNode();

  T->data = ch;              // 生成根结点
  T->father = father;
  
  father = ch;

  CreateBiTree(T->Left(), strTree,father);   // 构造左子树

  CreateBiTree(T->Right(), strTree,father);   // 构造右子树

 } 

}

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

void BiTree::PreLeave()

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

{

 PreLeave(root);

}


void BiTree::PreLeave(BiTreeNode* &t)

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

{


  if(t)//若二叉树结点不为空,执行如下操作:
  {
      if(!t->Left() && !t->Right()) //如果当前结点是叶子
          cout<<t->data<<" ";
      PreLeave(t->Left());//2、先序遍历该结点的左孩子

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


}


//5、定义遍历父节点函数

void BiTree::Prefather()

{

 Prefather(root);

}


void BiTree:: Prefather(BiTreeNode* &t)

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

{


   if(t)//若二叉树结点不为空,执行如下操作:
   {
       if(!t->Left() && !t->Right())//如果当前结点是叶子,输出它的父亲
           cout<<t->father<<" ";
       Prefather(t->Left());
       Prefather(t->Right());

   }


}


int main(void)

{

 int n,i;

 char strTree[800];

 BiTree myTree;

 cin>>n;

 cin.get();

    for(i=0;i<n;i++)

 {

  cin>>strTree;

  myTree.MakeTree(strTree);

  myTree.PreLeave();

  cout<<endl;

  myTree.Prefather();

  cout<<endl;

  myTree.Destroy();

 }

 return 0;


}

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理