二叉树 C++

代码参考：

http://blog.csdn.net/iqrocket/article/details/8266365

http://blog.csdn.net/luno1/article/details/7951993

二叉树的性质：

1、在二叉树的第 i 层上，至多有 2^i-1 个节点。（i >= 1）
2、深度为 k 的二叉树至多有 2^k -1 个节点（k >= 1）
3、对任何一棵二叉树 T，如果其终端节点数为 n0, 度为2 的节点数为 n2, 则 n0 = n2 +1
证明：分支线总数是 W, 节点总数是 N, 度为1的节点是 n1。 W = N -1
      W = N -1 = n1 + 2*n2
      N = n0 + n1 + n2
      => n0 = n2 + 1

4、具有 N 个结点的完全二叉树的深度为【log N】 + 1. (【X】表示不大于X 的最大整数，底是2)

证明：    2^k-1 -1 < N <= 2^k -1
          2^k-1 <= N < 2^k
          对两边取对数
          k -1 <= log N < k             k = 【log N】 + 1

5、如果对一棵有 N 个结点的完全二叉树（其深度为【log n】+ 1）的结点按层序编号（从第一层到第【log n】+ 1 层，每层从左到右），对任一结点 i （1<= i<=n）有：
a: 如果 i = 1, 则结点 i 是二叉树的根，无双亲；如果 i>1，则其双亲是结点【i/2】
b: 如果2i > n, 则结点 i 无左孩子（结点 i 为叶子结点）；否则其左孩子是结点 2i;
c: 如果2i+1 > n,则结点 i 无右孩子（结点 i 为叶子结点）；否则其左孩子是结点 2i+1;

二叉树类的声明：包括树的建立、递归遍历、非递归遍历、结点总数、叶子节点数、树的高度

#include<iostream>
#include<stack>
#include<queue>
using namespace std;
template<class T>
struct TreeNode
{
    T element;
    TreeNode* rightNode, *leftNode;
};

template<class T>
class BinaryTree
{
public:
    BinaryTree();
    ~BinaryTree();
    TreeNode<T>*GetRoot();
    //递归遍历
    void PreOrder(TreeNode<T>*);
    void Inorder(TreeNode<T>*);
    void PostOrder(TreeNode<T>*);
    //非递归遍历
    void NonPreOrder(TreeNode<T>*);
    void NonInOrder(TreeNode<T>*);
    void NonPostOrder(TreeNode<T>*);
    void LevelOrder(TreeNode<T>*);    //层序遍历

    int BTreeSize(TreeNode<T>*);       //计算树的节点总数
    int BTreeLeaves(TreeNode<T>*);     //计算树的叶子数
     int BTreeHight(TreeNode<T>*);      //计算树的高度

private:
    TreeNode<T>* root;
    TreeNode<T>*Create();
    void Release(TreeNode<T>*root);
};

二叉树中函数的实现：

//获取根结点
template<class T>
TreeNode<T>* BinaryTree<T>::GetRoot()
{
    return root;
}
//构造函数
template<class T>
BinaryTree<T>::BinaryTree()
{
    root = new TreeNode<T>;
    root = Create();
}
//析构函数
template<class T>
BinaryTree<T>::~BinaryTree()
{
    Release(root);
    delete root;
}
//生成树,采用先序遍历的方式生成树
template<class T>
TreeNode<T>* BinaryTree<T>::Create()
{
    char elem;
    cin >> elem;
    TreeNode<T>* node;
    if (elem == '#')
        node = NULL;
    else
    {
        node = new TreeNode<T>;
        node->element = elem;
        node->leftNode = Create();
        node->rightNode = Create();
    }
    return node;
}
//删除结点
template<class T>
void BinaryTree<T>::Release(TreeNode<T>*root)
{
    if (root != NULL)
    {
        Release(root->leftNode);
        Release(root->rightNode);
    }
}
//前序遍历
template<class T>
void BinaryTree<T>::PreOrder(TreeNode<T>*node)
{
    if (node == NULL)
        return;
    else
    {
        cout << node->element<<"  ";
        PreOrder(node->leftNode);
        PreOrder(node->rightNode);
    }
}
//中序遍历
template<class T>
void BinaryTree<T>::Inorder(TreeNode<T>*node)
{
    if (node == NULL)
        return;
    else
    {
        Inorder(node->leftNode);
        cout << node->element << "  ";
        Inorder(node->rightNode);
    }
}
//后序遍历
template<class T>
void BinaryTree<T>::PostOrder(TreeNode<T>*node)
{
    if (node == NULL)
        return;
    else
    {
        PostOrder(node->leftNode);
        PostOrder(node->rightNode);
        cout << node->element<<"  ";
    }
}

template<class T>
void BinaryTree<T>::NonPreOrder(TreeNode<T>*node)
{
    //前序遍历的顺序是：根左右
    stack<TreeNode<T>*>s;
    TreeNode<T>*pNode = node;
    while (pNode != NULL || !s.empty())
    {
        while (pNode != NULL)   //当pNode非空时， 1、打印根节点，并把根结点压入栈    2、将左叶子节点复制给 pNode,
        {
            cout << pNode->element << "  ";
            s.push(pNode);
            pNode = pNode->leftNode;
        }
        if (!s.empty())        //当栈非空时，将栈顶元素的右叶子复制给 pNode
        {
            pNode = s.top();
            s.pop();
            pNode = pNode->rightNode;
        }
    }
}

//非递归中序遍历
template<class T>
void BinaryTree<T>::NonInOrder(TreeNode<T>*node)     
{
    stack<TreeNode<T>*>s;
    TreeNode<T>*pNode = node;
    while ( pNode != NULL || !s.empty())
    {
        while (pNode != NULL)
        {
            s.push(pNode);
            pNode = pNode->leftNode;
        }
        if (!s.empty())
        {
            pNode = s.top();
            cout << pNode->element << "  ";
            s.pop();
            pNode = pNode->rightNode;
        }
    }
}

//非递归后序遍历
template<class T>
void BinaryTree<T>::NonPostOrder(TreeNode<T>*node)
{
    //遍历顺序：左右跟
    /*
         对任一结点，先将其入栈，访问该结点的左节点和右节点。若左右结点均访问过，则访问该节点
    */
    if (node == NULL)
        return;
    stack<TreeNode<T>*>s;
    queue<TreeNode<T>*>q;
    s.push(node);                 //将根结点压入栈
    TreeNode<T>*pre = NULL;
    TreeNode<T>* cur;
    while (!s.empty())
    {
        cur = s.top();
        //上一次访问的是当前节点的左子树
        if (cur->leftNode == NULL&&cur->rightNode == NULL || (pre != NULL) && (pre == cur->leftNode || pre == cur->rightNode))
        {
            cout << cur->element << "  ";
            s.pop();
            pre = cur;
        }
        else
        {
            if (cur->rightNode)
                s.push(cur->rightNode);
            if (cur->leftNode)
                s.push(cur->leftNode);
        }
    }

}

//层序遍历
template<class T>
void BinaryTree<T>::LevelOrder(TreeNode<T>*node)   //层序遍历
{
    TreeNode<T>*pNode = node;
    if (pNode == NULL)
        return;
    //将每次层的叶子节点进入队列
    queue<TreeNode<T>*>q;
    q.push(pNode);
    while (!q.empty())
    {
        pNode = q.front();
        cout << pNode->element << "  ";
        q.pop();
        if (pNode->leftNode)
            q.push(pNode->leftNode);
        if (pNode->rightNode)
            q.push(pNode->rightNode);
    }
}


//求二叉树结点个数的函数  
template<class T>
int BinaryTree<T>::BTreeSize(TreeNode<T>* node)
{
    //二叉树的结点个数为左右子树的高度之和再+1  
    if (node == NULL)
        return 0;
    else
        return 1 + BTreeSize(node->leftNode) + BTreeSize(node->rightNode);
}


//求二叉树叶子结点个数的函数  
template<class T>
int BinaryTree<T>::BTreeLeaves(TreeNode<T>* node)
{
    //当为空时，返回0；当找到叶子时返回1  
    if (node == NULL) 
        return 0;
    else
       if (node->leftNode == 0 && node->rightNode == 0)
            return 1;
       else
           return BTreeLeaves(node->leftNode) + BTreeLeaves(node->rightNode);
}

//求二叉树高度的函数  
template<class T>
int BinaryTree<T>::BTreeHight(TreeNode<T>* node)
{
    if (node == NULL) 
        return 0;
    else
    {
        //二叉树的高度为左右子树的最大者+1  
        int lHei = BTreeHight(node->leftNode);
        int rHei = BTreeHight(node->rightNode);
        return (lHei>rHei) ? lHei + 1 : rHei + 1;
    }
}

View Code

测试代码：输入： A B # D # C # #。树的形式为：

#include<iostream>
#include<string>
#include"BinaryTree.cpp"
using namespace std;

int main()
{
    cout << "请输入节点" << endl;   // A B # D # C # #
    BinaryTree<char>my_tree;
    
    my_tree.PreOrder(my_tree.GetRoot());
    cout << "递归先序遍历" << endl;

    my_tree.Inorder(my_tree.GetRoot());
    cout << "递归中序遍历" << endl;
    
    my_tree.PostOrder(my_tree.GetRoot());
    cout << "递归后序遍历" << endl;

    my_tree.LevelOrder(my_tree.GetRoot());
    cout << "层序遍历" << endl;


    my_tree.NonPreOrder(my_tree.GetRoot());
    cout << "非递归先序遍历" << endl;

    my_tree.NonInOrder(my_tree.GetRoot());
    cout << "非递归中序遍历" << endl;

    my_tree.NonPostOrder(my_tree.GetRoot());
    cout << "非递归后序遍历" << endl;

    cout << "二叉树的节点数是： " << my_tree.BTreeSize(my_tree.GetRoot()) << endl;
    cout << "二叉树的叶子数是: " << my_tree.BTreeLeaves(my_tree.GetRoot()) << endl;
    cout << "二叉树的高度是： " << my_tree.BTreeHight(my_tree.GetRoot()) << endl;

    cout << endl;
    cout << "hello world" << endl;
    system("pause");
    return 0;
}

View Code