二叉链表

二叉链表结点的实现

template<typename T>
struct BiNode{
  T data;
  BiNode<T> *lchild,*rchild;
};

二叉链表的实现

template<typename T>
class BiTree{
  private:
      BiNode<T> *root;
      BiNode<T> *Creat();//构造函数的调用
      void Release(BiNode<T> *bt);//析构函数的调用
      void PreOrder(BiNode<T> *bt);//前序遍历
      void InOrder(BiNode<T> *bt);//中序遍历
      void PostOrder(BiNode<T> *bt);//后序遍历
      void LeverOrder(BiNode<T> *bt);//层序遍历
  public:
      BiTree()
      {
          root=Creat();
      }
      ~BiTree()
      {
         Release(root);
      }
      void PreOrder()
      {
          PreOrder(root);
      }
      void InOrder()
      {
          InOrder(root);
      }
      void PostOrder()
      {
          PostOrder(root);
      }
      void LeverOrder()
      {
          LeverOrder(root);
      }
};

二叉树前序遍历递归算法

template<typename T>
void BiTree<T>::PreOrder(BiNode<T> *bt)
{
    if(bt==NULL)
        return;
    else{
        cout<<bt->data;
        PreOrder(bt->lchild);
        PreOrder(bt->rchild);
    }
}

二叉树中序遍历递归算法

template<typename T>
void BiTree<T>::InOrder(BiNode<T> *bt)
{
    if(bt==NULL)
        return;
    else{
        InOrder(bt->lchild);
        cout<<bt->data;
        InOrder(bt->rchild);
    }
}

二叉树后序遍历递归算法

template<typename T>
void BiTree<T>::PostOrder(BiNode<T> * bt)
{
    if(bt==NULL)
        return;
    else{
    PostOrder(bt->lchild);
    PostOrder(bt->rchild);
    cout<<bt->data;
    }
}

层序遍历

template<typename T>
void BiTree<T>::LeverOrder(BiNode<T> * bt)
{
    queue<BiNode<T> *> Queue;
    if(bt)
        Queue.push(bt);
    while(!Queue.empty())
    {
        bt=Queue.front();//取队列结点
        Queue.pop();
        cout<<bt->data;//访问当前结点
        if(bt->lchild)//左子树入栈
            Queue.push(bt->lchild);
        if(bt->rchild)//右子树入栈
            Queue.push(bt->rchild);
    }
}

构造函数

template<typename T>
BiNode<T> *BiTree<T>::Creat()
{
    BiNode<T> *bt;
    char ch;
    cin>>ch;
    if(ch=='#')
        bt=NULL;
    else{
        bt=new BiNode<T>;
        bt->data=ch;
        bt->lchild=Creat();
        bt->rchild=Creat();
    }
    return bt;
}

析构函数

 

template<typename T>
void BiTree<T>::Release(BiNode<T> *bt)
{
    if(bt!=NULL){
        Release(bt->lchild);
        Release(bt->rchild);
        delete bt;
    }
}

完整代码示例:

#include <iostream>
#include<queue>
using namespace std;
template<typename T>
struct BiNode{
  T data;
  BiNode<T> *lchild,*rchild;
};
template<typename T>
class BiTree{
  private:
      BiNode<T> *root;
      BiNode<T> *Creat();//构造函数的调用
      void Release(BiNode<T> *bt);//析构函数的调用
      void PreOrder(BiNode<T> *bt);//前序遍历
      void InOrder(BiNode<T> *bt);//中序遍历
      void PostOrder(BiNode<T> *bt);//后序遍历
      void LeverOrder(BiNode<T> *bt);//层序遍历
  public:
      BiTree()
      {
          root=Creat();
      }
      ~BiTree()
      {
         Release(root);
      }
      void PreOrder()
      {
          PreOrder(root);
      }
      void InOrder()
      {
          InOrder(root);
      }
      void PostOrder()
      {
          PostOrder(root);
      }
      void LeverOrder()
      {
          LeverOrder(root);
      }
};
template<typename T>
BiNode<T> *BiTree<T>::Creat()
{
    BiNode<T> *bt;
    char ch;
    cin>>ch;
    if(ch=='#')
        bt=NULL;
    else{
        bt=new BiNode<T>;
        bt->data=ch;
        bt->lchild=Creat();
        bt->rchild=Creat();
    }
    return bt;
}
template<typename T>
void BiTree<T>::Release(BiNode<T> *bt)
{
    if(bt!=NULL){
        Release(bt->lchild);
        Release(bt->rchild);
        delete bt;
    }
}
template<typename T>
void BiTree<T>::PreOrder(BiNode<T> *bt)
{
    if(bt==NULL)
        return;
    else{
        cout<<bt->data;
        PreOrder(bt->lchild);
        PreOrder(bt->rchild);
    }
}
template<typename T>
void BiTree<T>::InOrder(BiNode<T> *bt)
{
    if(bt==NULL)
        return;
    else{
        InOrder(bt->lchild);
        cout<<bt->data;
        InOrder(bt->rchild);
    }
}
template<typename T>
void BiTree<T>::PostOrder(BiNode<T> * bt)
{
    if(bt==NULL)
        return;
    else{
    PostOrder(bt->lchild);
    PostOrder(bt->rchild);
    cout<<bt->data;
    }
}
template<typename T>
void BiTree<T>::LeverOrder(BiNode<T> * bt)
{
    queue<BiNode<T> *> Queue;
    if(bt)
        Queue.push(bt);
    while(!Queue.empty())
    {
        bt=Queue.front();//取队列结点
        Queue.pop();
        cout<<bt->data;//访问当前结点
        if(bt->lchild)//左子树入栈
            Queue.push(bt->lchild);
        if(bt->rchild)//右子树入栈
            Queue.push(bt->rchild);
    }
}
int main()
{
   BiTree<char> bt;
   bt.PreOrder();
   cout<<endl;
   bt.LeverOrder();
    return 0;
}

 

 

发布者

deng

听闻余生久不遇,相逢别错过。

发表评论

电子邮件地址不会被公开。 必填项已用*标注