《数据结构》读书笔记 第六章 二叉树的二叉链表实现

没想到真的能写出来,因为这是第一次用类的方式封装描述。真的是第一次写类。而且加上二叉树这个比较难描述的东东,确实费了不少劲。发现面向对象确实是很好的。真的是让用户无需关心数据细节。当然可能是还没习惯,写得有点慢。

期间,递归的不熟练导致犯下了几次严重错误,好在自己都纠正了。

但是还有以下没有解决:

1、如何在类中调用函数指针?

2、Parent函数能不能用递归描述?

若有高手看到指点一二,不胜感激~ 微笑 

BiTree.h:定义了二叉类 BiTree以及基本操作

#include <iostream>
#include <queue>
using namespace std;

typedef int Elem;
typedef struct TNode
{
 TNode *lchild,*rchild;
 Elem data;
}BTreeNode,*BTree;

void print(Elem e)
{
 cout << e << ' ';
}

class BiTree
{
public:
 BiTree();
 void Go(int type);
 bool Empty();
 void Destroy();
 Elem Root();
 int Depth();
 Elem Parent(Elem e);
 Elem LeftChild(Elem e);
 Elem RightChild(Elem e);
 Elem LeftSibling(Elem e);
 ~BiTree(){}

private:
 BTree T;
 void Create(BTree &T);
 void InOrderTraverse(BTree &T);
 void del(BTree &T);
 BTree Point(BTree T,Elem e);
 int GetDepth(BTree T);
};

BiTree::BiTree()
{
 cout<<"下面创建二叉树,请安先序输入节点,0为结束:";
 try
 {
 Create(T);
 }
 catch(int err)
 {
  if(err==-1)
  {
   cout<<"无法分配内存."<<endl;

  }
 }

}
void BiTree::Create(BTree &T)
{
 Elem e;
 cin>>e;
 if(e)
 {
  T=new BTreeNode;
  if(T==NULL)
   throw -1;
  T->data=e;
  Create(T->lchild);
  Create(T->rchild);
 }
 else
  T=NULL;
}

void  BiTree::InOrderTraverse(BTree &T)
{
 if(T!=NULL)
 {
  InOrderTraverse(T->lchild);
  print(T->data);
  InOrderTraverse(T->rchild);
 }
}

 

void BiTree::Go(int type)
{
 switch(type)
 {
 case 0:
  cout<<"中序遍历树:";
  InOrderTraverse(T);
  cout<<endl;
  break;
 }
}

bool BiTree::Empty()
{
 return T==NULL;
}

void BiTree::del(BTree &T)
{
 if(T!=NULL)
 {
  del(T->lchild);
  del(T->rchild);
  delete T;
  T=NULL;
 }
}

void BiTree::Destroy()
{
 cout<<"清空二叉树…";
 del(T);
 cout<<"完毕"<<endl;
}

Elem BiTree::Root()
{
 if(T!=NULL)
  return T->data;
 else
  return 0;
}

Elem BiTree::Parent(Elem e)
{
 queue<BTree> Q;
 Q.push(T);
 while(!Q.empty())
 {
  BTree TQ=Q.front();
  Q.pop();
  if(TQ->lchild!=NULL&&TQ->lchild->data==e||TQ->rchild!=NULL&&TQ->rchild->data==e)
   return TQ->data;
  if(TQ->lchild!=NULL)
   Q.push(TQ->lchild);
  if(TQ->rchild!=NULL)
   Q.push(TQ->rchild);
 }
 return 0;
}

BTree BiTree::Point(BTree T,Elem e)
{
 queue<BTree> Q;
 BTree TQ;
 Q.push(T);
 while(!Q.empty())
 {
  TQ=Q.front();
  Q.pop();
  if(TQ->data==e)
   return TQ;
  if(TQ->lchild!=NULL)
   Q.push(TQ->lchild);
  if(TQ->rchild!=NULL)
   Q.push(TQ->rchild);
 }
 return NULL;
}

Elem BiTree::LeftChild(Elem e)
{
 BTree p;
 p=Point(T,e);
 if(p->lchild!=NULL)
  return p->lchild->data;
 else
  return 0;
}

Elem BiTree::RightChild(Elem e)
{
 BTree p;
 p=Point(T,e);
 if(p->rchild!=NULL)
  return p->rchild->data;
 else
  return 0;
}

Elem BiTree::LeftSibling(Elem e)
{
 BTree p=Point(T,Parent(e));
 if(p==NULL)
  return 0;
 else
 {
  if(p->rchild!=NULL && p->lchild!=NULL && p->rchild->data==e)
   return p->lchild->data;
 }
 return 0;
}

int BiTree::Depth()
{
 return GetDepth(T);
}

int BiTree::GetDepth(BTree T)
{
 int i=0,j=0;
 if(T!=NULL)
 {
  if(T->lchild!=NULL)
   i=GetDepth(T->lchild);
  if(T->rchild!=NULL)
   j=GetDepth(T->rchild);
  return i>j?i+1:j+1;
 }
 else
  return 0;
}

main.cpp:主程序+测试

#include "BiTree.h"

int main()
{
 BiTree T;
 T.Go(0);
 cout<<"二叉树是否为空:"<<T.Empty()<<endl;
 cout<<"根植:"<<T.Root()<<endl;
 cout<<"3的双亲节点是:"<<T.Parent(3)<<endl;
 cout<<"2的右孩子节点是:"<<T.RightChild(2)<<endl;
 cout<<"5的左兄弟节点是"<<T.LeftSibling(5)<<endl;
 cout<<"深度:"<<T.Depth()<<endl;
 //T.Destroy();
 //cout<<"二叉树是否为空:"<<T.Empty()<<endl;
 return 0;
}

Leave a Reply

Your email address will not be published.