《数据结构》读书笔记 第六章 二叉树的三叉链表存储

今天好像大脑有点疲劳了,或者是今天写得太多了,接近400行啊~

犯了两个有意思的错误,分享一下:

(1)写查双亲节点成员函数的时候 对数据2测试怎么怎么也过不去。把parent用2种方法分别写了2次 崩溃了。然后骤然发现在之前调用了一次assign 把根结点 1–>2…….

(2)还是写这个parent的时候 居然开了个队列开始准备塞东西 然后想起来这是三叉 好像有parent指针哦……

是该歇歇了,假期《数据结构》已经啃了大半本了,修养下该开学了。这假期收获真是不少啊,呵呵。

附:测试数据:

第一次创建二叉树 1 2 4 7 0 0 0 5 0 0 3 0 6 0 0

插入用的二叉树测试 8 9 10 12 0 0 0 11 0 0 0

BiTree:二叉链表的三叉存储

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

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

class BiTree
{
public:
 BiTree();
 Go(int type);
 bool Empty();
 void Depth();
 Elem Root();
 void Assign(Elem e1,Elem e2);
 void Parent(Elem e);
 void LeftChild(Elem e);
 void RightChild(Elem e);
 void LeftSibling(Elem e);
 void InsertChild(Elem e);
 void Destroy(Elem e);
 ~BiTree();
private:
 Create(BTree &T);
 void PreOrderTraverse(BTree T);
 void InOrderTraverse(BTree T);
 void PostOrderTraverse(BTree T);
 void LevelTraverse(BTree T);
 int Depth(BTree T);
 BTree Point(Elem e);
 void Destroy(BTree T);
 BTree T;
};

BiTree::BiTree()
{
 cout<<"请按照先序顺序输入二叉树:";
 try
 {
  Create(T);
 }
 catch(int err)
 {
  if(err==-1)
   cout<<"无法在堆上完成分配节点,退出"<<endl;
 }
}

BiTree::~BiTree()
{
 Destroy(T);
 cout<<"对象被销毁"<<endl;
}

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

BiTree::Go(int type)
{
 switch(type)
 {
 case 0:
  cout<<"二叉树先序遍历:";
  PreOrderTraverse(T);
  cout<<endl;
  break;
 case 1:
  cout<<"二叉树中序遍历:";
  InOrderTraverse(T);
  cout<<endl;
  break;
 case 2:
  cout<<"二叉树后序遍历:";
  PostOrderTraverse(T);
  cout<<endl;
  break;
 case 3:
  cout<<"二叉树层序遍历:";
  LevelTraverse(T);
  cout<<endl;
  break;
 }
}

void BiTree::PreOrderTraverse(BTree T)
{
 
 if(T!=NULL)
 {
  cout<<T->data<<" ";
  PreOrderTraverse(T->lchild);
  PreOrderTraverse(T->rchild);
 }

}

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

void BiTree::PostOrderTraverse(BTree T)
{
 if(T)
 {
  PostOrderTraverse(T->lchild);
  PostOrderTraverse(T->rchild);
  cout<<T->data<<" ";
 }
}

void BiTree::LevelTraverse(BTree T)
{
 queue<BTree> Q;
 Q.push(T);
 while(!Q.empty())
 {
  BTree T1=Q.front();
  Q.pop();
  if(T1)
  {
   cout<<T1->data<<" ";
   Q.push(T1->lchild);
   Q.push(T1->rchild);
  }
 }

}

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

void BiTree::Depth()
{
 cout<<"树的深度是:"<<Depth(T)<<endl;
}

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

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

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

void BiTree::Assign(Elem e1,Elem e2)
{
 BTree T1=Point(e1);
 if(T1!=NULL)
 {
  T1->data=e2;
  cout<<"已经把"<<e1<<"修改为"<<e2<<endl;
 }
 else
  cout<<"没有找到该元素,无法修改"<<endl;
  
}

void BiTree::Parent(Elem e)
{
 BTree T1=Point(e);
 if(T1)
 {
  if(T1->parent)
   cout<<e<<"的双亲节点是"<<T1->parent->data<<endl;
  else
   cout<<e<<"的双亲节点不存在"<<endl;
 }
 else
  cout<<e<<"的双亲节点不存在"<<endl;
}

void BiTree::LeftChild(Elem e)
{
 BTree T1=Point(e);
 if(T1)
 {
 if(T1->lchild)
 {
  cout<<e<<"的左孩子节点是"<<T1->rchild->data<<endl;
  return ;
 }
 }
 else
  cout<<e<<"的左孩子节点不存在"<<endl;
}

void BiTree::RightChild(Elem e)
{
 BTree T1=Point(e);
 if(T1)
 {
 if(T1->rchild)
 {
  cout<<e<<"的右孩子节点是"<<T1->rchild->data<<endl;
  return ;
 }
 }
 else
 cout<<e<<"的右孩子节点不存在"<<endl;
}

void BiTree::LeftSibling(Elem e)
{
 BTree T1;
 T1=Point(e);
 if(T1)
 {
  if(T1->parent->rchild&&T1->parent->rchild->data==e&&T1->parent->lchild)
   cout<<e<<"的左兄弟节点是:"<<T1->parent->lchild->data<<endl;
  else
   cout<<e<<"是独苗哦,没有左兄弟节点"<<endl;
 }
 else
  cout<<"无法找到"<<e<<endl;
}

void BiTree::InsertChild(Elem e)
{
 BTree T1=Point(e);
 if(T1)
 {
  cout<<"先创建一个新树,按照先序输入:";
  BTree Tmp;
  Create(Tmp);

  Tmp->rchild=T1->rchild;
  T1->rchild=Tmp;
  Tmp->parent=T1;
 }
 else
  cout<<"无法找到"<<e<<endl;

}

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

void BiTree::Destroy(Elem e)
{
 BTree T1=Point(e);
 if(T1)
 {
  cout<<"正在删除"<<e<<"及其节点";
  if(T1->parent->lchild->data==e)
   T1->parent->lchild=NULL;
  if(T1->parent->rchild->data==e)
   T1->parent->rchild=NULL;
  Destroy(T1);
  
 }
}

main.cpp:主程序+测试

#include "BiTree.h"

int main()
{
 BiTree T;
 
 T.Depth();
 //T.Assign(1,2);
 
 cout<<"树的根是:"<<T.Root()<<endl;
 T.RightChild(3);
 T.LeftSibling(5);
 T.InsertChild(2);
 T.Parent(8);
 T.Destroy(8);
 T.Go(3);
 return 0;
}

 

Leave a Reply

Your email address will not be published.