| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 513 人关注过本帖
标题:关于一道二叉树遍历的问题帮忙找下错!
取消只看楼主 加入收藏
lzywin
Rank: 1
等 级:新手上路
帖 子:21
专家分:0
注 册:2009-11-11
结帖率:50%
收藏
 问题点数:0 回复次数:1 
关于一道二叉树遍历的问题帮忙找下错!
#include<iostream.h>
#include<stdlib.h>

template<class T>
struct BinTreeNode{
    T data;
    BinTreeNode<T> *leftChild,*rightChild;
    BinTreeNode():leftChild(NULL),rightChild(NULL){}
    BinTreeNode(T x,BinTreeNode<T> *l=NULL,BinTreeNode<T> * r=NULL)
            :data(x),leftChild(l),rightChild(r){}
};

enum Tag{L,R};
template<class T>
struct stkNode{
    BinTreeNode<T> *ptr;
    enum Tag tag;
    stkNode(BinTreeNode<T> *N=NULL):ptr(N),tag(L){}
};
#include"03_01_089SeqStack.h"

template <class T>
class BinaryTree{
public:
    BinaryTree():root(NULL){}                        //构造函数
    BinaryTree(T value):RefValue(value),root(NULL){}//构造函数
    ~BinaryTree(){ if(root) destroy(root); }        //析构函数

    friend istream& operator>>(istream &in,BinaryTree<T> &Tree)//重载操作,输入
    { Tree.CreateBinTree(in,Tree.root);    return in; }

    void  preOrder(void (*visit)(BinTreeNode<T> *p));//p204前序遍历,visit是访问函数
    void   inOrder(void (*visit)(BinTreeNode<T> *p));//p205中序遍历,visit是访问函数
    void postOrder(void (*visit)(BinTreeNode<T> *p));//p206后序遍历,visit是访问函数

protected:
    BinTreeNode<T> *root;    //二叉树的根指针
    T RefValue;                //数据输入停止标志
    void destroy(BinTreeNode<T> *&subTree);            //p196删除二叉树使之为空树

    void CreateBinTree(istream &in,BinTreeNode<T> *&BT);//P197前序遍历建立二叉树
};

template<class T>//后序遍历删除
void BinaryTree<T>::destroy(BinTreeNode<T> *&subTree){
    if(subTree==NULL) return;
    destroy(subTree->leftChild);
    destroy(subTree->rightChild);
    delete subTree; subTree=NULL;
}

//(1) CreateBinTree的实现;

template<class T>
void CreateBinTree(istream&in,BinTreeNode<T>*&BT){
    SeqStack<BinTreeNode<char>*>s;
    BT=NULL;
    BinTreeNode<char>*p,*t;int k;
    char ch;
    in>>ch;
    while(ch!=RefValue){
        switch(ch){
        case'(':s.Push(p);k=1;break;
        case')':s.Pop(t);break;
            case','=2;break;
        default:p=new BinTreeNode(ch);
            if(BT==NULL)BT=p;
            else if(k==1){
                s.getTop(t);t->leftChild=p;
            }
            else{
                s.getTop(t);t->rightChild=p;
            }
        }
        in>>ch;
    }
}
//(2) preOrder的实现;
//void  preOrder(void (*visit)(BinTreeNode<T> *p));//p204前序遍历,visit是访问函数

template<class T>
void BinaryTree<T>::preOrder(void (*visit)(BinTreeNode<T> *p)){
    SeqStack<BinTreeNode<T>*>S;
    BinTreeNode<T>*p=root;
    S.Push(NULL);
    while(p!=NULL){
        visit(p);
        if(p->rightChild!=NULL)S.Push(p->rightChild);
        if(p->leftChild!=NULL)p=p->leftChild;
        else S.Pop(p);
    }
}
//(3) inOrder的实现;
//void   inOrder(void (*visit)(BinTreeNode<T> *p));//p205中序遍历,visit是访问函数

template<class T>
void BinaryTree<T>::inOrder(void (*visit)(BinTreeNode<T> *p)){
SeqStack<BinTreeNode<T>*>S;
BinTreeNode<T>*p=root;
do{
    while(p!=NULL){
        S.Push(p);
        p=p->leftChild;
    }
    if (!S.IsEmpty()){
        S.Pop(p);visit(p);
        p=p->rightChild;
    }
}
while (p!=NULL||!S.IsEmpty());
}
//(4) postOrder的实现。
    //void postOrder(void (*visit)(BinTreeNode<T> *p));//p206后序遍历,visit是访问函数

template<class T>
void BinaryTree<T>::postOrder(void (*visit)(BinTreeNode<T> *p)){
SeqStack<stkNode<T>*>S;stkNode<T> w;
    BinTreeNode<T>*p=root;
    do{
        while(p!=NULL){
            w.ptr=p; w.tag=L; S.Push(w);
            p=p->leftChild;
        }
        int continuel=1;
        while(continuel&&!S.IsEmpty()){
            S.Pop(w);p=w.ptr;
            switch(w.tag){
            case L:w.tag=R;S.Push(w);
                continuel=0;
                p=p->rightChild;
                break;
            case R:visit(p);break;
            }
        }
    }
    while(!S.IsEmpty());
    cout<<endl;
}
另外一个头函数;
#include<stdlib.h>//用于exit(1)
#include<iostream.h>
#include <assert.h>
const int stackIncreament=20;
template <class T>
class SeqStack{
public:
    SeqStack(int sz=10);
    ~SeqStack(){ delete[]elements;}
    void Push(const T &x);    //新元素x进栈
    bool Pop(T &x);            //栈顶元素出栈,由x返回
    bool getTop(T &x);    //读取栈顶元素,由x返回
    bool IsEmpty()const{ return top==-1; }  //判断栈空否
    int getSize()const{ return top+1; }//计算栈中元素个数
    void MakeEmpty(){ top=-1; }//置空栈
    friend ostream &operator<<(ostream &out,SeqStack<T> &s);
private:
    T*  elements;//存放栈中元素的栈数组
    int top;//栈顶指针   
    int maxSize;//栈最大可容纳元素个数
    void overflowProcess();//栈的溢出处理
   
 };

//(1) 构造函数的实现;
template <class T>
SeqStack<T>::SeqStack(int sz): top(-1), maxSize(sz) {
     elements = new T[maxSize];   
     assert(elements!=NULL);
}

//(2) 函数Push的实现;
template <class T>
void SeqStack<T>::Push(const T& x) {   
  if (top==maxSize-1) overflowProcess();
  elements[++top] =x;
}


//(3) 函数Pop的实现;
template <class T>
bool SeqStack<T>:: Pop (T& x) {
    if(IsEmpty()==true) return false;
    x=elements[top--];
    return true;
}

   
//(4) 函数getTop的实现;
template <class T>
bool SeqStack<T>::getTop(T& x) {
    if (IsEmpty()==true) return false;   
    x= elements[top];   
    return true;
}


//(5) 函数operator<<的实现;
template <class T>
ostream& operator <<(ostream& os ,SeqStack<T>& s) {
    os<<"top="<<s.top<<endl;  
    for(int i=0;i<=s.top;i++)
            os<<i<<":"<<s.elements[i]<<endl;
    return os;
}


//(6) 函数overflowProcess的实现。
template <class T>
void SeqStack<T>::overflowProcess( ) {
    T *newArray=new T[maxSize+stackIncreament];  
    if(newArray==NULL)  {cerr<<"存储分配失败!";exit(1); }
    for(int i=0;i<=top;i++)
       newArray[i]=elements[i];
    maxSize=maxSize+stackIncreament;
    delete []elements;
    elements=newArray;
}
最后是主函数:
#include<iostream.h>
#include"stack.h"

template<class T>
void visit(BinTreeNode<T> *p){cout<<p->data;}

void main(){
    BinaryTree<char> BT('#');
    cout<<"\n输入二叉树的广义表(#结束):"<<endl;
    cin>>BT;

    cout<<"前序遍历输出二叉树:\n";
    BT.preOrder(visit);
    cout<<endl;

    cout<<"中序遍历输出二叉树:\n";
    BT.inOrder(visit);
    cout<<endl;

    cout<<"后序遍历输出二叉树:\n";
    BT.postOrder(visit);
    cout<<endl;
}




搜索更多相关主题的帖子: 二叉树 遍历 
2009-12-22 16:35
lzywin
Rank: 1
等 级:新手上路
帖 子:21
专家分:0
注 册:2009-11-11
收藏
得分:0 
没有人帮忙吗?
2009-12-22 16:47
快速回复:关于一道二叉树遍历的问题帮忙找下错!
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.026762 second(s), 8 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved