treem.txt

一本数据结构的经典书籍-数据结构算法程序集里

//树的孩子兄弟表示法为存储结构的结构体Tree.h
template<class T> class Tree;
template<class T> struct TreeNode
{friend class Tree<T>;//树类为友元
 private:
  TreeNode<T> *firstChild;//第一个孩子结点指针域
  TreeNode<T> *nextSibling;//下一个兄弟结点指针域
 public:
  T data;//数据域
//构造函数
  TreeNode(T value,TreeNode<T> *fc=NULL,
    TreeNode<T> *ns=NULL):data(value),
     firstChild(fc),nextSibling(ns){}
//访问指针域的成员函数
  TreeNode<T>* &FirstChild()
   {return firstChild;}
  TreeNode<T>* &NextSibling()
   {return nextSibling;}
};
//树类
template<class T> class Tree
{private:
  TreeNode<T> *root;//根结点指针
  TreeNode<T> *curr;//当前结点指针
  //显示以t为先根结点的树的数据域
  void PreOrderTree(TreeNode<T> *&t);
  //显示以t为后根结点的树的数据域
  void PosOrderTree(TreeNode<T> *&t);
  //使当前结点为t所指结点
  int Current(TreeNode<T> *&t);
  //在树root中回溯查找结点s的双亲结点
  TreeNode<T> *SearchParent(TreeNode<T> *&root,TreeNode<T> *&s);
 public:
  //构造函数与析构函数
  Tree(){root=curr=NULL;}
  ~Tree(){DeleteSubTree(root);}
  //使根结点为当前结点
  int Root();
  //使当前结点的双亲结点为当前结点
  int Parent();
  //使当前结点的第一个孩子结点为当前结点
  int FirstChild();
  //使当前结点的兄弟结点为当前结点
  int NextSibling();
  //把valve插入到当前结点的最后一个结点
  void InsertChild(T value);
  //删除以t为根结点的子树
  void DeleteSubTree(TreeNode<T> *&t);
  //删除当前结点的第i个孩子结点
  int DeleteChild(int i);
  //删除以root为根结点的子树的第i个孩子结点
  int DeleteChild1(int i);
  //按先根遍历次序显示树的数据域值
  void DisplayTree();
  //按后根遍历次序显示树的数据域值
  void DisplayTree1();
};
//树类的实现Tree.cpp
template<class T>
void Tree<T>::DeleteSubTree(TreeNode<T> *&t)
{if(t==NULL) return;
 TreeNode<T> *q=t->firstChild,*p;
 while(q!=NULL)
 {p=q->nextSibling;
  DeleteSubTree(q);
  q=p;}
  cout<<"释放:"<<setw(2)<<t->data;
  delete t;
}
template<class T>
int Tree<T>::Current(TreeNode<T> *&t)
{if(t==NULL) return 0;
 curr=t;
 return 1;
}
template<class T>
int Tree<T>::Root()
{if(root==NULL)
  {curr=NULL;
   return 0;}
 return Current(root);
}
template<class T>
int Tree<T>::FirstChild()
{if(curr!=NULL&&curr->firstChild!=NULL)
  return Current(curr->firstChild);
 else return 0;
}
template<class T>
int Tree<T>::NextSibling()
{if(curr!=NULL&&curr->nextSibling!=NULL)
  return Current(curr->nextSibling);
 else return 0;
}
template<class T>
int Tree<T>::Parent()
{if(curr==NULL)
  {curr=root;
   return 0;}
 TreeNode<T> *p=SearchParent(root,curr);
 if(p==NULL) return 0;
 else return Current(p);
}
template<class T>
TreeNode<T> *Tree<T>::SearchParent(TreeNode<T> *&root,TreeNode<T> *&s)
{if(root==NULL) return NULL;
 if(root->FirstChild()==s||root->NextSibling()==s)
  return root;
 TreeNode<T> *p;
 if((p=SearchParent(root->FirstChild(),s))!=NULL) return p;
 if((p=SearchParent(root->NextSibling(),s))!=NULL) return p;
 return NULL;
}
template<class T>
void Tree<T>::InsertChild(T value)
{TreeNode<T> *newNode=new TreeNode<T> (value);
 if(root==NULL)  //当为空树时
  {root=curr=newNode;
   return;}
 if(curr->firstChild==NULL)//当当前结点无孩子时
  curr->firstChild=newNode;
 else                     //当当前结点有孩子时
  {TreeNode<T> *p=curr->firstChild;
   while(p->nextSibling!=NULL) p=p->nextSibling;
   p->nextSibling=newNode;
  }
  Current(newNode);//使新建立的结点成为当前结点
}      
template<class T>
int Tree<T>::DeleteChild(int i)
{TreeNode<T> *r=NULL;
 if(i==1)         //当删除当前结点的第一棵子树时
 {r=curr->firstChild;
  if(r==NULL) return 0;//要删除子树为空时返回
  curr->firstChild=r->nextSibling;//脱链要删除的子树
 }
 else {          //当删除当前结点的其他子树时
  int k=1;
  TreeNode<T> *p=curr->firstChild;
  while(p!=NULL&&k<=i-1)//寻找要删除子树的指针
  {p=p->nextSibling;
   k++;}
  if(p!=NULL)//寻找到要删除的子树的指针
  {r=p->nextSibling;
   if(r!=NULL)
    p->nextSibling=r->nextSibling;
   else return 0;
  }
  else return 0;
 }
 DeleteSubTree(r);
 return 1;
}
template<class T>
int Tree<T>::DeleteChild1(int i)
{if(root==NULL) return 0;//当为空树时
 TreeNode<T> *r=NULL,*q=root->firstChild;
 if(i==1&&q!=NULL) //当第一结点有孩子时
  {r=root->firstChild;
   root->firstChild=r->nextSibling;//脱链要删除的子树
  }
 else             //要删除第一结点外的其他子树时
  {int k=1;
   TreeNode<T> *p=root->firstChild;
   while(p!=NULL&&k<=i-1)//寻找要删除子树的指针
   {p=p->nextSibling;
    k++;
   }
  if(p!=NULL)    //寻找到要删除的子树的指针
   {r=p->nextSibling;
    if(r!=NULL)
     p->nextSibling=r->nextSibling;//脱链要删除的子树
    else return 0;}
  else return 0;
 }
 DeleteSubTree(r);//调用函数执行删除
 return 1;    
}
template<class T>
void Tree<T>::PreOrderTree(TreeNode<T> *&t)
{if(t==NULL) return;
 cout<<setw(2)<<t->data;//显示根结点数据
 if(t->firstChild!=NULL)//先根遍历子树
  PreOrderTree(t->firstChild);
 if(t->nextSibling!=NULL)
  PreOrderTree(t->nextSibling);
}
template<class T>
void Tree<T>::DisplayTree()
{PreOrderTree(root);}

template<class T>
void Tree<T>::DisplayTree1()
{PosOrderTree(root);}

template<class T>
void Tree<T>::PosOrderTree(TreeNode<T> *&t)
{if(t==NULL) return;
 if(t->firstChild!=NULL)//后根遍历子树
  PosOrderTree(t->firstChild);
 cout<<setw(2)<<t->data;//显示根结点数据
 if(t->nextSibling!=NULL)
  PosOrderTree(t->nextSibling);
}
//树类相关操作的测试TreeM.cpp
#include<iostream.h>
#include<iomanip.h>
#include<stdlib.h>
#include<conio.h>
#include "Tree.h"
#include "Tree.cpp"
void main()
{cout<<"TreeM.cpp运行结果:\n";
 int i;
 Tree<char> t;
 t.InsertChild('A');
 for(i=0;i<7;i++)
 {t.Root();
  if(i>=3&&i<5) t.FirstChild();
  t.InsertChild('B'+i);
 }
 cout<<"按后根遍历显示的结点次序为:\n";
 t.DisplayTree1();
 int k;
 cout<<"\n输入欲删除第几个结点(k):";cin>>k;
 if(t.DeleteChild1(k))
   cout<<"\n第"<<k<<"个孩子结点,删除成功!\n";
 else cout<<"\n第"<<k<<"个孩子结点,删除失败!\n";
 cout<<"按先根遍历显示的结点次序为:\n";
 t.DisplayTree();
 getch();
 cout<<endl<<"析构函数按后根遍历释放结点的次序为:\n";}
TreeM.cpp运行结果:
按后根遍历显示的结点次序为:
 E F B C D G H A
输入欲删除第几个结点(k):1
释放: E释放: F释放: B
第1个孩子结点,删除成功!
按先根遍历显示的结点次序为:
 A C D G H
析构函数按后根遍历释放结点的次序为:
释放: C释放: D释放: G释放: H释放: A

TreeM.cpp运行结果:
按后根遍历显示的结点次序为:
 E F B C D G H A
输入欲删除第几个结点(k):3
释放: G
第3个孩子结点,删除成功!
按先根遍历显示的结点次序为:
 A B E F C D H
析构函数按后根遍历释放结点的次序为:
释放: E释放: F释放: B释放: C释放: D释放: H释放: A