• <noscript id="e0iig"><kbd id="e0iig"></kbd></noscript>
  • <td id="e0iig"></td>
  • <option id="e0iig"></option>
  • <noscript id="e0iig"><source id="e0iig"></source></noscript>
  • (C++)二叉樹的線索化 / 線索二叉樹

    • 好久不見,朋友們!雖然我知道沒人看我的博客,但我還是想叨逼叨一下。啊,好久沒編程了(其實也就一周沒編),但你們知道,程序員一天不編程那能叫程序員么???雖然我不是程序員哈哈哈哈哈,但還是要有基本素養嘛。

    • 繼續寫二叉樹,給自己立一個flag,就是這幾天要寫完之前沒做完的幾道題,和二叉樹紅黑樹各種樹之類的~~雖然有這個flag,但我還是很實誠地遵從自己的內心,買了一張明天的電影票,等我回來告訴你們好不好看!好看的話,我就!!寫影評!!但!!不給看!!

    • 好的,我是屯了很多電影和書沒看啦,但我屯的代碼好像更多。之前又比較犯懶,就只碼代碼,沒寫博客,但我發現哦,寫博客真的很有助于增進對代碼的分析能力,所以我又開始以我神經兮兮的風格開始寫博客啦!

    • 今天我要寫的博客是關于二叉樹的線索化,當然,也可以理解為是線索二叉樹。

    線索二叉樹

    什么是線索二叉樹

    • 對于n個結點的二叉樹,在二叉鏈表的數據存儲結構中,總是有(2n - (n-1) = n+1)個空鏈域。
    • 我們利用這些空鏈域存放某種遍歷次序下該結點前驅結點和后續結點的指針,并將這些指針稱為線索,稱該二叉樹為線索二叉樹,稱給二叉樹加上線索的過程為二叉樹的線索化

    為什么要進行二叉樹的線索化

    • 我們都知道,二叉樹是一種非線性的數據結構,遍歷二叉樹時,我們常使用遞歸或者用棧輔助從而實現非遞歸的遍歷。
    • 顯然,當我們使用二叉樹作為存儲結構時, 取到一個結點,我們只能獲取到結點的左右孩子,而無法獲取到結點的前驅和后繼。
    • 那么,為了進一步增強遍歷的實用性,我們利用二叉樹結構中的空指針來存放各結點的前驅和后繼信息。

    線索二叉樹的基本設計

    這里寫圖片描述

    • 如果_left為空,則存放指向中序遍歷序列中該結點的前驅結點。
    • 如果_right為空,則存放指向中序遍歷序列中該結點的后繼結點。
    • 如果_leftTag為Link,則代表著結點存放的是其左孩子;存放的是Thread則代表著其存放的是其前驅結點。
    • 如果_rightTag為Link,則代表著結點存放的是其右孩子;存放的是Thread則代表著其存放的是其后繼結點。

    線索二叉樹的實現

    中序遍歷模型

    這里寫圖片描述

    代碼實現

    #include<iostream>
    
    using namespace std;
    
    //線索化標志Tag
    enum PointerTag {THREAD, LINK};
    
    //結點結構
    template<class T>
    struct BinaryTreeNodeThd
    {
        T _data;
        BinaryTreeNodeThd<T>* _left;
        BinaryTreeNodeThd<T>* _right;
        PointerTag _leftTag;
        PointerTag _rightTag;
    
        //構造函數
        BinaryTreeNodeThd(const T& x)
            :_data(x)
            , _left(NULL)
            , _right(NULL)
            , _leftTag(LINK)
            , _rightTag(LINK)
        {}
    };
    
    //基類迭代器
    template <class T>
    struct __BinaryTreeIterator
    {
        typedef BinaryTreeNodeThd<T> Node;
        typedef __BinaryTreeIterator<T> Self;
    
        Node* _node;
    
        __BinaryTreeIterator(Node* node)
            :_node(node)
        {}
    
        T& operator*()
        {
            return _node->_data;
        }
    
        T* operator->()
        {
            return &(_node->_data);
        }
    
        bool operator ==(const Self& s)
        {
            return (_node == s._node);
        }
    
        bool operator != (const Self& s)
        {
            return (_node != s._node);
        }
    
        virtual Self& operator++() = 0;//純虛函數
    };
    
    
    //中序遍歷迭代器
    template<class T>
    struct __BinaryTreeInInterator :public __BinaryTreeIterator<T>
    {
        typedef BinaryTreeNodeThd<T> Node;
        typedef __BinaryTreeInInterator<T> Self;
    
        __BinaryTreeInInterator(Node* node)
            :__BinaryTreeIterator(node)
        {}
    
        Self& operator++()
        {
            if (_node->_rightTag == THREAD)
            {
                _node = _node->_right;
            }
            else
            {
                Node* sub = _node->_right;
                if (sub && sub->_leftTag == LINK)
                {
                    sub = sub->_left;
                }
                _node = sub;
            }
            return *this;
        }
    };
    
    
    //前序遍歷迭代器
    template<class T>
    struct __BinaryTreePrevInterator :public __BinaryTreeIterator<T>
    {
        typedef BinaryTreeNodeThd<T> Node;
        typedef __BinaryTreePrevInterator<T> Self;
    
        __BinaryTreePrevInterator(Node* node)
            :__BinaryTreeInterator(node)
        {}
    
        Self& operator++()
        {
            if (_node->_leftTag == LINK)
            {
                _node = _node->_left;
            }
            else
            {
                _node = _node->_right;
            }
            return *this;
        }
    
    };
    
    
    //二叉樹的線索化
    template <class T>
    struct BinaryTreeThd
    {
        typedef BinaryTreeNodeThd<T> Node;
        typedef __BinaryTreeInInterator<T> InInterator;
        typedef __BinaryTreePrevInterator<T> PrevInterator;
    
    public:
        BinaryTreeThd(T* a, size_t n, const T& invalid)
        {
            size_t index = 0;
            _root = _CreateTree(a, n, index, invalid);
        }
    
        PrevInterator PrevBegin()
        {
            return root;
        }
    
        PrevInterator PrevEnd()
        {
            return NULL;
        }
    
        InInterator InBegin()
        {
            Node* sub = _root;
            while (sub && sub->_leftTag == LINK)
            {
                sub = sub->_left;
            }
            return sub;
        }
    
        InInterator InEnd()
        {
            return NULL;
        }
    
        void InOrder()
        {
            _InOrder(_root);
            cout << endl;
        }
    
        void InOrderThreading()
        {
            Node* prev = NULL;
            _InOrderThreading(_root, prev);
        }
    
    protected:
        Node* _CreateTree(T* a, size_t n, size_t& index, const T& invalid)
        {
            Node* root = NULL;
            if (index < n && a[index] != invalid)
            {
                root = new Node(a[index]);
                root->_left = _CreateTree(a, n, ++index, invalid);
                root->_right = _CreateTree(a, n, ++index, invalid);
            }
            return root;
        }
    
        void _InOrder(Node* root)
        {
            if (root == NULL)
            {
                return;
            }
            _InOrder(root->_left);
            cout << root->_data << ' ';
            _InOrder(root->_right);
        }
    
        void _InOrderThreading(Node* root, Node*& prev)
        {
            if (root == NULL)
                return;
    
            _InOrderThreading(root->_left, prev);
    
            if (root->_left == NULL)
            {
                root->_left = prev;
                root->_leftTag = THREAD;
            }
    
            if (prev && prev->_right == NULL)
            {
                prev->_right = root;
                prev->_rightTag = THREAD;
            }
            prev = root;
    
            _InOrderThreading(root->_right, prev);
    
        }
    
    private:
        Node* _root;
    };
    

    測試用例

    void TestBinaryTreeThd()
    {
        int a1[] = {1, 2, 3, '#', '#', 4, '#' , '#', 5, 6};
        BinaryTreeThd<int> t1(a1, sizeof(a1)/sizeof(a1[0]), '#');
        t1.InOrder();
        t1.InOrderThreading();
    

    實現結果

    這里寫圖片描述

    References

    http://blog.csdn.net/u014492609/article/details/40477795
    http://blog.csdn.net/my_heart_/article/details/52086321

    版權聲明:本文為JS_Evey原創文章,遵循 CC 4.0 BY-SA 版權協議,轉載請附上原文出處鏈接和本聲明。
    本文鏈接:https://blog.csdn.net/JS_Evey/article/details/78451209

    智能推薦

    【c++】二叉樹的線索化

    什么是二叉樹的線索化?或者問什么是線索二叉樹? 按照某種遍歷方式對二叉樹進行遍歷,可以把二叉樹中所有結點排序為一個線性序列。在改序列中,除第一個結點外每個結點有且僅有一個直接前驅結點;除最后一個結點外每一個結點有且僅有一個直接后繼結點。這些指向直接前驅結點和指向直接后續結點的指針被稱為線索(Thread),加了線索的二叉樹稱為線索二叉樹。 以上是搜狗百科的一段文字,反正我是沒看太懂。簡單點,以我的...

    線索二叉樹去線索化

         今天想來這里分享一下自己的代碼。      在做數據結構的課程設計的時候,文檔上面有要求刪除結點以及左右子樹的功能。然而在之前的設計中,我已經將二叉樹遍歷設計成前序線索二叉樹遍歷的代碼了。所以,要想刪除節點必須利用線索二叉樹刪除結點。然而感覺工程量過大(其實是沒時間設計了),只能將線索二叉樹恢復成正常二叉樹,...

    線索化二叉樹以及遍歷線索化二叉樹

    線索化二叉樹以及遍歷線索化二叉樹 1.線索二叉樹基本介紹 n個結點的二叉鏈表中含有n+1 【公式 2n-(n-1)=n+1】 個空指針域。利用二叉鏈表中的空指針域,存放指向該結點在某種遍歷次序下的前驅和后繼結點的指針(這種附加的指針稱為"線索") 這種加上了線索的二叉鏈表稱為線索鏈表,相應的二叉樹稱為線索二叉樹(Threaded BinaryTree)。根據線索性質的不同,線索...

    線索化二叉樹以及遍歷線索化二叉樹

    問題的提出 線索化二叉樹的介紹 1) n個結點的二叉鏈表中含有n+1;公式2n-(n-1)=n+1個空指針域。利用二叉鏈表中的空指針域,存放指向該結點在某種遍歷次序下的前驅和后繼結點的指針(這種附加的指針稱為"線索")。 公式:因為一共有2n個指針,除了根節點,每個節點都會被指針引用。 2)這種加上了線索的二叉鏈表稱為線索鏈表,相應的二叉樹稱為線索二叉樹(Threaded Bi...

    hive 導出數據之一列多行,轉為一行多列

    需求:提取數據 說明:原數據是一列多行,需要轉化為一行多列 待查詢表為:temp_05 待查詢數據為: 待查詢數據如圖: 需要提取的數據表頭如下: 預定日期 昨日價格 前天價格 2018-02-01 2018-02-02 2018-02-03 2018-02-04 可用提數 SQL 數據如圖: 以下為嘗試過程 數據如圖: 數據如圖: 數據如圖: 數據如圖:...

    猜你喜歡

    asp.net做一個簡易的聊天室

    要求: 結果: 關鍵代碼: Default.aspx Default.aspx.cs Default2.aspx Default2.aspx.cs Default3.aspx Default3.aspx.cs Default4.aspx...

    動態SQL和多表關聯-筆記

    《動態SQL與多表關聯》筆記 學習目標 能夠使用動態SQL完成SQL拼接 能夠使用resultMap完成多表查詢 能夠使用一對一查詢 能夠使用一對多查詢 (注:多對多其實就是兩個一個多) 映射文件:為什么要resultMap 目標 定義結果映射 使用結果映射 回顧 在mybatis中有2種配置文件: 核心配置文件,如:sqlMapConfig.xml 實體類映射文件,如:UserMapper.xm...

    【OpenGL C++ UE4】獲取模型頂點及面索引數據,并優化存儲結構供UE4繪制

    目錄 一、功能需求 二、成果 三、環境配置 四、詳細步驟 4.1 Max制作三棱錐并處理 4.2 核心代碼 4.2.1 傳入結構體數據 4.2.2 頂點去重、更新索引 4.2.3 輸出本地CSV文件 4.3 UE4繪制 一、功能需求 想必你肯定會問我一個問題,UE4直接導入模型不好么? 哈哈,前提是在做畢設時,導師提供的只有頂點與面索引數據,沒有模型。 下文詳細介紹了畢設開發中的難點,涉...

    解決Pyinstaller打包numpy和pandas庫文件過大問題

    解決Pyinstaller壓縮numpy和pandas庫文件過大問題 文件包類型和網上的方法 Windows下docker的安裝 在docker下實現打包     今天是2021年的第一天,先祝各位小伙伴現年快樂哈。最近因為做了一個項目,需要打包文件,文件中包含了numpy和pandas庫,結果打包出來幾百行的代碼居然要900m,人都傻了,翻遍了全網找解決方...

    精品国产乱码久久久久久蜜桃不卡