91久久精品日日躁夜夜躁国产,超碰人人爱,在线成人小视频

先前說了樹的基本操作，我們采用的是二叉鏈表來保存樹形結構，當然二叉有二叉的困擾之處，比如我想找到當前結點的“前驅”和“后繼”，那么我們就必須要遍歷一下樹，然后才能定位到該“節點”的“前驅”和“后繼”，每次定位都是o（n），這不是我們想看到的，那么有什么辦法來解決呢？

（1）在節點域中增加二個指針域，分別保存“前驅”和“后繼”，那么就是四叉鏈表了，哈哈，還是有點浪費空間啊。

（2）看下面的這個二叉樹，我們知道每個結點有2個指針域，4個節點就有8個指針域，其實真正保存節點的指針

僅有3個，還有5個是空閑的，那么為什么我們不用那些空閑的指針域呢，達到資源的合理充分的利用。

算法系列15天速成第十二天樹操作【中】

一：線索二叉樹

1 概念

剛才所說的在空閑的指針域里面存放“前驅”和“后繼”就是所謂的線索。

<1> 左線索：在空閑的左指針域中存放該“結點”的“前驅”被認為是左線索。

<2> 右線索：在空閑的右指針域中存放該“結點“的”后繼“被認為是右線索。

當“二叉鏈表”被套上這種線索，就被認為是線索鏈表，當“二叉樹”被套上這種線索就被認為是線索二叉樹，當然線索根據

二叉樹的遍歷形式不同被分為“先序線索”，“中序線索”，“后序線索”。

2 結構圖

說了這么多，我們還是上圖說話，就拿下面的二叉樹，我們構建一個中序線索二叉樹，需要多動動腦子喲。

<1> 首先要找到“中序遍歷”中的首結點d，因為“d結點”是首節點，所以不存在“前驅”，左指針自然是空，

”d節點”的右指針存放的是“后繼”，那么根據“中序遍歷”的規則應該是b，所以d的右指針存放著b節點。

<2> 接著就是“b節點”，他的左指針不為空，所以就不管了，但是他的“右指針”空閑，根據規則“b結點“的右

指針存放的是"a結點“。

<3> 然后就是“a節點”，他已經被塞的滿滿的，所以就沒有“線索”可言了。

<4> 最后就是“c節點”，根據規則，他的“左指針”存放著就是“a節點“，”c節點“是最后一個節點，右指針自然就是空的，你懂的。

算法系列15天速成第十二天樹操作【中】

3 基本操作

常用的操作一般有“創建線索二叉樹”，”查找后繼節點“，”查找前驅節點“，”遍歷線索二叉樹“，下面的操作我們就以”中序遍歷“來創建中序線索二叉樹。

<1> 線索二叉樹結構

從“結構圖”中可以看到，現在結點的指針域中要么是”子節點（subtree）“或者是”線索（thread）“，此時就要設立標志位來表示指針域存放的是哪一種。

復制代碼代碼如下:

#region 節點標識(用于判斷孩子是節點還是線索)
    /// <summary>
/// 節點標識(用于判斷孩子是節點還是線索)
/// </summary>
    public enum nodeflag
    {
        subtree = 1,
        thread = 2
    }
    #endregion

    #region 線索二叉樹的結構
    /// <summary>
/// 線索二叉樹的結構
/// </summary>
/// <typeparam name="t"></typeparam>
    public class threadtree<t>
    {
        public t data;
        public threadtree<t> left;
        public threadtree<t> right;
        public nodeflag leftflag;
        public nodeflag rightflag;
    }
    #endregion

<2> 創建線索二叉樹

剛才也說了如何構建中序線索二叉樹，在代碼實現中，我們需要定義一個節點來保存當前節點的前驅，我練習的時候迫不得已，只能使用兩個

ref來實現地址操作，達到一個tree能夠讓兩個變量來操作。

復制代碼代碼如下:

#region 中序遍歷構建線索二叉樹
        /// <summary>
/// 中序遍歷構建線索二叉樹
/// </summary>
/// <typeparam name="t"></typeparam>
/// <param name="tree"></param>
        public void bintreethreadingcreate_ldr<t>(ref threadtree<t> tree, ref threadtree<t> prevnode)
        {
            if (tree == null)
                return;

//先左子樹遍歷，尋找起始點
bintreethreadingcreate_ldr(ref tree.left, ref prevnode);

//如果left為空，則說明該節點可以放“線索”
tree.leftflag = (tree.left == null) ? nodeflag.thread : nodeflag.subtree;

//如果right為空，則說明該節點可以放“線索”
tree.rightflag = (tree.right == null) ? nodeflag.thread : nodeflag.subtree;

            if (prevnode != null)
            {
                if (tree.leftflag == nodeflag.thread)
                    tree.left = prevnode;
                if (prevnode.rightflag == nodeflag.thread)
                    prevnode.right = tree;
            }

//保存前驅節點
prevnode = tree;

            bintreethreadingcreate_ldr(ref tree.right, ref prevnode);
        }
        #endregion

<3> 查找后繼結點

現在大家都知道，后繼結點都是保存在“結點“的右指針域中，那么就存在”兩種情況“。

《1》拿“b節點“來說，他沒有右孩子，則肯定存放著線索（thread),所以我們直接o（1）的返回他的線索即可。

《2》拿“a節點”來說，他有右孩子，即右指針域存放的是subtree，悲哀啊，如何才能得到“a節點“的后繼呢？其實也很簡單，

根據”中序“的定義，”a節點“的后繼必定是”a節點“的右子樹往左鏈找的第一個沒有左孩子的節點（只可意會，不可言傳，嘻嘻）。

復制代碼代碼如下:

#region 查找指定節點的后繼
        /// <summary>
/// 查找指定節點的后繼
/// </summary>
/// <typeparam name="t"></typeparam>
/// <param name="tree"></param>
        public threadtree<t> bintreethreadnext_ldr<t>(threadtree<t> tree)
        {
            if (tree == null)
                return null;

            //如果查找節點的標志域中是thread，則直接獲取
            if (tree.rightflag == nodeflag.thread)
                return tree.right;
            else
            {
                //根據中序遍歷的規則是尋找右子樹中中序遍歷的第一個節點
                var rightnode = tree.right;

                //如果該節點是subtree就需要循環遍歷
                while (rightnode.leftflag == nodeflag.subtree)
                {
                    rightnode = rightnode.left;
                }
                return rightnode;
            }
        }
        #endregion

<4> 查找前驅節點

這個跟（3)的操作很類似，同樣也具有兩個情況。

《1》拿“c結點”來說，他沒有“左子樹”，則說明“c節點”的左指針為thread，此時，我們只要返回左指針域即可得到前驅結點。

《2》拿"a節點“來說，他有”左子樹“，則說明”a節點“的左指針為subtree，那么怎么找的到”a節點“的前驅呢？同樣啊，根據

”中序遍歷“的性質，我們可以得知在”a節點“的左子樹中往”右鏈“中找到第一個沒有”右孩子“的節點。

復制代碼代碼如下:

#region 查找指定節點的前驅
        /// <summary>
/// 查找指定節點的前驅
/// </summary>
/// <typeparam name="t"></typeparam>
/// <param name="tree"></param>
/// <returns></returns>
        public threadtree<t> bintreethreadprev_ldr<t>(threadtree<t> tree)
        {
            if (tree == null)
                return null;

            //如果標志域中存放的是線索，那么可以直接找出來
            if (tree.leftflag == nodeflag.thread)
                return tree.left;
            else
            {
                //根據”中序“的規則可知，如果不為thread，則要找出左子樹的最后節點
//也就是左子樹中最后輸出的元素
                var leftnode = tree.left;

while (leftnode.rightflag == nodeflag.subtree)
leftnode = leftnode.right;

                return leftnode;
            }
        }
        #endregion

<5> 遍歷線索二叉樹

因為我們構建線索的時候采用的是“中序”，那么我們遍歷同樣采用“中序”，大家是否看到了“線索”的好處，此時我們找某個節點的時間復雜度變為了

o(1) ~0(n)的時間段，比不是線索的時候查找“前驅"和“后繼”效率要高很多。

復制代碼代碼如下:

#region 遍歷線索二叉樹
        /// <summary>
/// 遍歷線索二叉樹
/// </summary>
/// <typeparam name="t"></typeparam>
/// <param name="tree"></param>
        public void bintreethread_ldr<t>(threadtree<t> tree)
        {
            if (tree == null)
                return;

while (tree.leftflag == nodeflag.subtree)
tree = tree.left;

            do
            {
                console.write(tree.data + "\t");

tree = bintreethreadnext_ldr(tree);

} while (tree != null);

}
#endregion

最后上一下總的運行代碼

復制代碼代碼如下:

using system;
using system.collections.generic;
using system.linq;
using system.text;

namespace threadchaintree
{
    class program
    {
        static void main(string[] args)
        {
            threadtreemanager manager = new threadtreemanager();

//生成根節點
threadtree<string> tree = createroot();

//生成節點
addnode(tree);

threadtree<string> prevnode = null;

//構建線索二叉樹
manager.bintreethreadingcreate_ldr(ref tree, ref prevnode);

            console.writeline("\n線索二叉樹的遍歷結果為：\n");
            //中序遍歷線索二叉樹
            manager.bintreethread_ldr(tree);
        }

        #region 生成根節點
        /// <summary>
/// 生成根節點
/// </summary>
/// <returns></returns>
        static threadtree<string> createroot()
        {
            threadtree<string> tree = new threadtree<string>();

console.writeline("請輸入根節點，方便我們生成樹\n");

tree.data = console.readline();

console.writeline("根節點生成已經生成\n");

            return tree;
        }
        #endregion

        #region 插入節點操作
        /// <summary>
/// 插入節點操作
/// </summary>
/// <param name="tree"></param>
        static threadtree<string> addnode(threadtree<string> tree)
        {
            threadtreemanager mananger = new threadtreemanager();

            while (true)
            {
                threadtree<string> node = new threadtree<string>();

console.writeline("請輸入要插入節點的數據：\n");

node.data = console.readline();

console.writeline("請輸入要查找的父節點數據：\n");

var parentdata = console.readline();

                if (tree == null)
                {
                    console.writeline("未找到您輸入的父節點，請重新輸入。");
                    continue;
                }

console.writeline("請確定要插入到父節點的：1 左側，2 右側");

direction direction = (direction)enum.parse(typeof(direction), console.readline());

tree = mananger.bintreethreadaddnode(tree, node, parentdata, direction);

console.writeline("插入成功，是否繼續？ 1 繼續， 2 退出");

                if (int.parse(console.readline()) == 1)
                    continue;
                else
                    break;
            }

            return tree;
        }
        #endregion
    }

    #region 插入左節點或者右節點
    /// <summary>
/// 插入左節點或者右節點
/// </summary>
    public enum direction { left = 1, right = 2 }
    #endregion

    #region 線索二叉樹的基本操作
    /// <summary>
/// 線索二叉樹的基本操作
/// </summary>
    public class threadtreemanager
    {
        #region 將指定節點插入到二叉樹中
        /// <summary>
/// 將指定節點插入到二叉樹中
/// </summary>
/// <typeparam name="t"></typeparam>
/// <param name="tree"></param>
/// <param name="node"></param>
/// <param name="direction">插入做左是右</param>
/// <returns></returns>
        public threadtree<t> bintreethreadaddnode<t>(threadtree<t> tree, threadtree<t> node, t data, direction direction)
        {
            if (tree == null)
                return null;

            if (tree.data.equals(data))
            {
                switch (direction)
                {
                    case direction.left:
                        if (tree.left != null)
                            throw new exception("樹的左節點不為空，不能插入");
                        else
                            tree.left = node;

                        break;
                    case direction.right:
                        if (tree.right != null)
                            throw new exception("樹的右節點不為空，不能插入");
                        else
                            tree.right = node;

                        break;
                }
            }

bintreethreadaddnode(tree.left, node, data, direction);
bintreethreadaddnode(tree.right, node, data, direction);

            return tree;
        }
        #endregion

//先左子樹遍歷，尋找起始點
bintreethreadingcreate_ldr(ref tree.left, ref prevnode);

//如果left為空，則說明該節點可以放“線索”
tree.leftflag = (tree.left == null) ? nodeflag.thread : nodeflag.subtree;

//如果right為空，則說明該節點可以放“線索”
tree.rightflag = (tree.right == null) ? nodeflag.thread : nodeflag.subtree;

//保存前驅節點
prevnode = tree;

            bintreethreadingcreate_ldr(ref tree.right, ref prevnode);
        }
        #endregion