欧美一级特黄大片做受成人-亚洲成人一区二区电影-激情熟女一区二区三区-日韩专区欧美专区国产专区

【數(shù)據(jù)結(jié)構(gòu)】二叉樹-創(chuàng)新互聯(lián)

二叉樹概念

10年積累的成都網(wǎng)站建設(shè)、做網(wǎng)站經(jīng)驗，可以快速應(yīng)對客戶對網(wǎng)站的新想法和需求。提供各種問題對應(yīng)的解決方案。讓選擇我們的客戶得到更好、更有力的網(wǎng)絡(luò)服務(wù)。我雖然不認識你，你也不認識我。但先做網(wǎng)站設(shè)計后付款的網(wǎng)站建設(shè)流程，更有山陽免費網(wǎng)站建設(shè)讓你可以放心的選擇與我們合作。


在計算機科學(xué)中，二叉樹是每個節(jié)點最多有兩個子樹的樹結(jié)構(gòu)。通常子樹被稱作“左子樹”（left subtree）和“右子樹”（right subtree）。二叉樹常被用于實現(xiàn)二叉查找樹和二叉堆。

二 叉樹的每個結(jié)點至多只有二棵子樹(不存在度大于2的結(jié)點)，二叉樹的子樹有左右之分，次序不能顛倒。二叉樹的第i層至多有2^{i-1}個結(jié)點；深度為k 的二叉樹至多有2^k-1個結(jié)點；對任何一棵二叉樹T，如果其終端結(jié)點數(shù)為n_0，度為2的結(jié)點數(shù)為n_2，則n_0=n_2+1。

(1)完全二叉樹——若設(shè)二叉樹的高度為h，除第 h 層外，其它各層 (1～h-1) 的結(jié)點數(shù)都達到大個數(shù)，第h層有葉子結(jié)點，并且葉子結(jié)點都是從左到右依次排布，這就是完全二叉樹。

(2)滿二叉樹——除了葉結(jié)點外每一個結(jié)點都有左右子葉且葉子結(jié)點都處在最底層的二叉樹。

二叉樹性質(zhì)

(1) 在非空二叉樹中，第i層的結(jié)點總數(shù)不超過2^(i-1) , i>=1；

(2) 深度為h的二叉樹最多有2^h - 1 個結(jié)點(h>=1)，最少有h個結(jié)點；

(3) 對于任意一棵二叉樹，如果其葉結(jié)點數(shù)為N0，而度數(shù)為2的結(jié)點總數(shù)為N2，則N0=N2+1；

(4) 具有n個結(jié)點的完全二叉樹的深度為log 2 (n+1)    [ log 以2為底的 n+1 ]

存儲結(jié)構(gòu)：順序存儲，鏈?zhǔn)酱鎯?/p>

遍歷方式：前序遍歷，中序遍歷，后序遍歷

前序遍歷：

void _PreOrder(Node* root)
    {
        if (root == NULL)
            return;

        cout << root->_data << " ";
        _PreOrder(root->_left);
        _PreOrder(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 << " ";
    }

此外，對于二叉樹的操作還有：

樹的深度Depth()

樹的大小Size()

葉子結(jié)點的個數(shù)LeafSize()

K層也加點個數(shù) GetKLevel()

實現(xiàn)如下：

Depth()：

size_t _Depth(Node* root)
    {
        if (root == NULL)
            return 0;

        int leftDepth = _Depth(root->_left);
        int rightDepth = _Depth(root->_right);

        return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
    }

Size()：

size_t _Size(Node* root)
    {
        if (root == NULL)
            return 0;
        return _Size(root->_left) + _Size(root->_right) + 1;
    }

LeafSize()：

void _LeafSize(Node* root, size_t& size) // size需傳引用，以保證每次在上次的調(diào)用加值，否則size結(jié)果為0
    {
        if (root == NULL)
            return;
        if (root->_left == NULL && root->_right == NULL)
        {
            ++size;
            return;
        }
        _LeafSize(root->_left,size);
        _LeafSize(root->_right, size);
    }

GetKLevel()：

void _GetKLevel(Node* root, int k,
        size_t level, size_t& kSize)
    {
        if (root == NULL)
        {
            return;
        }

        if (level == k)
        {
            ++kSize;
            return;
        }

        _GetKLevel(root->_left, k, level + 1, kSize);
        _GetKLevel(root->_right, k, level + 1, kSize);
    }

至此，二叉樹的基本操作已經(jīng)完成。

我們發(fā)現(xiàn)在實現(xiàn)二叉樹的前序，中序，后序遍歷時都是利用遞歸的機制，那么非遞歸又是怎么實現(xiàn)的呢？

在此，寫出三種不同遍歷方式的非遞歸方式實現(xiàn)：

前序遍歷（非遞歸）：

void _PreOrder_NoR() 
    {
        stack<Node*> s;
        if (_root)
        {
            s.push(_root);
        }

        while (!s.empty())
        {
            Node* top = s.top();
            cout << top->_data << " ";

            s.pop();

            if (top->_right) // 先壓右樹，后壓左樹
            {
                s.push(top->_right); 
            }
            if (top->_left)
            {
                s.push(top->_left);
            }
        }
    }

中序遍歷（非遞歸）：

void _InOrder_NoR() 
    {
        Node* cur = _root;
        stack<Node*> s;

        while (cur || !s.empty())
        {
            while (cur)
            {
                // 1.壓一棵樹的左路節(jié)點，直到最左節(jié)點
                s.push(cur);
                cur = cur->_left;
            }
             // 2.棧不為空，出棧訪問，并移向右樹，判斷右樹是否為空，后循環(huán)此操作，直至棧為空
            if (!s.empty())
            {
                Node* top = s.top();
                s.pop();
                cout << top->_data << " ";
                cur = top->_right;
            }
        }
    }

后序遍歷（非遞歸）：

void _PostOrder_NoR()
    {
        Node* pre = NULL;
        Node* cur = _root;
        stack<Node*> s;
        while (cur || !s.empty())
        {
            while (cur)
            {
                s.push(cur);
                cur = cur->_left;
            }

            Node* top = s.top();
            if (top->_right == NULL || top->_right == pre)
            {
                cout << top->_data << " ";
                s.pop();
                pre = top;
            }
            else
            {
                cur = top->_right;
            }
        }
    }

發(fā)現(xiàn)，非遞歸的實現(xiàn)是利用棧結(jié)構(gòu)存儲和管理二叉樹的。

附源代碼以及測試代碼：

BinaryTree.h 文件：

#pragma once 

#include <stack>
template <class T>
struct BinaryTreeNode
{
    T _data;
    BinaryTreeNode<T>* _left;
    BinaryTreeNode<T>* _right;

    BinaryTreeNode(const T& x)
        : _data(x)
        , _left(NULL)
        , _right(NULL)
    {}
};

template <class T>
class BinaryTree
{
    typedef BinaryTreeNode<T> Node;
public:
    BinaryTree()
        :_root(NULL)
    {}

    BinaryTree(const T* a, size_t size, const T& invalid)
    {
        size_t index = 0;
        _root = _CreatBinaryTree( a, size, index, invalid);
    }

    BinaryTree(const BinaryTree<T>& t)
    {
        _root = _Copy(t._root);
    }

    //BinaryTree<T>& operator=(const BinaryTree<T>& t)
    //{
    //    if (this != &t)
    //    {
    //        Node* tmp = _Copy(t._root);
    //        _Destory(_root);
    //        _root = tmp;
    //    }
    //    return *this;
    //}

    BinaryTree<T>& operator=(BinaryTree<T> t)
    {
        swap(this->_root, t._root);
        return *this;
    }

    ~BinaryTree()
    {
        _Destory(_root);
        _root = NULL;
    }

    void PreOrder()
    {
        _PreOrder(_root);
        cout << endl;
    }

    void InOrder()
    {
        _InOrder(_root);
        cout << endl;
    }

    void PostOrder()
    {
        _PostOrder(_root);
        cout << endl;
    }

    size_t Size()
    {
        return _Size(_root);
    }

    size_t Depth()
    {
        return _Depth(_root);
    }

    size_t LeafSize()
    {
        size_t size = 0;
        _LeafSize(_root,size);
        return size;
    }

    size_t GetKLevel(int k)
    {
        size_t kSize = 0;
        size_t level = 1;
        _GetKLevel(_root,k,level,kSize);

        return kSize;
    }

    void PreOrder_NoR()
    {
        _PreOrder_NoR();
        cout << endl;
    }

    void InOrder_NoR()
    {
        _InOrder_NoR();
        cout << endl;
    }

    void PostOrder_NoR()
    {
        _PostOrder_NoR();
        cout << endl;
    }


protected:
    void _Destory(Node* root)
    {
        if (root == NULL)
        {
            return;
        }

        _Destory(root->_left);
        _Destory(root->_right);

        delete root;
    }

    Node* _Copy(Node* root)
    {
        if (root == NULL)
        {
            return NULL;
        }

        Node* newRoot = new Node(root->_data);
        newRoot->_left = _Copy(root->_left);
        newRoot->_right = _Copy(root->_right);

        return newRoot;
    }

    Node* _CreatBinaryTree(const T* a, size_t size,
                            size_t& index, const T& invalid)
    {
        Node* root = NULL;
        while (index < size && a[index] != invalid)
        {
            root = new Node(a[index]); // new并初始化
            root->_left = _CreatBinaryTree( a, size, ++index, invalid);
            root->_right = _CreatBinaryTree( a, size, ++index, invalid);
        }
        return root;
    }

    void _PreOrder(Node* root)
    {
        if (root == NULL)
            return;

        cout << root->_data << " ";
        _PreOrder(root->_left);
        _PreOrder(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 << " ";
    }

    size_t _Size(Node* root)
    {
        if (root == NULL)
            return 0;
        return _Size(root->_left) + _Size(root->_right) + 1;
    }

    size_t _Depth(Node* root)
    {
        if (root == NULL)
            return 0;

        int leftDepth = _Depth(root->_left);
        int rightDepth = _Depth(root->_right);

        return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
    }

    void _LeafSize(Node* root, size_t& size) // size需傳引用，以保證每次在上次的調(diào)用加值，否則size結(jié)果為0
    {
        if (root == NULL)
            return;
        if (root->_left == NULL && root->_right == NULL)
        {
            ++size;
            return;
        }
        _LeafSize(root->_left,size);
        _LeafSize(root->_right, size);
    }

    void _GetKLevel(Node* root, int k,
        size_t level, size_t& kSize)
    {
        if (root == NULL)
        {
            return;
        }

        if (level == k)
        {
            ++kSize;
            return;
        }

        _GetKLevel(root->_left, k, level + 1, kSize);
        _GetKLevel(root->_right, k, level + 1, kSize);
    }

    void _PreOrder_NoR() // 前序遍歷->非遞歸
    {
        stack<Node*> s;
        if (_root)
        {
            s.push(_root);
        }

        while (!s.empty())
        {
            Node* top = s.top();
            cout << top->_data << " ";

            s.pop();

            if (top->_right) // 先壓右樹，后壓左樹
            {
                s.push(top->_right); 
            }
            if (top->_left)
            {
                s.push(top->_left);
            }
        }
    }

    void _InOrder_NoR() 
    {
        Node* cur = _root;
        stack<Node*> s;

        while (cur || !s.empty())
        {
            while (cur)
            {
                // 1.壓一棵樹的左路節(jié)點，直到最左節(jié)點
                s.push(cur);
                cur = cur->_left;
            }
             // 2.棧不為空，出棧訪問，并移向右樹，判斷右樹是否為空，后循環(huán)此操作，直至棧為空
            if (!s.empty())
            {
                Node* top = s.top();
                s.pop();
                cout << top->_data << " ";
                cur = top->_right;
            }
        }
    }

    void _PostOrder_NoR()
    {
        Node* pre = NULL;
        Node* cur = _root;
        stack<Node*> s;
        while (cur || !s.empty())
        {
            while (cur)
            {
                s.push(cur);
                cur = cur->_left;
            }

            Node* top = s.top();
            if (top->_right == NULL || top->_right == pre)
            {
                cout << top->_data << " ";
                s.pop();
                pre = top;
            }
            else
            {
                cur = top->_right;
            }
        }
    }

protected:
    Node* _root;
};

Test.cpp 文件：

#include <iostream>
using namespace std;

#include "BinaryTree.h"

int main()
{
    int a[10] = { 1, 2, 3, '#', '#', 4, '#', '#', 5, 6 };
    BinaryTree<int> t( a, 10, '#');

    cout << t.Depth() << endl;
    cout << t.Size() << endl;

    t.PreOrder();
    t.InOrder();
    t.PostOrder();

    cout<< t.GetKLevel(1) << endl;
    cout << t.GetKLevel(3) << endl;

    cout << t.LeafSize() << endl;

    t.PreOrder_NoR();
    t.InOrder_NoR();
    t.PostOrder_NoR();

    system("pause");
    return 0;
}

若有紕漏，歡迎指正。

創(chuàng)新互聯(lián)www.cdcxhl.cn，專業(yè)提供香港、美國云服務(wù)器，動態(tài)BGP最優(yōu)骨干路由自動選擇，持續(xù)穩(wěn)定高效的網(wǎng)絡(luò)助力業(yè)務(wù)部署。公司持有工信部辦法的idc、isp許可證， 機房獨有T級流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確進行流量調(diào)度，確保服務(wù)器高可用性。佳節(jié)活動現(xiàn)已開啟，新人活動云服務(wù)器買多久送多久。

網(wǎng)站欄目：【數(shù)據(jù)結(jié)構(gòu)】二叉樹-創(chuàng)新互聯(lián)
網(wǎng)頁鏈接：http://aaarwkj.com/article32/dgohpc.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供移動網(wǎng)站建設(shè)、品牌網(wǎng)站設(shè)計、企業(yè)網(wǎng)站制作、虛擬主機、網(wǎng)站營銷、電子商務(wù)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)

微信小程序開發(fā)
91精品一区二区三区91人妻| 亚洲精品日韩国产3区| 蜜桃视频在线中文字幕| 91免费人成网站在线观看| 亚洲一区精品中文字幕| 极品性感尤物少妇粉嫩逼| 在线看日本十八禁网站| 蜜桃精品一区二区三区在线观看 | 欧美电影剧情av在线| 99热只有这里才有精品| 国产免费成人午夜免费视频| 久章草在线免费视频播放| 国产高清亚洲一区亚洲二区| 91精品大片免费在线观看| 成年人性生活一级视品| 狠狠综合久久av一区二区大宝| 日本加勒比中文在线观看| 久久热在线视频精品视频| 亚洲精品国产av成人| 久久这里只有精品蜜桃| 蜜桃网站视频免费观看| 在线观看永久免费黄色| 天堂av新版在线观看| 国产三级三级三级精品8ⅰ区| 国产91高清在线观看| 夫妻性生活在线视频一级片| 日韩精品在线观看你懂的| 欧美另类不卡在线观看| 久草亚洲一区二区三区av| 激情欧美精品桃桃激情| 日本不卡一二区不久精品免费| 中文字幕人妻秘书社长| 欧美一区二区专区在线| 人妻少妇久久中文字幕久久| 欧美亚洲精品在线观看| 久久日韩人妻中文字幕| 夜福利国产视频大屁股| 国产欧美日韩一区二区三区四区| 国产自产一区二区三区精品| 女同三人按摩高潮喷出| 国产精品一区二区av在线|