二叉树(Binary Tree)的二叉链表(Binary Linked List)实现

#ifndef __BINARYNODE_H__
#define __BINARYNODE_H__
template <class T>
class BinaryNode
{
public:
  T data;
  BinaryNode<T> *lchild, *rchild;
};
#endif

#ifndef __BINARYTREE_H__
#define __BINARYTREE_H__
#include "BinaryNode.h"
template <class T>
class BinaryTree
{
public:
  BinaryTree();
  ~BinaryTree();
public:
  void PreOrder();
  void InOrder();
  void PostOrder();
  void LeverOrder();
private:
  static int count;
  BinaryNode<T> *root;
  BinaryNode<T> *Creat(BinaryNode<T> *_binarytree);
private:
  void PreOrder(BinaryNode<T> *_binarytree);
  void InOrder(BinaryNode<T> *_binarytree);
  void PostOrder(BinaryNode<T> *_binarytree);
  void Release(BinaryNode<T> *_binarytree);
};
#endif

#include "BinaryTree.h"
#include <iostream>
using namespace std;
template <class T>
int BinaryTree<T>::count = 0;
template <class T>
BinaryTree<T>::BinaryTree()
{root = Creat(root);}
template <class T>
BinaryTree<T>::~BinaryTree()
{Release(root);}
template <class T>
void BinaryTree<T>::PreOrder()
{PreOrder(root);}
template <class T>
void BinaryTree<T>::InOrder()
{InOrder(root);}
template <class T>
void BinaryTree<T>::PostOrder()
{PostOrder(root);}
template <class T>
void BinaryTree<T>::LeverOrder()
{
  int front = -1, rear = -1;
  BinaryNode<T> *tempNode;
  BinaryNode<T> **queue = new BinaryNode<T> *[count];
  queue[++rear] = root;
  while (front != rear)
  {
  tempNode = queue[++front];
  cout << tempNode->data << "\t";
  if (tempNode->lchild != nullptr)
    queue[++rear] = tempNode->lchild;
  if (tempNode->rchild != nullptr)
    queue[++rear] = tempNode->rchild;
  }
}
template <class T>
BinaryNode<T> *BinaryTree<T>::Creat(BinaryNode<T> *_binarytree)
{
  char ch;
  cin >> ch;
  if (ch == '#')
  _binarytree = nullptr;
  else
  {
  _binarytree = new BinaryNode<T>;
  _binarytree->data = ch;
  _binarytree->lchild = Creat(_binarytree->lchild);
  _binarytree->rchild = Creat(_binarytree->rchild);
  }
  count += 1;
  return _binarytree;
}
template <class T>
void BinaryTree<T>::PreOrder(BinaryNode<T> *_binarytree)
{
  if (_binarytree == nullptr)
  return;
  else
  {
  cout << _binarytree->data << "\t";
  PreOrder(_binarytree->lchild);
  PreOrder(_binarytree->rchild);
  }
}
template <class T>
void BinaryTree<T>::InOrder(BinaryNode<T> *_binarytree)
{
  if (_binarytree == nullptr)
  return;
  else
  {
  InOrder(_binarytree->lchild);
  cout << _binarytree->data << "\t";
  InOrder(_binarytree->rchild);
  }
}
template <class T>
void BinaryTree<T>::PostOrder(BinaryNode<T> *_binarytree)
{
  if (_binarytree == nullptr)
  return;
  else
  {
  PostOrder(_binarytree->lchild);
  PostOrder(_binarytree->rchild);
  cout << _binarytree->data << "\t";
  }
}
template <class T>
void BinaryTree<T>::Release(BinaryNode<T> *_binarytree)
{
  if (_binarytree != nullptr)
  {
  Release(_binarytree->lchild);
  Release(_binarytree->rchild);
  delete _binarytree;
  }
}

#include <iostream>
#include "BinaryTree.h"
#include "BinaryTree.cpp"
using namespace std;
int main()
{
  BinaryTree<char> *bt = new BinaryTree<char>;
  cout << "LeverOrder: \t";
  bt->LeverOrder();
  cout << endl;
  cout << "PreOrder: \t";
  bt->PreOrder();
  cout << endl;
  cout << "InOrder: \t";
  bt->InOrder();
  cout << endl;
  cout << "PostOrder: \t";
  bt->PostOrder();
  cout << endl;
  return 0;
}

//要形成树(#号代表空节点)：
                    A                               A
                  /   \                           /   \
                 B     C          ====>          B     C
                  \                             / \   / \
                   D                           #   D #   #
                                                  / \
                                                 #   #
// 输入(#号代表空节点)：
A
B
#
D
#
#
C
#
#
// 输出
LeverOrder:     A       B       C       D
PreOrder:       A       B       D       C
InOrder:        B       D       A       C
PostOrder:      D       B       C       A