C++二叉树数据结构_c++ 二叉树 用什么数据结构

什么是二叉树？

• 二叉树是节点有限集合，集合或者为空，或者是由一个根节点加上两个子树的（左子树和右子树）、互不相交的节点组成的数据类型
• 二叉树的每个节点最多有2个子女，且有左右之分不能颠倒，分别称为左子女和右子女
• 二叉树中不存在只存在度为0的节点（即为叶子节点，无子女）、度为1的节点（只有一个子女的节点）、度为2的节点（左右子女都有的节点）
• 二叉树是分支数不超过2的有序树，具有5种可能的形态：空二叉树、只有根节点的二叉树、只有左子树的二叉树、只有右子树的二叉树、左右子树都有的二叉树

树相关的术语

这些术语对于二叉树算法的理解至关重要：

节点（node）：包含数据项及指向其他节点的分支

节点的度（degree）：是指节点所拥有的子树棵树

叶节点（leaf）：度为0的节点，也称之为终端节点

分支节点（branch）：除叶节点的以外的其他节点，又称之为非终端节点

子女节点（child）：若节点A有直接子节点B、C等，（B、C节点的父节点为A），则这些直接子节点为A的子女节点

父节点（parent)：若节点A有子女节点，则A为子节点的父节点

兄弟节点（sibling）：有同一父节点的子女互为兄弟

祖先节点（ancestor）：从根节点到该节点所经过的分支上的所有节点

子孙节点（descendant)：某一节点的子女、以及子女的子女都是子孙节点、

节点所处层次（level）：也称为节点的深度，从根节点到该节点所经过的分支条数，根节点在第1层、根节点的子女在第2层、树中任意节点的层次为它的父节点的层次加1

树的深度（depth）：树中距离根节点最远的节点所处的层次即为树的深度，空树的深度为0，只有一个根节点的树的深度为1

树的高度（height）：叶节点的高度为1，非叶节点的高度为它的子女节点的高度的最大值加1，树的高度与深度计算方向不同，当数值相等

树的度（degree）：树中节点的度最大值，对于二叉树，树的度为2

有序树（ordered tree)：节点中各颗子树（T1，T2，T3…)是有次序的即为有序树，而无序树的次数是可相互交换的或无序的

森林(forest)：由（m>=0)颗树的集合，在数据结构中，删去一棵非空树的根节点，树就变成森林，反之添加一个根节点森林就成为一棵树

二叉树有哪些性质？

1.二叉树的第i层最多有$2^{i-1}$个节点（k>=0)

证明：当i=1，非空二叉树有1个节点；当i=2最多有$2^1$个节点；当i等于k最多有$2^{k-1}$个节点

2.深度为k（k>=0)的二叉树最少有k个节点，最多有$2^k-1$个节点

证明：

每一层至少有一个节点，整个二叉树至少有K个节点

当i==0时，无节点；当i>=1时为非空二叉树，第i层最多有$2^{i-1}$个节点

3.对于一棵非空二叉树，若叶节点数为n0，度为2的非叶节点数为n2，则n0=n2+1

证明：

• 具有n个节点的二叉树只存在度为0、度为1、度为2的节点，节点总数n=n0+n1+n2
• 具有n个节点的二叉树拥有边数e=n-1
• 二叉树节点度为1则发出1条边，度为2则发出2条边，度为0则发出0条边，则总边数e=n1+2*n2
• 将以上等式联立方程组消去n1，则有n0=n2+1

4.具有n个节点的完全二叉树，深度为$\lceil {\log }_2(n+1)\rceil$

证明：深度为k的二叉树最多节点个数 $2^{k-1}-1<n\le 2^k-1$，求出用n表示出k即为所求

完全二叉树（complete binary tree）：一棵具有N个节点深度为k二叉树，从第1层到第k-1层的各层节点数都是满的，仅有第k层节点不满，即第k层节点从右向左连续缺若干个节点

满二叉树（full binary tree）：深度为k且具有$2^k-1$个节点的二叉树即为满二叉树，满二叉树的每一层节点都达到最大个数

5.具有n个节点的完全二叉树自顶向下、同一层自左向右连续编号1,2,3...,n并依次放入一个一维数组A[i]($0\le i<n$)，则存在以下关系：

（1）若i==0，则节点i为根，无父节点；若i>1，则节点i的父节点为节点$\lfloor i/2\rfloor$

（2）若2 * i <=n，则节点i的左子女为2 * i

（3）若2 * i + 1 <= n，则节点i的右子女节点为2 * i + 1

（4）若节点i为奇数，则A[i]表示左子女，则它的右兄弟为 A[i+1]

（5）若节点i为偶数，且i > 0 ，则A[i]表示右子女，则它的左兄弟为A[i-1]

（6）节点i所在层次为$\lfloor lo{g}_2(i+1)\rfloor +1$

二叉树如何进行存储？

1.数组存储

若二叉树是完全二叉树，具有N个节点，可用一个大小为N的数组A[N]存储，第k个节点(k>=0 && k<N）的父节点为(k-1)/2向下取整，第k个节点的子女节点为2*k-1，注2*k-1<N

若二叉树是普通的非完全二叉树，具有M个节点，那么最多需要一个大小为$2^{M-1}-1$的数组，显然存在空间利用率非常低

2.二叉链表存储

对于二叉树，每个节点存在三个域：数据域、左子女指针、右子女指针

每个节点存在只有左子女、只有右子女、左右子女都有的可能

具有N个节点的二叉树，存在N-1条边，具有2*N个指针域，其中空指针域有2*N-（N-1)=N+1个

二叉树实现

//二叉树
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <iostream>
#include <queue>
#include <stack>
#include <string>

using namespace std;
//二叉树的节点
template <class T> struct TreeNode {
  T data;
  TreeNode<T> *leftChild;
  TreeNode<T> *rightChild;
  TreeNode() : leftChild(NULL), rightChild(NULL) {}
  TreeNode(T x, TreeNode<T> *l = NULL, TreeNode<T> *r = NULL) {
    data = x;
    leftChild = l;
    rightChild = r;
  }
};
//二叉树
template <class T> class BinTree {
private:
  TreeNode<T> *root;
  T refValue;
  void insert(TreeNode<T> *&subtree, const T &x);
  void destroy(TreeNode<T> *&subtree);
  TreeNode<T> *find(TreeNode<T> *subtree, const T &x);
  TreeNode<T> *copy(TreeNode<T> *subtree);
  int getHeight(TreeNode<T> *subtree);
  int getSize(TreeNode<T> *subtree);
  void Traverse(TreeNode<T> *subtree, ostream &out);
  void preOrder(TreeNode<T> *subTree, void (*visit)(TreeNode<T> *p));
  void postOrder(TreeNode<T> *subtree, void (*visit)(TreeNode<T> *p));
  void inOrder(TreeNode<T> *subtree, void (*visit)(TreeNode<T> *p));

  TreeNode<T> *getParent(TreeNode<T> *subtree, TreeNode<T> *curr);

  friend ostream &operator<<(ostream &out, BinTree<T> &tree) {
    //out<<"二叉树前序遍历："<<endl;
    tree.Traverse(tree.root, out);
    out << endl;
    return out;
  }
  //给定节点t，删除该节点的删除叶子节点
  void delLeafNode(TreeNode<T> *&t);
  //给定节点t，计算该节点及其子节点度为2的节点数量
  int degree_2(TreeNode<T> *t);
  //给定节点t，计算该节点及其子节点度为1的节点数量
  int degree_1(TreeNode<T> *t);
  //
  int nodeLevel(TreeNode<T> *node, T x, int h);
  //广义表建立二叉树
  void createIstreamBinTree(istream &in, TreeNode<T> *&subtree); //创建二叉树
  文件形式输入广义表
  void inputFilePreRecursion(ifstream &in, TreeNode<T> *&subtree);
  void tablePrint(TreeNode<T> *treenode);

public:
  //前序序列建立二叉树
  void createBinTree(string &str);
  //广义表建立二叉树
  friend istream &operator>>(istream &in, BinTree<T> &subtree) {
    subtree.createIstreamBinTree(in, subtree.root);
    return in;
  }
  BinTree() : root(NULL) {}
  //构造一个空二叉树，参数value表示输入的结束符
  BinTree(T value) : refValue(value), root(NULL) {}
  //使用前序遍历形式的字符串序列str(如：ABC##DE#G##F###)，构造一棵二叉树
  //前序遍历形式的字符串规则：
  //  1.指定#表示空节点，对于读取的每一个字符，如果不是#，则先建立根、然后建立左子树
  //  2.当读取到#，说明左子女节点到底了，这时要创建右子女节点
  //  3.当连续读取到2个#，说明该节点所在子树创建完了，需要在父节点上创建子树
  //  4.当连续读取到3个#，说明二叉树创建完毕
  BinTree(T value, string &str) {
    refValue = value;
    root = NULL;
    createBinTree(str);
  }
  //		复制构造
  BinTree(BinTree<T> &tree) { root = copy(tree.root); }
  ~BinTree() { destroy(root); }
  //删除叶子节点
  void delLeafNode() { delLeafNode(root); }
  // 2度节点个数
  int degree_2() { return degree_2(root); }
  // 1度节点个数 ，即叶子节点
  int degree_1() { return degree_1(root); }
  bool isEmpty() { return (root == NULL) ? true : false; }
  //返回树根
  TreeNode<T> *getRoot() const { return root; }
  //返回父节点
  TreeNode<T> *getParent(TreeNode<T> *curr) {
    return (root == NULL || root == curr) ? NULL : getParent(root, curr);
  }
  //返回右子女
  TreeNode<T> *getRightChild(TreeNode<T> *curr) {
    return (curr != NULL) ? curr->rightChild : NULL;
  }
  //返回左子女
  TreeNode<T> *getLeftChild(TreeNode<T> *curr) {
    return (curr == NULL) ? NULL : curr->leftChild;
  }
  //返回树深度
  int getHeight() { return getHeight(root); }
  //前序
  void preOrder(void (*visit)(TreeNode<T> *p)) { preOrder(root, visit); }
  //中序
  void inOrder(void (*visit)(TreeNode<T> *p)) { inOrder(root, visit); }
  //后序
  void postOrder(void (*visit)(TreeNode<T> *p)) { postOrder(root, visit); }
  //层次遍历
  void levelOrder(void (*visit)(TreeNode<T> *p));
  //插入节点
  bool insert(const T &item) {
    if (root == NULL) {
      return 0;
    } else {
      insert(root, item);
      return 1;
    }
  }
  //查找树节点
  TreeNode<T> *find(const T &item) { return find(root, item); }
  //树节点总数
  int getSize() { return getSize(root); }
  //给定一个值x，返回该值对应节点所处的层次
  int nodeLevel(T x) { return nodeLevel(root, x, 1); }
  //删除指定节点，若找到节点 x ，则将该节点删除并返回true，否则返回false
  bool removeData(T x);
  //文件形式输入广义表建立的二叉树
  void inputFilePreRecursion(ifstream &in) { inputFilePreRecursion(in, root); }
  //使用一个广义表字符串，使用栈实现广义表前序建立二叉树
  //广义表字符串如：A(B(C,),D(E,F(,G))))#
  //广义表建立二叉树规则：
  // 1.第1个字符为根节点，括号()为根的左右子树
  // 2.左右子树用逗号分隔，若仅有左子树或仅有右子树，逗号不能缺省
  // 3.整个广义表的结尾加上一个特殊的符号#，表示结束
  void createTableTree(string &str);
  //输出以广义表表示的树
  void tablePrint() { tablePrint(root); }
  //计算值为x对应节点所在层次的节点个数
  int gainCurrLevelNodes(T x) {
    // nodeLevel(x)计算节点 x 所处层次
    int k = nodeLevel(x);
    return gainCurrLevelNodes(root, k);
  }

  //计算指定节点所在层次的节点总数
  int gainCurrLevelNodes(TreeNode<T> *rootnode, int k) {
    queue<TreeNode<T> *> Q;
    TreeNode<T> *p = root;
    if (k == 0 || k == 1) {
      return k;
    }
    int curr = 1; //当前节点
    int next = 0; //下一层次节点未知设为0
    int level = 1;
    Q.push(p);
    while (!Q.empty()) {
      p = Q.front();
      Q.pop();
      curr--;
      if (p->leftChild != NULL) {
        Q.push(p->leftChild);
        next++;
      }
      if (p->rightChild != NULL) {
        Q.push(p->rightChild);
        next++;
      }
      if (curr == 0) { //为 0 说明栈中
        level++;
        curr = next;
        next = 0;
        if (level == k) {
          break;
        }
      }
    }
    return curr;
  }
  //每一层次的节点
  void queueLevelOrder(TreeNode<T> *rootnode) {

    if (!root)
      return;
    queue<TreeNode<T> *> Q;
    queue<T> R;
    Q.push(rootnode); //根节点进队
    int level = 0;    //第几层
    cout << "层次"
         << "\t"
         << "数量"
         << "\t"
         << "节点" << endl;
    while (!Q.empty()) {
      int curr = Q.size(); //当前层数的节点数量
      for (int i = 0; i < curr; i++) {
        TreeNode<T> *temp = Q.front();
        Q.pop();
        if (temp->leftChild) { //若当前层节点有孩子，则孩子进队
          Q.push(temp->leftChild);
        }
        if (temp->rightChild) {
          Q.push(temp->rightChild);
        }
        R.push(temp->data); //每层的节点值存入R中
      }
      level++;
      cout << level << "\t" << curr << "\t";
      if (!R.empty()) {
        cout << R.front();
        R.pop();
        while (!R.empty()) {
          cout << " " << R.front();
          R.pop();
        }
        cout << endl;
      }
    }
  }

  //该方法对于ABC##DE#G##F###是错误的
  // int gainCurrLevelNodes(TreeNode<T> *rootnode,int k){
  //			if(rootnode==NULL || k == 0){
  //				return 0;
  //			}
  //			if(k==1){
  //				cout<<"k==1:"<<rootnode->data<<" "<<endl;
  //				return 1;
  //			}
  //
  //
  //				return
  // gainCurrLevelNodes(root->leftChild,k-1)+gainCurrLevelNodes(root->rightChild,k-1);
  //
  //			}
};
///*非递归实现求二叉树第k层的节点数*/

//	int COUNT_tree(Tnode *root, int depth, int k, int *number) {
//				if (root == NULL)
//					return 0;
//				if (depth == k) {
//					(*number)++;
//				}
//				COUNT(root->Lchild, depth + 1, k, number);
//				COUNT(root->Rchild, depth + 1, k, number);
//				return *number;
//			}

/*int  GetBTreeKthLevelNodesTotal( BTreeNode_t *pRoot, int KthLevel){
    if( pRoot == NULL || KthLevel <= 0 )
        return 0;
    if( pRoot != NULL && KthLevel == 1 )
        return 1;

    return (GetBTreeKthLevelNodesTotal( pRoot->m_pLeft, KthLevel-1) +
GetBTreeKthLevelNodesTotal( pRoot->m_pRight, KthLevel - 1 ) );
}
*/
//输出广义表
template <class T> void BinTree<T>::tablePrint(TreeNode<T> *node) {
  if (node != NULL) {
    cout << node->data;
    if (node->leftChild != NULL || node->rightChild != NULL) {
      cout << "(";
      tablePrint(node->leftChild);
      cout << ",";
      if (node->rightChild != NULL) {
        tablePrint(node->rightChild);
      }
      cout << ")";
    }
  }
}

//文件输入前序流创建树
template <class T>
void BinTree<T>::inputFilePreRecursion(ifstream &in, TreeNode<T> *&subtree) {
  T item;
  if (!in.eof()) {
    in >> item;
    if (item != refValue) {
      subtree = new TreeNode<T>(item);
      inputFilePreRecursion(in, subtree->leftChild);
      inputFilePreRecursion(in, subtree->rightChild);
    } else {
      subtree = NULL;
    }
  }
}
//使用栈实现非递归前序建立二叉树
template <class T> void BinTree<T>::createBinTree(string &str) {
  stack<TreeNode<T> *> S;
  root = new TreeNode<T>(str[0]); // 第一个字符作为根节点
  S.push(root);
  int k = 1;
  while (!S.empty()) {
    if (S.top()->leftChild == NULL &&
        str[k - 1] !=
            '#') { //前一个字符不为 #，前一次左子女为 NULL，说明为根节点
      if (str[k] != '#') { //可以建立左子女
        TreeNode<T> *left = new TreeNode<T>(str[k]);
        S.top()->leftChild = left;
        S.push(left);
      }
      k++;
    } else {
      if (S.top()->rightChild == NULL) { //前一次右子女为空
        if (str[k] != '#') {             //可以建立右子女
          TreeNode<T> *right = new TreeNode<T>(str[k]);
          S.top()->rightChild = right;
          S.push(right);
        } else { //若是 # ，则弹出
          S.pop();
        }
        k++;
      } else { //右子女不为 NULL，则两个子女连入完毕，退栈
        S.pop();
      }
    }
  }
}

//删除指定节点
template <class T> bool BinTree<T>::removeData(T x) {
  TreeNode<T> *curr, *parent, *p = find(x); //查找要删除的节点
  if (p == NULL) {
    return 0;
  }
  curr = p;
  queue<TreeNode<T> *> Q;
  Q.push(curr);
  while (!Q.empty()) {
    curr = Q.front();
    Q.pop();
    if (curr->leftChild != NULL) {
      Q.push(curr->leftChild);
    }
    if (curr->rightChild != NULL) {
      Q.push(curr->rightChild);
    }
  }
  if (curr == root) {
    delete root;
    root = NULL;
  } else {
    p->data = curr->data;
    parent = getParent(curr);
    if (parent->leftChild == curr) {
      parent->leftChild = NULL;
    } else {
      parent->rightChild = NULL;
    }
    delete curr;
  }
  return 1;
}

//计算 节点 X 所处的层次
template <class T> int BinTree<T>::nodeLevel(TreeNode<T> *node, T x, int h) {
  if (node == NULL) {
    return 0;
  } else if (node->data == x) {
    return h;
  } else {
    int l = nodeLevel(node->leftChild, x, h + 1);
    if (l != 0) {
      return l;
    } else {
      return nodeLevel(node->rightChild, x, h + 1);
    }
  }
}

//广义表建立二叉树，字符串参数
//算法思想：
// 1.若读取的是一个字母，则为其建立一个新的节点，并用k=1表示左子女，k=2表示右子女，将其链接到父节点
// 2.若是左括号"("，表示子表的开始，将k置为1，若是右括号")"，表示子表的结束
// 3.若是逗号","表示以左子女为根的子树处理完毕，接着应处理以右子女为根的子树，并将k置为2
// 4.不断读取每一个字符，直到读取结束符"#"为止
//算法中使用栈，进入子表之前，先将根节点进栈，用来给括号内的子女链接上，在子表处理完之后退栈
template <class T> void BinTree<T>::createTableTree(string &str) {
  stack<TreeNode<T> *> s;
  TreeNode<T> *p, *t;
  root = NULL;
  unsigned int k;
  for (int i = 0; str[i] != refValue; i++) {
    switch (str[i]) {
    case '(':
      s.push(p);
      k = 1;
      break;
    case ')':
      s.pop();
      break;
    case ',':
      k = 2;
      break;
    default:
      p = new TreeNode<T>(str[i]);
      if (root == NULL)
        root = p;
      else if (k == 1) {
        t = s.top();
        t->leftChild = p;
      } else {
        t = s.top();
        t->rightChild = p;
      }
    }
  }
}

//利用队列实现非递归查找
template <class T>
TreeNode<T> *BinTree<T>::find(TreeNode<T> *subtree,
                              const T &x) { // a(b(c,d),e(f,g))#
  TreeNode<T> *p = subtree;
  queue<TreeNode<T> *> Q;
  Q.push(p);
  while (!Q.empty()) {
    p = Q.front();
    Q.pop();
    if (p != NULL && p->data == x) {
      return p;
    }
    if (p->leftChild != NULL) {
      Q.push(p->leftChild);
    }
    if (p->rightChild != NULL) {
      Q.push(p->rightChild);
    }
  }
  return NULL;
}

//递归查找
// TreeNode<T> *BinTree<T>::find(TreeNode<T> *subtree, const T &x) {
// //a(b(c,d),e(f,g))#
//		if(subtree==NULL){
//			return NULL;
//		}
//		if(subtree->data==x){
//			return subtree;
//		}
//		TreeNode<T> *p1 = find(subtree->leftChild,x);
//		if(p1!=NULL){
//			return p1;
//		}
//		TreeNode<T> *p2 = find(subtree->rightChild,x);
//		if(p2!=NULL){
//					return p2;
//			}
//		return NULL;
//	}

//递归方法插入一个树节点
template <class T> void BinTree<T>::insert(TreeNode<T> *&subtree, const T &x) {
  if (subtree->leftChild == NULL) {
    TreeNode<T> *newNode = new TreeNode<T>(x);
    subtree->leftChild = newNode;
  } else if (subtree->rightChild == NULL) {
    TreeNode<T> *newNode = new TreeNode<T>(x);
    subtree->rightChild = newNode;
  } else {
    insert(subtree->leftChild, x);
  }
}
//非递归使用队列方法插入一个树节点
// template<class T>
// void  BinTree<T>::insert(TreeNode<T> *&subtree,const T &x) {
// TreeNode<T> *p = subTree;
//	queue<TreeNode<T> * > Q;
//	Q.push(p);
//	while(!Q.empty()){
//		p = Q.front();
//		Q.pop();
//		if(p->leftChild!=NULL){
//			Q.push(p->leftChild);
//		}
//		if(p->rightChild!=NULL){
//			Q.push(p->rightChild);
//		}
//
//	}
//}

//二叉树层次遍历
template <class T> void BinTree<T>::levelOrder(void (*visit)(TreeNode<T> *p)) {
  queue<TreeNode<T> *> Q;
  TreeNode<T> *p = root;
  if (root == NULL) {
    return;
  }
  int curr = 1, next = 0;
  int level = 1;
  Q.push(p);
  cout << endl << "第" << level << "层节点总数：" << curr << endl;
  cout << "节点：";
  while (!Q.empty()) {
    p = Q.front();
    Q.pop();
    visit(p);
    curr--;
    if (p->leftChild != NULL) {
      Q.push(p->leftChild);
      next++;
    }
    if (p->rightChild != NULL) {
      Q.push(p->rightChild);
      next++;
    }
    if (curr == 0) {
      level++;
      curr = next;
      next = 0;
      if (curr != 0) { // curr==0则节点为 0
        cout << endl << "第" << level << "层节点总数：" << curr << endl;
        cout << "节点：";
      }
    }
  }
  cout << endl;
}

//删除二叉树所有节点
template <class T> void BinTree<T>::destroy(TreeNode<T> *&subtree) {
  if (subtree != NULL) {
    destroy(subtree->leftChild);
    destroy(subtree->rightChild);
    delete subtree;
  }
}

//返回指定节点的父节点
template <class T>
TreeNode<T> *
BinTree<T>::getParent(TreeNode<T> *subtree,
                      TreeNode<T> *curr) { //获取当前节点curr的父节点
  if (subtree == NULL || curr == NULL) {
    return NULL;
  }
  if (subtree->leftChild == curr || subtree->rightChild == curr) {
    return subtree;
  }
  TreeNode<T> *p;
  if ((p = getParent(subtree->leftChild, curr)) != NULL) {
    return p;
  } else {
    return getParent(subtree->rightChild, curr);
  }
}

//前序遍历输出所有节点
template <class T>
void BinTree<T>::Traverse(TreeNode<T> *subtree, ostream &out) {
  if (subtree != NULL) {
    out << subtree->data << " ";
    Traverse(subtree->leftChild, out);
    Traverse(subtree->rightChild, out);
  }
}

//输入流创建树
template <class T>
void BinTree<T>::createIstreamBinTree(istream &in, TreeNode<T> *&subtree) {
  stack<TreeNode<T> *> s;
  subtree = NULL;
  TreeNode<T> *p, *t;
  unsigned int k;
  T ch;
  in >> ch; 
  //虽然是模板类，但是目前只支持字符型，不然会报错
  while (ch != refValue) {
    switch (ch) {
    case '(':
      s.push(p);
      k = 1;
      break;
    case ')':
      s.pop();
      break;
    case ',':
      k = 2;
      break;
    default:
      p = new TreeNode<T>(ch);
      if (subtree == NULL)
        subtree = p;
      else if (k == 1) {
        t = s.top();
        t->leftChild = p;
      } else {
        t = s.top();
        t->rightChild = p;
      }
    }
    in >> ch;
  }
}

//中序遍历
template <class T>
void BinTree<T>::inOrder(TreeNode<T> *subtree,
                         void (*visit)(TreeNode<T> *p)) { //中序遍历
  if (subtree != NULL) {
    inOrder(subtree->leftChild, visit);
    visit(subtree);
    inOrder(subtree->rightChild, visit);
  }
}

//前序遍历
template <class T>
void BinTree<T>::preOrder(TreeNode<T> *subtree, void (*visit)(TreeNode<T> *p)) {
  if (subtree != NULL) {
    visit(subtree);
    preOrder(subtree->leftChild, visit);
    preOrder(subtree->rightChild, visit);
  }
}

//后序遍历
template <class T>
void BinTree<T>::postOrder(TreeNode<T> *subtree,
                           void (*visit)(TreeNode<T> *p)) {
  if (subtree != NULL) {
    postOrder(subtree->leftChild, visit);
    postOrder(subtree->rightChild, visit);
    visit(subtree);
  }
}

//返回树的大小
template <class T> int BinTree<T>::getSize(TreeNode<T> *subtree) {
  if (subtree == NULL) {
    return 0;
  } else {
    return 1 + getSize(subtree->leftChild) + getSize(subtree->rightChild);
  }
}

//返回树的深度
template <class T> int BinTree<T>::getHeight(TreeNode<T> *subtree) {
  if (subtree == NULL) {
    return 0;
  } else {
    int i = getHeight(subtree->leftChild);
    int j = getHeight(subtree->rightChild);
    return (i < j) ? j + 1 : i + 1;
  }
}

//复制树
template <class T> TreeNode<T> *BinTree<T>::copy(TreeNode<T> *subtree) {
  if (subtree == NULL) {
    return NULL;
  }
  TreeNode<T> *temp = new TreeNode<T>;
  temp->data = subtree->data;
  temp->leftChild = copy(subtree->leftChild);
  temp->rightChild = copy(subtree->rightChild);
  return temp;
}

//非成员函数重载，比较两棵树树是否相等
template <class T> bool operator==(BinTree<T> &s, BinTree<T> &t) {
  return (equal(s.root, t.root)) ? 1 : 0;
}
template <class T> bool equal(TreeNode<T> &a, TreeNode<T> &b) {
  if (a == NULL && b == NULL) {
    return 1;
  }
  if (a != NULL && a != NULL && a->data == b->data &&
      equal(a->leftChild, b->leftChild) &&
      equal(a->rightChild, b->rightChild)) {
    return 1;
  }
  return 0;
}

//返回度数为 1 的节点个数
template <class T> int BinTree<T>::degree_1(TreeNode<T> *t) {
  if (t == NULL) {
    return 0;
  }
  if (t->leftChild != NULL && t->rightChild == NULL ||
      t->leftChild == NULL && t->rightChild != NULL) {
    return 1 + degree_1(t->leftChild) + degree_1(t->rightChild);
  } else {
    return degree_1(t->leftChild) + degree_1(t->rightChild);
  }
}

返回度数为 2 的节点个数
template <class T> int BinTree<T>::degree_2(TreeNode<T> *t) {
  if (t == NULL) {
    return 0;
  }
  if (t->leftChild != NULL && t->rightChild != NULL) {
    return 1 + degree_2(t->leftChild) + degree_2(t->rightChild);
  } else {
    return degree_2(t->leftChild) + degree_2(t->rightChild);
  }
}

//删除树的叶子节点
template <class T> void BinTree<T>::delLeafNode(TreeNode<T> *&t) {
  if (t == NULL) {
    return;
  }
  if (t->leftChild == NULL && t->rightChild == NULL) {
    delete t;
    t = NULL;
  } else {
    delLeafNode(t->leftChild);
    delLeafNode(t->rightChild);
  }
}

// visit函数指针可调用的输出 函数
template <class T> void print(TreeNode<T> *node) { //非类成员输出函数
  cout << node->data << " ";
}
void binaryTree_test() {

  cout << "【二叉树】" << endl;
  char ref = '#';
  BinTree<char> p(ref);

  //	方式一：以前序序列建立二叉树

  //	string ss="ABC##DE#G##F###";
  //	cout<<"1.前序序列建立二叉树"<<endl;
  //	cout<<ss<<endl;
  //	p.createBinTree(ss);
  //	cout<<endl;

  //	方式二：输入广义表建立二叉树
  //	输入例子：
  //	a(b(c,d),e(f,g))#
  //  A(B(C(H(L,M),J),D(E(,G),F)),A)#

  //	cout<<"以输入广义表的方式建立二叉树：";
  //	cin>>p;

  //	方式三：广义表字符串建立二叉树
  cout << "1.广义表建立二叉树" << endl;
  string str = "A(B(C(H(L,M),J),D(E(,G),F)),A)#";
  cout << str << endl << endl;
  // A(B(C(H(L,M),J),D(E(,G),F)),A)#
  p.createTableTree(str);

  cout << "2.遍历输出" << endl;

  cout << "前序遍历" << endl;
  p.preOrder(print);
  cout << endl << endl;

  cout << "中序遍历" << endl;
  p.inOrder(print);
  cout << endl << endl;

  cout << "后序遍历" << endl;
  p.postOrder(print);
  cout << endl << endl;

  cout << "3.树的深度：" << p.getHeight() << endl << endl;

  cout << "4.节点数量：" << p.getSize() << endl << endl;

  cout << "5.度数为1的节点数：" << p.degree_1() << endl << endl;
  cout << "6.度数为2的节点数：" << p.degree_2() << endl << endl;

  //	查找节点所处层次
  cout << "7.查找指定节点所处层次、同一层次节点数量" << endl << endl;
  char c[] = "abcLMPQCKABCDEF";
  int k = 0;
  cout << "节点\t层次\t数量" << endl;
  while (c[k] != '\0') {
    cout << c[k] << "\t";
    TreeNode<char> *curr = p.find(c[k]);
    if (curr != NULL) {
      cout << p.nodeLevel(curr->data) << "\t";
      cout << p.gainCurrLevelNodes(curr->data) << endl;
    } else {
      cout << "" << endl;
    }
    k++;
  }

  cout << "8.输出广义表" << endl;
  p.tablePrint();
  cout << endl << endl;

  cout << "9.层次遍历" << endl;
  p.levelOrder(print);
  cout << endl << endl;

  cout << "10.删除叶子节点后层次遍历" << endl;
  p.delLeafNode();
  p.queueLevelOrder(p.getRoot());
  cout << endl << endl;

  cout << "11.复制构造函数调用" << endl;
  BinTree<char> q = p;
  cout << "前序输出：" << q;
  cout << "树深度：" << p.getHeight() << endl;
  cout << endl;

  cout << "12.自动插入节点" << endl;
  string node = "1234567890HIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
  cout << "插入" << node.length() << "个节点" << endl;
  int i;
  for (i = 0; i < node.length(); i++) {
    //		cin>>ch;
    q.insert(node[i]);
    cout << node[i] << " ";
    if (i % 10 == 9) {
      cout << endl;
    }
  }
  cout << endl << endl;

  cout << "13.查看插入后的所有节点" << endl;
  cout << "输出节点" << endl;
  cout << q << endl;

  i = 50;
  cout << "14.删除指定节点" << endl;
  cout << "删除操作" << i << "次" << endl;
  cout << "删除"
       << "\t"
       << "执行结果" << endl;
  srand(time(0));
  while (i--) {
    char del = node[rand() % node.length()];
    cout << del << "\t" << q.removeData(del) << endl;
  }
  cout << "15.删除后查看结果" << endl;
  cout << "查看删除后剩余节点" << endl;
  cout << q << endl;
  cout << "深度：" << q.getHeight() << endl;
  cout << "节点数量：" << q.getSize() << endl;
  cout << endl;
}
//文件读取
void BinaryTree_file_read() {
  cout << "【二叉树】" << endl;
  char ref = '#';
  BinTree<char> p(ref);
  //文件输入
  ifstream f("tree.txt"); // ABC##DE#G##F###
  if (f) {
    cout << "文件读取成功" << endl;
    p.inputFilePreRecursion(f);
  }
  cout << "输出节点" << endl;
  cout << p;
  cout << "树的深度：" << p.getHeight() << endl;
  //	插入节点
  char ch;
  int i;
  string node = "1234567890HIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
  const int N = 100;
  cout << "插入" << node.length() << "个节点" << endl;

  for (i = 0; i < node.length(); i++) {
    // cin>>ch;
    p.insert(node[i]);
  }
  cout << "输出节点" << endl;
  cout << p;
  cout << "树的深度：" << p.getHeight() << endl;
  cout << "输出广义表" << endl;
  p.tablePrint();
  //删除树节点
  int j = 3;
  while (j--) {
    char del;
    cout << "删除节点:";
    cin >> del;
    cout << "是否成功：" << p.removeData(del) << endl;
    cout << p;
  }
}

int main() {
  cout << "xxxxxx" << endl;
  binaryTree_test();
  //	test_file_read();
  return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900