귀속 실현 두 갈래 나무

#pragma once
#include<iostream>
using namespace std;
#include<queue>
template<class T>
struct BinaryTreeNode{                    // 
 char _value;
 BinaryTreeNode* _left;
 BinaryTreeNode* _right;
 BinaryTreeNode(char value)
  :_value(value)
  ,_left(NULL)
  , _right(NULL)
 {}
};
template<class T>
class BinaryTree{
public:
 BinaryTree()         // 
  :_root(NULL)
 {}
 BinaryTree(const char* str):_root(NULL){       // 
  _CreateBinaryTree(_root,str);
 }
 BinaryTree(const BinaryTree& t){               // 
  _root = _Copy(t._root);
 }
 BinaryTree &operator =(const BinaryTree& t){   // 
  swap(_root, t._root);
  return *this;
 }
 ~BinaryTree(){          // 
  _Delete(_root);
 }
 void PrevOrder(){          // 
  _PrevOrder(_root);
  cout << endl;
 }
 void InOrder(){                                // 
  _InOrder(_root);
  cout << endl;
 }
 void PostOrder(){                              // 
  _PostOrder(_root);
  cout << endl;
 }
 void LevelOrder(){                             // 
  _LevelOrder(_root);
  cout << endl;
 }
 int Size(){                                    // 
  return _Size(_root);
 }
 int Depth(){          // 
  return _Depth(_root);
 }
protected:
 void _CreateBinaryTree(BinaryTreeNode<T>*& root, const char*& str){     // 
  if (*str != '#' && *str != '\0'){
   root = new BinaryTreeNode<T>(*str);
   _CreateBinaryTree(root->_left, ++str);
   _CreateBinaryTree(root->_right, ++str);
  }
 }
 BinaryTreeNode<T>* _Copy(BinaryTreeNode<T>* root){                       // 
  BinaryTreeNode<T>* _new = NULL;
  if (root){
   _new = new BinaryTreeNode<T>(root->_value);
   while (root){
    _new->_left = _Copy(root->_left);
    _new->_right = _Copy(root->_right);
    return _new;
   }
  }
  return _new;
 }
 BinaryTreeNode<T>* _Delete(BinaryTreeNode<T>* root){                   // 
  while (root){
   _Delete(root->_left);
   _Delete(root->_right);
   delete root;
   return root;
  }
  return root;
 }
 void _PrevOrder(BinaryTreeNode<T>* root){                        // 
  if (root){
   cout << root->_value << " ";
   _PrevOrder(root->_left);
   _PrevOrder(root->_right);
  }
 }
 void _InOrder(BinaryTreeNode<T>* root){                          // 
  if (root){
   if (root->_left == NULL && root->_right == NULL)
    cout << root->_value << " ";
   else{
    _InOrder(root->_left);
    cout << root->_value << " ";
    _InOrder(root->_right);
   }
  }
 }
 
 void _PostOrder(BinaryTreeNode<T>* root){                       // 
  if (root){
   if (root->_left == NULL && root->_right == NULL)
    cout << root->_value << " ";
   else{
    _PostOrder(root->_left);
    _PostOrder(root->_right);
    cout << root->_value << " ";
   }
  }
 }
 void _LevelOrder(BinaryTreeNode<T>* root){                        // 
  queue<BinaryTreeNode<T>*> q;
  q.push(root);
  while (root){
   cout << root->_value << " ";
   if (!q.empty()){
    BinaryTreeNode<T>* front = q.front();
    q.pop();
    q.push(front->_left);
    q.push(front->_right);
   }
   root = q.front();
  }
 }
 int _Size(BinaryTreeNode<T>* root){                          // 
  int count = 0;
  if (root){
   count += _Size(root->_left);
   count += _Size(root->_right);
  }
  if (root)
   return count + 1;
  else
   return count;
 }
 int _Depth(BinaryTreeNode<T>* root){                        // 
  int left_depth = 0;
  int right_depth = 0;
  if (root){
   left_depth = _Depth(root->_left);
   right_depth = _Depth(root->_right);
   return (left_depth > right_depth) ? left_depth + 1 : right_depth + 1;
  }
  else
   return 0;
 }
private:
 BinaryTreeNode<T>* _root;
};