本文共 4958 字，大约阅读时间需要 16 分钟。

#pragma once#include
   
    #include
    
     #include
     
      #include
      
       using namespace std;template
       
        struct BinaryTreeNode{    T _data;    BinaryTreeNode
        
         * _left; BinaryTreeNode
         
          * _right; BinaryTreeNode(const T& x) :_data(x) , _left(NULL) , _right(NULL) {}};template
          
           class BinaryTree{ typedef BinaryTreeNode
           
             Node;public: BinaryTree() :_root(NULL) {} BinaryTree(T *p, size_t n, const T& invalid) { size_t index = 0; _root = _Create(p, n, invalid, index); } //前中后序递归遍历 void Prevorder() { _PrevOrder(_root); cout << endl; } void Inorder() { _Inorder(_root); cout << endl; } void Postorder() { _Postorder(_root); cout << endl; } //前中后序非递归遍历 void PrevOrder() { _PrevOrder(_root); cout << endl; } void InOrder() { _InOrder(_root); cout << endl; } void PostOrder() { _PostOrder(_root); cout << endl; } //销毁一棵树 void Destory() { _Destory(_root); } //二叉树所有节点 size_t BinaryTree_size() { return _BinaryTree_size(_root); } //二叉树叶子节点 size_t Leafsize() { return _Leafsize(_root); } //第K层节点 size_t GetKLevelSize(size_t k) { return _GetKLevelSize(_root, k); } //判断一个节点是否在树中 bool IsIntree(int k) { return _IsIntree(_root,k); } //层序遍历，利用queue void LevelOrder() { _LevelOrder(_root); cout << endl; } //是否完全二叉树 bool IsCompleteTree() { return _IsCompleteTree(_root); }protected: //递归前中后序遍历 void _Prevorder(Node* root) { if (root == NULL) return; else { cout << root->_data << ""; _Prevorder(root->_left); _Prevorder(root->_right); return; } } void _Inorder(Node* root) { if (root == NULL) { return; } else { _Inorder(root->_left); cout << root->_data << ""; _Inorder(root->_right); return; } } void _Postorder(Node* root) { if (root == NULL) return; else { _Postorder(root->_left); _Postorder(root->_right); cout << root->_data << ""; return; } } //非递归遍历 void _PrevOrder(Node* root) { if (root == NULL) { return; } else { stack
            
              s; Node* cur = root; while (cur || !s.empty()) { while (cur) { cout << cur->_data << ""; s.push(cur); cur = cur->_left; } Node* top = s.top(); s.pop(); cur = top->_right; } return; } } void _InOrder(Node* root) { if (root == NULL) { return; } else { stack
             
               s; Node* cur = root; while (cur || !s.empty()) { while (cur) { s.push(cur); cur = cur->_left; } Node* top = s.top(); cout << top->_data << ""; s.pop(); cur = top->_right; } } } void _PostOrder(Node* root) { if (root == NULL) { return; } else { Node* prev = NULL; Node* cur = root; stack
              
                s; while (cur || !s.empty()) { while (cur) { s.push(cur); cur = cur->_left; } Node* top = s.top(); if (NULL == top->_right || top->_right == prev) { cout << top->_data << ""; prev = top; s.pop(); } else { cur = top->_right; } } } } //销毁 void _Destory(Node* root) { if (root == NULL) { return; } else { _Destroy(root->_left); _Destroy(root->_right); delete root; } } //二叉树所有节点个数 size_t _BinaryTree_size(Node* root) { if (root == NULL) { return 0; } else { return _BinaryTree_size(root->_left) + _BinaryTree_size(root->_right) + 1; } } //叶子节点个数 size_t _Leafsize(Node *root) { if (root == NULL) { return 0; } if (root->_left == NULL&&root->_right == NULL) { return 1; } return _Leafsize(root->_left) + _Leafsize(root->_right); } //第k层节点数 size_t _GetKLevelSize(Node* root, size_t n) { if (root == NULL || n == 0) { return 0; } if (n == 1) { return 1; } return _GetKLevelSize(root->_left,n-1) + _GetKLevelSize(root->_right,n-1); } //判断是否在树中 bool _IsIntree(Node* root, int n) { if (root == NULL) { return false; } if (root->_data == n) { return true; } return _IsIntree(root->_left, n) || _IsIntree(root->_right, n); } //层序遍历 void _LevelOrder(Node* root) { if (root == NULL) { return; } else { queue
               
                 q; Node* cur = root; q.push(cur); while (!q.empty()) { Node* front = q.front(); q.pop(); cout << front->_data << ""; if (front->_left) q.push(front->_left); if (front->_right) q.push(front->_right); } } } //是否完全二叉树 bool _IsCompleteTree(Node* root) { queue
                
                  q; if (root) { q.push(root); bool tag = true; while (!q.empty()) { Node* front = q.front(); if (front->_left) { if (tag == false) { return false; } else { q.push(front->_left); } } else { tag = false; } if (front->_right) { if (tag == false) { return false; } else { q.push(front->_right); } } else { tag = false; } } return true; } return true; }private: Node* _root; Node* _Create(T* p, size_t n, const T& invalid, size_t& index) { Node* root = NULL; if (index < n&&p[index] != invalid) { root = new Node(p[index]); root->_left = _Create(p, n, invalid, ++index); root->_right = _Create(p, n, invalid, ++index); } return root; }};//测试代码#define _CRT_SECURE_NO_WARNINGS 1#include"BinaryTreee.h"void TestTree1(){ int array[] = { 1, 2, 4, '#', '#', 5, '#', '#', 3, 6, '#', '#', 7,'#','#' }; BinaryTree
                 
                   t1(array, sizeof(array) / sizeof(array[0]), '#'); t1.Prevorder(); t1.Inorder(); t1.Postorder(); t1.PrevOrder(); t1.InOrder(); t1.PostOrder(); /*t1.Destory();*/ t1.LevelOrder(); bool size = t1.IsCompleteTree(); //size_t size = t1.GetKLevelSize(2); cout << size << endl;}int main(){ TestTree1(); system("pause"); return 0;}
                 
                
               
              
             
            
           
          
         
        
       
      
     
    
   

转载地址：http://brlai.baihongyu.com/