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

今天好像大脑有点疲劳了，或者是今天写得太多了，接近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;
}

四号程序员

Keep It Simple and Stupid

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

Leave a Reply Cancel reply