c++数据结构,二叉树运行不出来

k7y2kmym
  • 1
新手上路,请多包涵
#include <iostream>
#include <stack>
using namespace std;

template <class ElemType>          // 二叉链表结点结构
struct BTNode
{
    ElemType data;
    BTNode<ElemType> *lchild, *rchild;
};

//二叉链表类
template<class ElemType>
class BinaryTree
{
public:
    //构造函数    
    BinaryTree():m_root(NULL){}

    //按以先序次序输入结点值的方式建立二叉树
    void _Create(BTNode<ElemType> * &T,ElemType ch[],const ElemType &c,int &i);

    //按先序次序输入结点值的方式建立二叉树的接口函数
    void Create(ElemType ch[], const ElemType &c);
    

    //求叶子结点个数
    int _Leaf(BTNode<ElemType> *T);

    //求叶子结点个数的接口函数
    int Leaf()
    {
        return _Leaf(m_root);
    }
        
    //求二叉树的深度
    int _Depth(BTNode<ElemType>*);

    //求二叉树的深度的接口函数
    int Depth()
    {
        return _Depth(m_root);
    }

    //先序递归遍历二叉树
    void _PreorderTraverse(BTNode<ElemType>*T,void (*visit)(const ElemType &e));

    //先序递归遍历二叉树的接口函数
    void PreorderTraverse()
    {
        _PreorderTraverse(m_root,visit);
    }

    //中序递归遍历二叉树
    void _InorderTraverse(BTNode<ElemType>*T);
    
    //中序递归遍历二叉树的接口函数 
    void InorderTraverse()
    {
        _InorderTraverse(m_root);
    }

    //后序递归遍历二叉树
    void _PostorderTraverse(BTNode<ElemType>*T);

    //后序递归遍历二叉树的接口函数 
    void PostorderTraverse () 
    {
        _PostorderTraverse(m_root);
    }

    //先序非递归遍历二叉树
    void PreorderTraverseNonRecursive();

    //计算二叉树中结点值为奇数的结点个数
    int _CountOdd(BTNode<ElemType> *T);   

    //计算二叉树中结点值为奇数的结点个数的接口函数
    int CountOdd()       
    {
         int NumOdd=_CountOdd(m_root);
         return NumOdd; 
    } 

    //以广义表形式输出二叉树
    void _Print(BTNode<ElemType> *T);

    //以广义表形式输出二叉树的接口函数
    void Print()
    {
        _Print(m_root);
    }


private:
    BTNode<ElemType> *m_root;    
};

//按先序次序输入结点值的方式建立二叉树
template <class ElemType>
void BinaryTree<ElemType>:: _Create(BTNode<ElemType> * &T,ElemType ch[],const ElemType &c,int &i)
{
    if(ch[i]==c)
        T=NULL;
    else{
        T=new BTNode<ElemType>;
        T->data=ch[i];
        _Create(T->lchild,ch,c,++i);
        _Create(T->rchild,ch,c,++i);
    }
}

//按先序次序输出结点值的方式建立二叉树的接口函数
template<class ElemType>
void BinaryTree<ElemType>::Create(ElemType ch[],const ElemType &c)
{
    int i=0;
    _Create(m_root,ch,c,i);
}

//求二叉树的深度
template <class ElemType>
int BinaryTree<ElemType>::_Depth(BTNode<ElemType>* T)
{
if(!T)
return 0;
int h1,h2;
h1=_Depth(T->lchild);
h2=_Depth(T->rchild);
return h1>h2?h1+1:h2+1;
}


//先序递归遍历二叉树
template <class ElemType>
void BinaryTree<ElemType>::_PreorderTraverse(BTNode<ElemType>*T,void(*visit)(const ElemType &e))
{ 
    if(T){
        visit(T->data);
        _PreorderTraverse(T->lchild,visit);
        _PreorderTraverse(T->rchild,visit);
    }

}

//中序递归遍历二叉树
template <class ElemType>
void BinaryTree<ElemType>::_InorderTraverse(BTNode<ElemType>*T,void (*visit)(const ElemType &e))
{
    if(T){
        _InorderTraverse(T->lchild,visit);
        visit(T->data);
        _InorderTraverse(T->rchild,visit);
    }


}

//后序递归遍历二叉树
template <class ElemType>
void BinaryTree<ElemType>::_PostorderTraverse(BTNode<ElemType>*T)
{
    if(T){
        _PostorderTraverse(T->lchild,visit);
        -PostorderTraverse(T->rchild,visit);
        visit(T->data);
    }

}

//先序遍历的非递归遍历二叉树
template<class ElemType>
void BinaryTree<ElemType>::PreorderTraverseNonRecursive()
{
stack<BTNode<ElemType> *> S;
BTNode<ElemType> *p;
S.push (m_root);
while (!S.empty ()) {
p = S.top ();

while (p)
 {
visit(p->data);
p = p->lchild;
S.push(p); // 向左走到尽头
}
S.pop(); // 空指针退栈

if (!S.empty())
{
p = S.top ();
S.pop();
S.push(p->rchild);
}
}

}

//求二叉树叶子结点个数
template<class ElemType>
int BinaryTree<ElemType>::_Leaf(BTNode<ElemType> *T)
{

    if(T==NULL)
        return 0;
    else if(T->lchild==NULL&&T->rchild==NULL)
        return 1;
    else
        return _Leaf(T->lchild)+_Leaf(T->rchild);
}

//计算二叉树中结点值(如果是字符,则应为字符ASCII码值)为奇数的结点个数
template<class ElemType>
int BinaryTree<ElemType>::_CountOdd(BTNode<ElemType> *T)
{

    static int a=1;
    if(T==NULL)
        return 0;
    else{
        if(T->data%2!=0){
            a++;
        _CountOdd(T->lchild);
        _CountOdd(T->rchild);
        }
    }
    return a;
}

//以广义表形式输出二叉树
template <class ElemType> 
void BinaryTree<ElemType>::_Print(BTNode<ElemType> *T)
{
    if(T)
    {
        cout<<T->data;
        if(T->lchild!=NULL||T->rchild!=NULL)
        {
            cout<<"(";
            _Print(T->lchild);
            if(T->rchild!=NULL) 
                cout<<",";
            _Print(T->rchild);
            cout<<")";
        }
    }
}


//主函数
int main()
{
    BinaryTree<char>b;
    char ch[50],c;
    cout<<"请输入序列"<<endl;
    cin>>ch;
    cout<<"请输入特殊字符"<<endl;
    cin>>c;
    b.Create(ch,c);
    cout<<"建立的二叉树为 "<<endl;
    b.Print();
    cout<<"奇结点个数"<<b.CountOdd()<<endl;
    b.PreorderTraverse();
    cout<<"先序非递归"<<endl;
    b.Print();
    cout<<"叶子结点个数"<<b.Leaf<<endl;

    return 0;
}
回复
阅读 381
撰写回答
你尚未登录,登录后可以
  • 和开发者交流问题的细节
  • 关注并接收问题和回答的更新提醒
  • 参与内容的编辑和改进,让解决方法与时俱进
宣传栏