歡迎來到Linux教程網
Linux教程網
Linux教程網
Linux教程網
您现在的位置: Linux教程網 >> UnixLinux >  >> Linux編程 >> Linux編程

後序遍歷求解判斷一顆二叉樹是否為平衡二叉樹

題目:輸入一棵二叉樹的根結點,判斷該樹是不是平衡二叉樹。如果某二叉樹中任意結點的左右子樹的深度相差不超過1,那麼它就是一棵平衡二叉樹。

有了求二叉樹的深度的經驗之後再解決這個問題,我們很容易就能想到一個思路:在遍歷樹的每個結點的時候,調用函數TreeDepth得到它的左右子樹的深度。如果每個結點的左右子樹的深度相差都不超過1,按照定義它就是一棵平衡的二叉樹。這種思路對應的代碼如下:
bool IsBalanced(BinaryTreeNode* pRoot)
{
    if(pRoot == NULL)
        return true;
    int left = TreeDepth(pRoot->m_pLeft);
    int right = TreeDepth(pRoot->m_pRight);
    int diff = left - right;
    if(diff > 1 || diff < -1)
        return false;
    return IsBalanced(pRoot->m_pLeft) && IsBalanced(pRoot->m_pRight);
}

上面的代碼固然簡潔,但我們也要注意到由於一個節點會被重復遍歷多次,這種思路的時間效率不高。例如在函數IsBalance中輸入上圖中的二叉樹,首先判斷根結點(值為1的結點)的左右子樹是不是平衡結點。此時我們將往函數TreeDepth輸入左子樹根結點(值為2的結點),需要遍歷結點4、5、7。接下來判斷以值為2的結點為根結點的子樹是不是平衡樹的時候,仍然會遍歷結點4、5、7。毫無疑問,重復遍歷同一個結點會影響性能。接下來我們尋找不需要重復遍歷的算法。
如果我們用後序遍歷的方式遍歷二叉樹的每一個結點,在遍歷到一個結點之前我們已經遍歷了它的左右子樹。只要在遍歷每個結點的時候記錄它的深度(某一結點的深度等於它到葉節點的路徑的長度),我們就可以一邊遍歷一邊判斷每個結點是不是平衡的。
#include<iostream>
#include<stack>
using namespace std;
struct BinaryTreeNode
{
    int data;
    BinaryTreeNode* left;
    BinaryTreeNode* right;
    BinaryTreeNode(int x)
        :data(x)
        , left(NULL)
        , right(NULL)
    {}
};
class BinaryTree
{
protected:
    BinaryTreeNode* _root;
    BinaryTreeNode* _CreateBinaryTree(int* arr, int& index, int size)
    {
        BinaryTreeNode* root = NULL;
        if (index < size&&arr[index] != '#')
        {
            root = new BinaryTreeNode(arr[index]);
            root->left = _CreateBinaryTree(arr, ++index, size);
            root->right = _CreateBinaryTree(arr, ++index, size);
        }
        return root;
    }
     
public:
    BinaryTree()
        :_root(NULL)
    {}
    BinaryTree(int *arr, int size)
    {
        int index = 0;
        _root = _CreateBinaryTree(arr, index, size);
    }
    bool IsBalance()
    {
        int depth = 0;
        return _IsBalance(_root, depth);
    }
    int Height()
    {
        return _Height(_root);
    }
    void PreOrder_Non()
    {
        if (_root == NULL)
            return;
        BinaryTreeNode* cur = _root;
        stack<BinaryTreeNode*> s;
        s.push(_root);
        while (!s.empty())
        {
            cur = s.top();
            printf("%d ", cur->data);
            s.pop();
            if (cur->right)
                s.push(cur->right);
            if (cur->left)
                s.push(cur->left);
        }
        cout << endl;
    }
protected:
    int _Height(BinaryTreeNode* root)
    {
        if (root == NULL)
            return 0;
        int left = _Height(root->left);
        int right = _Height(root->right);
        return left > right ? left + 1 : right + 1;
    }
    bool _IsBalance(BinaryTreeNode* root, int& depth)
    {
        if (root == NULL)
            return true;
        int left, right;
        if (_IsBalance(root->left, left) && _IsBalance(root->right, right))
        {
            int dif = left - right;
            if (dif <= 1 && dif >= -1)
            {
                depth = left > right ? left + 1 : right + 1;
                return true;
            }
        }
        return false;
    }
};
int main()
{
    int a[] = { 1,2,3,'#','#','#'};
    BinaryTree t(a,sizeof(a)/sizeof(a[0]));
     
    t.PreOrder_Non();
    cout<<t.IsBalance()<<endl;
     
    system("pause");
    return 0;
}

在上面的代碼中,我們用後序遍歷的方式遍歷整棵二叉樹。在遍歷某結點的左右子結點之後,我們可以根據它的左右子結點的深度判斷它是不是平衡的,並得到當前結點的深度。當最後遍歷到樹的根結點的時候,也就判斷了整棵二叉樹是不是平衡二叉樹了。

Copyright © Linux教程網 All Rights Reserved