回 帖 发 新 帖 刷新版面

主题:高手帮忙添加一个层序遍历,就差这个了

#include <iostream.h>
#include <stdlib.h>
#include <strstrea.h>//给出使用字符串流对象的头文件
#include <conio.h>
typedef char  ElemType ;   //定义二叉树的结点类型
struct  BTreeNode{
    ElemType data;           //值域
    BTreeNode *left;         //左孩子指针域
    BTreeNode *right;        //右孩子指针域
};

/*void InitBTree(BTreeNode &BT);   //处始化二叉树,即把它置为一棵空树
void CreateBTree(BTreeNode *&BT,char *a);     //生成二叉树
void Preorder(BTreeNode *BT);          //前序遍历二叉树
void Inorder(BTreeNode *BT);           //中序遍历二叉树
void Postorder(BTreeNode *BT);         //后序遍历二叉树
int  BTreeDepth(BTreeNode *BT);        //求二叉树的深度
void PrintBTree(BTreeNode *BT);       //输出二叉树
void Levelorder(BTreeNode *BT);       //遍历
void ClearBTree(BTreeNode *BT)         //清除二叉树*/


//处始化二叉树
void InitBTree(BTreeNode *&BT)
{
    BT=NULL;
}
//建立二叉树
void CreateBTree(BTreeNode *&BT,char *a)
{
    BTreeNode *s[10];
    int top=-1;
    BT=NULL;
    BTreeNode *p;
    int k;
    istrstream ins(a);
    char ch;
    ins>>ch;
    while(ch!='@')
    {
        switch(ch)
        {
        case'(':
            top++;s[top]=p;k=1;
            break;
        case')':
            top--;
            break;
            case',':
            k=2;
            break;
            default:
                p=new BTreeNode;
                p->data=ch;p->left=p->right=NULL;
                if(BT==NULL)
                    BT=p;
                else{
                    switch(k)
                    {
                      case 1:
                          s[top]->left=p;
                          break;
                      case 2:
                          s[top]->right=p;
                    }
                }
        }
        ins>>ch;
    }
}
//前序遍历的递归
void Preorder(BTreeNode *BT)
{
 if(BT!=NULL)
 {
  cout<<BT->data<<' ';  //访问根结点
  Preorder(BT->left);   //前序遍历左子树
  Preorder(BT->right);   //前序遍历右子树
 }
}

//中序遍历的递归
void Inorder(BTreeNode *BT)
{
 if(BT!=NULL)
 {
  Inorder(BT->left);   //中序遍历左子树 
  cout<<BT->data<<' '; //访问根结点
  Inorder(BT->right);   //中序遍历右子树
 }
}

//后序遍历的递归
void Postorder(BTreeNode *BT)
{
 if(BT!=NULL)
 {
  Postorder(BT->left); //后序遍历左子树
  Postorder(BT->right); //访问根结点
  cout<<BT->data<<' '; //后序遍历右子树
 }
}
//二叉树的深度
int BTreeDepth(BTreeNode *BT)
{
    if(BT==NULL)
        return 0;
    else
    {
        int dep1=BTreeDepth(BT->left);
        int dep2=BTreeDepth(BT->right);
        if (dep1>dep2)
            return  dep1+1;
        else 
            return  dep2+1;
    }
}
//按层次遍历
//输出二叉树
void PrintBTree(BTreeNode *BT)
{
    if(BT!=NULL)
    {
        cout<<BT->data; 
        if(BT->left!=NULL||BT->right!=NULL)
        {
            cout<<'(';
            PrintBTree(BT->left);
            if(BT->right!=NULL)
                cout<<',';
            PrintBTree(BT->right);
            cout<<')';
        }
    }
}
//主函数
void main()
{
    BTreeNode *bt;
    InitBTree(bt);
    char b[50];
    cout<<"输入以'@'字符作为结束符的二叉树广义表表示:"<<endl;
    cin.getline(b,sizeof(b));
    CreateBTree(bt,b);
    cout<<"输出二叉树:";
    PrintBTree(bt);
    cout<<endl;
    cout<<"前序:";
    Preorder(bt);
    cout<<endl;
    cout<<"中序";
    Inorder(bt);
    cout<<endl;
    cout<<"后序";    
    Postorder(bt);
    cout<<endl;
    //cout<<"按层";
    //Levelorder(bt);
    //cout<<endl;
    cout<<"二叉树的深度为:";
    cout<<BTreeDepth(bt)<<endl;
    //ClearBTree(bt);
    getch();
}
再帮忙告诉我核心算法设计(流程图)
万分感激

回复列表 (共2个回复)

沙发

//lyt8604@sohu.com
//QQ:393870322
void leveltran(btree b)//二叉排序树的层次遍历
{                            
  struct node
  {
   btree vec[MAXLEN];
   int f,r;
  }q;
  q.f=0;
  q.r=0;
  if(b!=NULL) printf("%d ",b->data);
  q.vec[q.r]=b;
  q.r=q.r+1;
  while(q.f<q.r)//模拟队列,用q.r和q.f做标志,当两者相等时即队列为空
  {
   b=q.vec[q.f];
   q.f=q.f+1;
   if(b->left!=NULL)
   {
    printf("%d ",b->left->data);
    q.vec[q.r]=b->left;
    q.r=q.r+1;
   }
   if(b->right!=NULL)
   {
    printf("%d ",b->right->data);
    q.vec[q.r]=b->right;
    q.r=q.r+1;
   }
  }
}

板凳

用队列就可以了

我来回复

您尚未登录,请登录后再回复。点此登录或注册