靓女.cpp

包括建立输出前序遍历中序遍历后序遍历、求树高统计叶子总数等

#include<iostream>
#include"zz.h"
#include<queue>
using namespace std;

class BLinkTree//  定义单向链表类
{
public:
BTreeNode *head;
int NodeNum;//结点总数
int total;//叶子总数
public:
BLinkTree();// 定义构造函数
~BLinkTree();//析构函数
BTreeNode* Creat(int first);
void PreOrder1(BTreeNode*t,int first);//前序遍历递归算法
void PreOrder2();//前序遍历非递归算法
void InOrder1(BTreeNode*t,int first);//中序遍历递归算法
void InOrder2();//中序遍历非递归算法
void PostOrder1(BTreeNode*t,int first);//后序遍历递归算法
void PostOrder2();//后序遍历非递归算法
void PrintLayerOrder();//层次输出树
int Depth(BTreeNode*t,int first);//求树高
void YeZiTotal(BTreeNode*t,int first);//求叶子总数
};
//////////////////////////////////////////////////////////////////////////////
//  构造函数
//  函数功能：建立一棵二叉树
//函数参数：无
//参数返回值：无
BLinkTree::BLinkTree()
{
head=NULL;
total=NodeNum=0;
}
//////////////////////////////////////////////////////////////////////////////
// 析构函数
// 函数功能：将二叉树所有节点的空间释放
//函数参数：无
//参数返回值：无
BLinkTree::~BLinkTree()
{
stack s=stack(NodeNum);
BTreeNode*current;
current=head;
s.push(current);
while(!s.empty())
{
  current=s.pop();
  
  if(current->lchild!=NULL)s.push(current->lchild);
  if(current->rchild!=NULL)s.push(current->rchild);
  delete current;
}
}
//////////////////////////////////////////////////////////////////////////////
//  建树函数
//  函数功能：建立一棵二叉树
//函数参数：
//         first:如果是第一次，进行初始化  
//参数返回值：指向树节点结构的指针
BTreeNode* BLinkTree::Creat(int first)
{
BTreeNode*current;
char ch;
cin>>ch;
if(ch=='.')current=NULL;
else
{
  current=new BTreeNode;
  current->data=ch;
  if(first)
  {
   head=current;
   first=0;
  }
  NodeNum++;
  current->lchild=Creat(first);
  current->rchild=Creat(first);
}
return current;
}
//////////////////////////////////////////////////////////////////////////////
//  前序遍历递归函数
//  函数功能：用递归按根左右的顺序遍历二叉树
//  函数参数：
//        t:当前的节点
//        first:如果是第一次，进行初始化        
//  参数返回值：无   
void BLinkTree::PreOrder1(BTreeNode*t,int first)
{
BTreeNode*current;
if(first)
{
  current=head;
  first=0;
}
else current=t;
if(current!=NULL)
{
  cout<<current->data;
  PreOrder1(current->lchild,first);
  PreOrder1(current->rchild,first);
}
}
//////////////////////////////////////////////////////////////////////////////
//  前序遍历非递归函数
//  函数功能：按根左右的顺序遍历二叉树
//函数参数：没有
//       
//参数返回值：没有
  
void BLinkTree::PreOrder2()
{
BTreeNode* current;
stack s=stack(NodeNum);
current=head;
s.push(current);

while(!s.empty())
{
  current=s.pop();
 
  cout<<current->data;
  
  if(current->rchild!=NULL)
  s.push(current->rchild);
  if(current->lchild!=NULL)
   s.push(current->lchild);
}
}
//////////////////////////////////////////////////////////////////////////////
//  中序遍历递归函数
//  函数功能：用递归按左根右的顺序遍历二叉树
//  函数参数：
//          t:当前的节点
//          first:如果是第一次，进行初始化
//  参数返回值：无
void BLinkTree::InOrder1(BTreeNode*t,int first)
{
BTreeNode* current;
if(first)
{
  current=head;
  first=0;
}
else current=t;
if(current!=NULL)
{
  InOrder1(current->lchild,first);
  cout<<current->data;
  InOrder1(current->rchild,first);
}
}
//////////////////////////////////////////////////////////////////////////////
//中序遍历非递归算法函数
//函数功能:按左根右的顺序遍历二叉树
//函数参数:无
//参数返回值:无
void BLinkTree::InOrder2()
{
BTreeNode*current;
stack s=stack(NodeNum);
current=head;
while(!s.empty()||current!=NULL)
{
  while(current!=NULL)
  {
   s.push(current);
   current=current->lchild;
  }
  if(!s.empty()){
   current=s.pop();
  
   cout<<current->data;
   current=current->rchild;
  }
}
}
//////////////////////////////////////////////////////////////////////////////
//   后序遍历递归算法函数
//  函数功能：用递归按左右根的顺序遍历二叉树
//函数参数：
//        t:当前的节点
//        first:如果是第一次，进行初始化
//参数返回值：无
void BLinkTree::PostOrder1(BTreeNode*t,int first)
{
BTreeNode*current;

if(first)
{
  current=head;
  first=0;
}
else current=t;
if(current!=NULL)
{
  PostOrder1(current->lchild,first);
  PostOrder1(current->rchild,first);
  cout<<current->data;
}
}
//////////////////////////////////////////////////////////////////////////////
//后序遍历非递归算法函数函数
//函数功能:按左右根的顺序遍历二叉树
//函数参数:无
//参数返回值:无
void BLinkTree::PostOrder2()
{
BTreeNode*current;
int flag;
stack s1=stack(NodeNum);
stack1 s2=stack1(NodeNum);
current=head;
while(!s1.empty()||current!=NULL)
{
  while(current!=NULL)
  {
   s1.push(current);
   s2.push(0);
   current=current->lchild;
  }
  if(!s1.empty())
  {
   current=s1.pop();
   
   flag=s2.pop();
  
   if(flag==1)
   {
    cout<<current->data;
    current=NULL;
   }
      else
   {
    s1.push(current);
    s2.push(1);
    current=current->rchild;
   }
  }
}
}
//////////////////////////////////////////////////////////////////////////////////
//层次遍历树的结点的函数
//函数功能：输出数的结点 按照层次的关系输出
//函数参数：无
//函数返回值：无
void BLinkTree::PrintLayerOrder()
{
BTreeNode*current;
queue<BTreeNode*>q;
if(head!=NULL)
  q.push(head);
while(!q.empty())
{
  current=q.front();
  q.pop();
  cout<<current->data;
  if(current->lchild!=NULL) 
   q.push(current->lchild);
  if(current->rchild!=NULL)
   q.push(current->rchild);
}
}
//////////////////////////////////////////////////////////////////////////////
// 求树高函数
//函数功能:求出树的高度
//函数参数:
//        t:当前的节点
//        first:如果是第一次，进行初始化
//参数返回值:
//        pHigh:树的高度
int BLinkTree::Depth(BTreeNode*t,int first)
{
int currentDepth,lDepth,rDepth;
BTreeNode*current;
if(first)
{
  current=head;
  first=0;
}
else current=t;
if(current==NULL)
  currentDepth=0;
else
{
  lDepth=Depth(current->lchild,first);
  rDepth=Depth(current->rchild,first);
  if(lDepth>rDepth)
   currentDepth=lDepth+1;
  else
   currentDepth=rDepth+1;
}
return (currentDepth);
}
//////////////////////////////////////////////////////////////////////////////
//  求叶子总数函数
//  函数功能：求出树的叶子的总数
//函数参数：
//        t:当前的节点
//        first:如果是第一次，进行初始化
//参数返回值：无
//          
void BLinkTree::YeZiTotal(BTreeNode*t,int first)
{
BTreeNode*current;
if(first)
{
  current=head;
  first=0;
}
else
  current=t;
if(current!=NULL)
{
  if(current->lchild==NULL&&current->rchild==NULL)
   total++;
  YeZiTotal(current->lchild,first);
  YeZiTotal(current->rchild,first);
}
}
//////////////////////////////////////////////////////////////////////////////
//  主函数
//参数返回值：
//          0:成功；
int main()
{
BLinkTree t;
int finished=0;
    int choice,n;
while(!finished)
{
  cout<<" *********Menu*********"<<endl;
  cout<<" 1------建立一棵二叉树"<<endl;
  cout<<" 2------前序遍历递归算法"<<endl;
  cout<<" 3------前序遍历非递归算法"<<endl;
  cout<<" 4------中序遍历递归算法"<<endl;
  cout<<" 5------中序遍历非递归算法"<<endl;
  cout<<" 6------后序遍历递归算法"<<endl;
  cout<<" 7------后序遍历非递归算法"<<endl;
  cout<<" 8------求树高"<<endl;
  cout<<" 9------求叶子总数"<<endl;
  cout<<" 10-----求结点个数"<<endl;
  cout<<" 11-----输出二叉树"<<endl;
  cout<<" 12-----退出"<<endl;
  cin>>choice;
  switch(choice)
  {
  case 1:
   t.Creat(1);
   break;
  case 2:
   t.PreOrder1(t.head,1);
   break;
  case 3:
   
   t.PreOrder2();
   break;
  case 4:
   t.InOrder1(t.head,1);
   break;
  case 5:
  
   t.InOrder2();
   break;
  case 6:
   t.PostOrder1(t.head,1);
   break;
  case 7:
   
   t.PostOrder2();
   break;
  case 8:
   n=t.Depth(t.head,1);
   cout<<"树高为："<<n<<endl;
   break;
     case 9:
   t.YeZiTotal(t.head,1);
   cout<<"叶子总数为："<< t.total <<endl;
   break;
  case 10:
   cout<<"结点总数为："<<t.NodeNum<<endl;
   break;
  case 11:
   t.PrintLayerOrder();
   break;
     case 12:
   finished=1;
     break;
  }
}
return 0;
}