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

二叉树

在计算机科学中，二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用于实现二叉查找树和二叉堆。

二叉树的每个结点至多只有二棵子树(不存在度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒。二叉树的第i层至多有2^{i-1}个结点；深度为k的二叉树至多有2^k-1个结点；对任何一棵二叉树T，如果其终端结点数为n_0，度为2的结点数为n_2，则n_0=n_2+1。

一棵深度为k，且有2^k-1个节点称之为满二叉树；深度为k，有n个节点的二叉树，当且仅当其每一个节点都与深度为k的满二叉树中，序号为1至n的节点对应时，称之为完全二叉树。

二叉树的五种形式

在阅读的大部分书籍中，二叉树的实现都使用的是递归的方法，当然我也不例外：

二叉树的遍历是一个大问题，下面我将用递归法与非递归法分别实现

//前序    void _PrevOrder(Node* root)    {        if (root == NULL)            return;        cout << root->_data << " ";        _PrevOrder(root->_left);        _PrevOrder(root->_right);    }//中序    void _InOrder(Node* root)    {        if (root == NULL)            return;        _InOrder(root->_left);        cout << root->_data << " ";        _InOrder(root->_right);    }//后序    void _PostOrder(Node* root)    {        if (root == NULL)            return;        _PostOrder(root->_left);        _PostOrder(root->_right);        cout << root->_data << " ";    }

非递归法：

void LevelOrder()//层序遍历    {        if (_root == NULL)            return;        queue
   
    
     *> q;        q.push(_root);        while (!q.empty())        {            BinaryTreeNode
     
      * root = q.front();            if (root->_left)            {                q.push(root->_left);            }            if (root->_right)            {                q.push(root->_right);            }            cout << root->_data << " ";            q.pop();        }        cout << endl;    }    //层序使用的是队列的先进先出性质，将每一层的节点从左到右分别遍历打印//方法一：    void PrevOrder_NonR()//前序遍历非递归    {        stack
      
        s;        if (_root)            s.push(_root);        while (!s.empty())        {            Node* root = s.top();            cout << root->_data << " ";            s.pop();            if (root->_right)            {                s.push(root->_right);            }            if (root->_left)            {                s.push(root->_left);            }        }        cout << endl;    }//方法二：void PrevOrder_NonR()//前序便利非递归    {        cout << "PrevOrder_NonR: ";        stack
       
         s;        Node* root = _root;        while (!s.empty()||root!=NULL)        {            while (root)            {                cout << root->_data << " ";                s.push(root);                root = root->_left;            }            while (!s.empty())            {                root = s.top();                s.pop();                root = root->_right;                break;            }        }        cout << endl;    }    void InOrder_NonR()//中序遍历非递归    {        stack
        
          s; Node* root = _root; while (root != NULL || !s.empty()) { while (root) { s.push(root); root = root->_left; } while (!s.empty()) { root = s.top(); cout << root->_data << " "; s.pop(); root = root->_right; } } cout << endl; } void PostOrder_NonR()//后序遍历非递归 { stack
         
           s; Node* cur = _root; Node* prev = NULL; while (cur || !s.empty()) { // 入栈做孩子节点 while (cur) { s.push(cur); cur = cur->_left; } // 2.右节点为空/之前右节点已经访问过了的时候访问当前的栈顶节点 Node* top = s.top(); if (top->_right == NULL || prev == top->_right) { cout << top->_data << " "; s.pop(); prev = top; } else { cur = top->_right; } } cout << endl; }
         
        
       
      
     
    
   

完整代码

#pragma once#include
   
    #include
    
     using namespace std;#include
     
      #include
      
       template
       
        struct BinaryTreeNode{    BinaryTreeNode
        
         * _left; BinaryTreeNode
         
          * _right; T _data; BinaryTreeNode(const T& x) :_data(x) , _left(NULL) , _right(NULL) {}};template
          
           class BinaryTree{ typedef BinaryTreeNode
           
             Node;public: BinaryTree() :_root(NULL) {} BinaryTree(const T* arr, size_t size, const T& invalid)//默认参数列表，构造函数,(数组，大小，非法值) { size_t index = 0; _CreateTree(_root, arr, size, index, invalid);//（根,数组，大小，非法值） } BinaryTree(BinaryTree
            
             & t)//拷贝构造函数 { this->_root = _CopyBinaryTree(t._root); } /*BinaryTree
             
              & operator=(BinaryTree
              
                t) { if (this != &t) { this->Destory(); this->_root = _CopyBinaryTree(t._root); } return *this; }*/ BinaryTree
               
                & operator=(BinaryTree
                
                  t) { swap(_root, t._root); return *this; } ~BinaryTree()//析构函数 { Destory(); } void PrevOrder()//递归前置遍历 { cout << "PrevOrder: "; _PrevOrder(_root); cout << endl; } void InOrder()//递归中序遍历 { cout << "InOrder: "; _InOrder(_root); cout << endl; } void PostOrder()//递归后序遍历 { cout << "PostOrder: "; _PostOrder(_root); cout << endl; } void LevelOrder()//层序遍历 { cout << "LeveOrder: "; if (_root == NULL) return; queue
                 
                  
                   *> q; q.push(_root); while (!q.empty()) { BinaryTreeNode
                   
                    * root = q.front(); if (root->_left) { q.push(root->_left); } if (root->_right) { q.push(root->_right); } cout << root->_data << " "; q.pop(); } cout << endl; } void PrevOrder_NonR()//前序便利非递归 { cout << "PrevOrder_NonR: "; stack
                    
                      s; if (_root) s.push(_root); while (!s.empty()) { Node* root = s.top(); cout << root->_data << " "; s.pop(); if (root->_right) { s.push(root->_right); } if (root->_left) { s.push(root->_left); } } cout << endl; } void InOrder_NonR()//中序遍历非递归 { cout << "InOrder_NoR: "; stack
                     
                       s; Node* root = _root; while (root != NULL || !s.empty()) { while (root) { s.push(root); root = root->_left; } while (!s.empty()) { root = s.top(); cout << root->_data << " "; s.pop(); root = root->_right; } } cout << endl; } void PostOrder_NonR()//后序遍历非递归 { cout << "PastOrder_NonR: "; stack
                      
                        s; Node* cur = _root; Node* prev = NULL; while (cur || !s.empty()) { // 入栈做孩子节点 while (cur) { s.push(cur); cur = cur->_left; } // 2.右节点为空/之前右节点已经访问过了的时候访问当前的栈顶节点 Node* top = s.top(); if (top->_right == NULL || prev == top->_right) { cout << top->_data << " "; s.pop(); prev = top; } else { cur = top->_right; } } cout << endl; } int Size()//节点个数 { return _Size(_root); } int Depth()//树的深度 { return _Depth(_root); } int LeafSize()//叶子节点的个数 { size_t count = 0; return _LeafSize(_root, count); } int GetKLevel(size_t k)//第K层节点个数 { size_t count = 0; return _GetKlevel(_root, k, count); } void Destory() { _Destory(_root); _root = NULL; }protected: void _CreateTree(BinaryTreeNode
                       
                        *& root, const T array[], size_t size, size_t& index, const T& invalid) { if (index < size && array[index] != invalid) { root = new BinaryTreeNode
                        
                         (array[index]); _CreateTree(root->_left, array, size, ++index, invalid); _CreateTree(root->_right, array, size, ++index, invalid); } } Node* _CopyBinaryTree(Node* root) { Node* newRoot = NULL; if (root) { newRoot = new Node(root->_data); newRoot->_left = _CopyBinaryTree(root->_left); newRoot->_right = _CopyBinaryTree(root->_right); } return newRoot; } void _Destory(Node* root) { if (root == NULL) return; _Destory(root->_left); _Destory(root->_right); delete root; } void _PrevOrder(Node* root) { if (root == NULL) return; cout << root->_data << " "; _PrevOrder(root->_left); _PrevOrder(root->_right); } void _InOrder(Node* root) { if (root == NULL) return; _InOrder(root->_left); cout << root->_data << " "; _InOrder(root->_right); } void _PostOrder(Node* root) { if (root == NULL) return; _PostOrder(root->_left); _PostOrder(root->_right); cout << root->_data << " "; } int _Size(Node* root) { if (root == NULL) { return 0; } return _Size(root->_left) + _Size(root->_right) + 1; } int _Depth(Node* root) { if (root == NULL) { return 0; } int leftDepth = _Depth(root->_left) + 1; int rightDepth = _Depth(root->_right) + 1; return leftDepth > rightDepth ? leftDepth : rightDepth; } int _LeafSize(Node* root, size_t& count) { if (root) { if ((root->_left == NULL) && (root->_right == NULL)) { count++; } _LeafSize(root->_left, count); _LeafSize(root->_right, count); } return count; } int _GetKlevel(Node* root, size_t k, size_t& count) { if (root) { if (1 == k) { count++; } else { _GetKlevel(root->_left, k - 1, count); _GetKlevel(root->_right, k - 1, count); } } return count; }protected: Node* _root;};
                        
                       
                      
                     
                    
                   
                  
                 
                
               
              
             
            
           
          
         
        
       
      
     
    
   

测试用例

#include"BinaryTree.h"void TestBinaryTree(){    cout << "TestBinaryTree:" << endl;    int array[20] = { 1, 2, 3, '#', '#', 4, '#', '#', 5, 6 };    BinaryTree
   
     tree(array, 10,'#');    tree.PrevOrder();    tree.PrevOrder();    tree.PrevOrder_NonR();    tree.InOrder();    tree.InOrder_NonR();    tree.PostOrder();    tree.PostOrder_NonR();    tree.LevelOrder();    cout << "Height:" << tree.Depth() << endl;    cout << "LeafSzie:" << tree.LeafSize() << endl;    cout << "KLeveSzie of 2:" << tree.GetKLevel(10) << endl;    cout << "Size:" << tree.Size() << endl;    BinaryTree
    
      treeCopy1 = tree;    treeCopy1.PrevOrder();    BinaryTree
     
       treeCopy2;    treeCopy2 = tree;    treeCopy2.PrevOrder();}int main(){    TestBinaryTree();    system("pause");    return 0;}