• <noscript id="e0iig"><kbd id="e0iig"></kbd></noscript>
  • <td id="e0iig"></td>
  • <option id="e0iig"></option>
  • <noscript id="e0iig"><source id="e0iig"></source></noscript>
  • 二叉排序樹(BinSortTree)

    二叉排序樹介紹

    二叉排序樹,又稱為二叉查找樹。它或者是一棵空樹,或者是具有下列性質的二叉樹。
    若它的左子樹不為空,則左子樹上所有的結點的值均小于根結構的值;
    若它的右子樹不為空,則右字數上所有結點的值均大于它的根結點的值;
    它的左右子樹也分別為二叉排序樹。
    1,排序方便
    2,方便查找
    3,方便插入和刪除

    二叉排序樹最終實現:所有的左子樹的值都小于父節點的值,所有的右子樹的值都大于父節點的值


    二叉排序樹實現

    二叉數:
    這里寫圖片描述
    遍歷:
    這里寫圖片描述

    【刪除】分為四種情況:
    這里寫圖片描述
    1. 刪除的結點,左右孩子都為空
    2. 刪除的結點,左孩子不為空,右孩子為空
    3. 刪除的結點,左孩子為空,右孩子不為空
    4. 刪除的結點,左右孩子都不為空

    更新:先刪除再更新,要保持二叉排序樹始終是排好序的!


    代碼實現:

    using System;
    using System.Text;
    
    namespace cchoop
    {
        class Program
        {
            public static void Main()
            {
                BinSortTree tree = new BinSortTree();
                int[] arr = { 62, 58, 88, 47, 73, 99, 35, 51, 93, 37 };
                for (int i = 0; i < arr.Length; i++)
                {
                    tree.Add(arr[i]);
                }
    
                Console.Write("中序遍歷:");
                tree.MidTraversal();
                Console.Write("\n前序遍歷:");
                tree.PreTraversal();
                Console.Write("\n后序遍歷:");
                tree.AfterTraversal();
                Console.WriteLine("\n");
    
                //查找
                Console.WriteLine("查找50:" + tree.Find(50));
                Console.WriteLine("查找58:" + tree.Find(58));
                Console.WriteLine();
    
                //更新
                Console.WriteLine("更新108 To 8888:" + tree.Update(108, 8888));
                Console.WriteLine("更新58 To 8888:" + tree.Update(58, 8888));
                Console.Write("中序遍歷:");
                tree.MidTraversal();
                Console.WriteLine("\n");
    
                //刪除
                Console.WriteLine("刪除58:" + tree.Delete(58));
                Console.WriteLine("刪除88:" + tree.Delete(88));
                Console.Write("中序遍歷:");
                tree.MidTraversal();
                Console.WriteLine("\n");
    
            }
        }
    
        /// <summary>
        /// 二叉排序樹-鏈式存儲
        /// </summary>
        class BinSortTree
        {
            private BinSortNode root;
    
            //添加
            public void Add(int item)
            {
                BinSortNode node = new BinSortNode(item);
    
                //根結點為空
                if (root == null)
                {
                    root = node;
                    return;
                }
    
                //根節點不為空
                BinSortNode tempNode = root;
                while (true)
                {
                    if (node.Data < tempNode.Data)  //放在左邊
                    {
                        if (tempNode.LeftChild == null)
                        {
                            node.Parent = tempNode;
                            tempNode.LeftChild = node;
                            break;
                        }
                        else
                        {
                            tempNode = tempNode.LeftChild;
                        }
                    }
                    else  //放在右邊
                    {
                        if (tempNode.RightChild == null)
                        {
                            node.Parent = tempNode;
                            tempNode.RightChild = node;
                            break;
                        }
                        else
                        {
                            tempNode = tempNode.RightChild;
                        }
                    }
                }
            }
    
            //刪除
            public bool Delete(int item)
            {
                bool flag = false;
    
                if (root == null)
                {
                    return false;
                }
    
                BinSortNode tempNode = root;
                while (true)
                {
                    if (tempNode == null)
                    {
                        break;
                    }
                    if (tempNode.Data == item)
                    {
                        Delete(tempNode);
                        flag = true;
                        break;
                    }
                    else if (tempNode.Data > item)
                    {
                        tempNode = tempNode.LeftChild;
                    }
                    else
                    {
                        tempNode = tempNode.RightChild;
                    }
                }
    
                return flag;
            }
    
            private void Delete(BinSortNode node)
            {
                //四種情況:1.刪除的結點,左右孩子都為空
                //2.刪除的結點,左孩子不為空,右孩子為空
                //3.刪除的結點,左孩子為空,右孩子不為空
                //4.刪除的結點,左右孩子都不為空
                if (node.LeftChild == null && node.RightChild == null)
                {
                    if (node == root)   //頭結點
                    {
                        root = null;
                    }
                    else
                    {
                        if (node.Parent.LeftChild == node)
                        {
                            node.Parent.LeftChild = null;
                        }
                        else if (node.Parent.RightChild == node)
                        {
                            node.Parent.RightChild = null;
                        }
                    }
                    return;
                }
    
                if (node.LeftChild != null && node.RightChild == null)
                {
                    if (node == root)  //頭結點
                    {
                        root = node.LeftChild;
                    }
                    else
                    {
                        if (node.Parent.LeftChild == node)
                        {
                            node.Parent.LeftChild = node.LeftChild;
                        }
                        else if (node.Parent.RightChild == node)
                        {
                            node.Parent.RightChild = node.LeftChild;
                        }
                        node.LeftChild.Parent = node.Parent;
                    }
    
                    return;
                }
    
                if (node.LeftChild == null && node.RightChild != null)
                {
                    if (node == root)  //頭結點
                    {
                        root = node.RightChild;
                    }
                    else
                    {
                        if (node.Parent.LeftChild == node)
                        {
                            node.Parent.LeftChild = node.RightChild;
                        }
                        else if (node.Parent.RightChild == node)
                        {
                            node.Parent.RightChild = node.RightChild;
                        }
                        node.RightChild.Parent = node.Parent;
                    }
    
                    return;
                }
    
    
                //遞歸刪除
                if (node.LeftChild != null && node.RightChild != null)
                {
                    BinSortNode tempNode = node.RightChild;
                    while (tempNode.LeftChild != null)
                    {
                        tempNode = tempNode.LeftChild;
                    }
                    node.Data = tempNode.Data;
                    this.Delete(tempNode);
                }
            }
    
            //更新結點
            public bool Update(int oldValue, int newValue)
            {
                bool flag = false;
    
                if (root == null)
                {
                    return false;
                }
    
                BinSortNode tempNode = root;
                while (true)
                {
                    if (tempNode == null)
                    {
                        break;
                    }
                    if (tempNode.Data == oldValue)
                    {
                        //如果這樣更新將會破壞“排序”這個特點,所以更新,應該先刪除再添加,這棵樹仍然是二叉排序樹
                        //tempNode.Data = newValue;  
                        Delete(tempNode);
                        this.Add(newValue);
                        flag = true;
                        break;
                    }
                    else if (tempNode.Data > oldValue)
                    {
                        tempNode = tempNode.LeftChild;
                    }
                    else
                    {
                        tempNode = tempNode.RightChild;
                    }
                }
    
                return flag;
            }
    
            //查找
            public bool Find(int item)
            {
                return Find(item, root);
            }
            private bool Find(int item, BinSortNode node)
            {
                if (node == null)
                {
                    return false;
                }
    
                if (item == node.Data)
                {
                    return true;
                }
                else if (item > node.Data)
                {
                    return Find(item, node.RightChild);
                }
                else
                {
                    return Find(item, node.LeftChild);
                }
            }
    
            //前序遍歷
            public void PreTraversal()
            {
                PreTraversal(root);
            }
            private void PreTraversal(BinSortNode node)
            {
                if (node == null)
                {
                    return;
                }
                Console.Write(node.Data + " ");
                PreTraversal(node.LeftChild);
                PreTraversal(node.RightChild);
            }
    
            //中序遍歷
            public void MidTraversal()
            {
                MidTraversal(root);
            }
            private void MidTraversal(BinSortNode node)
            {
                if (node == null)
                {
                    return;
                }
                MidTraversal(node.LeftChild);
                Console.Write(node.Data + " ");
                MidTraversal(node.RightChild);
            }
    
            //后序遍歷
            public void AfterTraversal()
            {
                AfterTraversal(root);
            }
            private void AfterTraversal(BinSortNode node)
            {
                if (node == null)
                {
                    return;
                }
                AfterTraversal(node.LeftChild);
                AfterTraversal(node.RightChild);
                Console.Write(node.Data + " ");
            }
        }
    
        class BinSortNode
        {
            public BinSortNode Parent { get; set; }        //父節點
            public BinSortNode LeftChild { get; set; }      //左孩子
            public BinSortNode RightChild { get; set; }     //右孩子
            public int Data { get; set; }
    
            public BinSortNode(int data)
            {
                this.Data = data;
            }
        }
    }

    打印結果:
    這里寫圖片描述


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

    智能推薦

    二叉排序樹

    二叉排序樹 需求 給你一個數列(7,3,10,12,5,1,9),要求能夠高效的完成對數據的查詢和添加 解決方案分析 使用數組 數組未排序,優點:直接在數組尾添加,速度快。缺點:查找速度慢。 數組排序,優點:可以使用二分查找,查找速度快,缺點:為了保證數組有序,在添加新數據時,找到插入位置后,后面的數據需整體移動,速度慢。 使用鏈式存儲-鏈表 不管鏈表是否有序,查找速度都慢,添加數據速度比數組快,...

    二叉排序樹

    定義 二叉排序樹(Binary Sort Tree)又稱二叉查找樹、二叉搜索樹。 它或者是一棵空樹;或者是具有下列性質的二叉樹: (1)若左子樹不空,則左子樹上所有結點的值均小于它的根結點的值; (2)若右子樹不空,則右子樹上所有結點的值均大于它的根結點的值; (3)左、右子樹也分別為二叉排序樹; 對于線性結構: 1.若采用順序存儲,當數據是排好序的時候則刪除和插入困難,當數據不是排好序的時候,查...

    二叉排序樹

    二叉排序樹的性質: 二叉排序樹的插入操作: ③的左右孩子均為空,且由于此樹的性質,10置為③的右孩子,結束。 二叉排序樹的刪除: 解決思路: 1.直接刪除 2.如圖: 3.如圖: 中序遍歷為:17-18-19-20-28-29-30-32 LeetCode: 代碼實現: 實現結果:...

    二叉排序樹

    二叉排序樹 如果這樣簡單無序存儲,刪除固然簡單,若要查找則困難。 故而產生了二叉排序樹這樣的存儲方式。 二叉排序樹( Binary Sort Tree)又稱為二叉查找樹,它或者是一棵空樹,或者是具有下列性質的二叉樹: 1 若它的左子樹不為空,則左子樹上所有結點的值均小于它的根結構的值; 2 若它的右子樹不為空,則右子樹上所有結點的值均大于它的根結構的值; 3 即它的左、右子樹也分別為二叉排序樹(遞...

    二叉排序樹

    1.定義          二叉排序樹(BinarySortTree)定義如下: 二叉排序樹或者是一棵空樹,或者是具有下列性質的二叉樹: (1)若左子樹不空,則左子樹上所有結點的值均小于或等于它的根結點的值; (2)若右子樹不空,則右子樹上所有結點的值均大于或等于它的根結點的值; (3)左、右子樹也分別為二叉排序樹; 由定義可知...

    猜你喜歡

    二叉排序樹

    文章目錄 二叉排序樹 一、定義 二、 二叉排序樹性質: 三、二叉排序樹的操作 1、建立 2、查找 3、插入 4、刪除 四、代碼實現 1、二叉樹的建立 2、查找 3、插入 4、刪除 5、實驗數據 6、編譯環境 五、后記 二叉排序樹 一、定義 二叉排序樹,又叫二叉查找樹,如果非空,則具有以下性質: 若它的左子樹不空,則左子樹上所有節點的值均小于它的根節點的值; 若它的右子樹不空,則右子樹上所有節點的值...

    二叉排序樹

    二叉排序樹 簡介: 一棵空樹,或者是具有下列性質的二叉樹: (1)若左子樹不空,則左子樹上所有結點的值均小于它的根結點的值; (2)若右子樹不空,則右子樹上所有結點的值均大于它的根結點的值; (3)左、右子樹也分別為二叉排序樹; (4)沒有鍵值相等的結點。 [以上結果來自百度百科] 上圖就是一個簡單的二叉排序樹 插入(添加)節點 假設我們有一個數組int arr[] = { 5,8,2,7,4,1...

    二叉排序樹(Java)

    二叉排序樹(Java) 二叉排序樹(Binary Sort Tree),又稱二叉查找樹(Binary Search Tree),亦稱二叉搜索樹。 定義 一棵空樹,或者是具有下列性質的二叉樹稱為二叉排序樹: 若左子樹不空,則左子樹上所有結點的值均小于它的根結點的值; 若右子樹不空,則右子樹上所有結點的值均大于它的根結點的值; 左、右子樹也分別為二叉排序樹; 相關操作 舉個栗子 以結點權值集合為arr...

    二叉排序樹BST

    二叉排序樹(Binary Sort Tree),又稱二叉查找樹(Binary Search Tree),亦稱二叉搜索樹。 二叉排序樹的性質:左子樹上所有結點的值均小于或等于它的根結點的值;右子樹上所有結點的值均大于或等于它的根結點的值;左、右子樹也分別為二叉排序樹; 如圖是一個BST。 ----------------------------------------------- 有了這種性質,B...

    數組刪除其中某個對象的方法

    數組刪除其中的對象或元素,在前端是比較常見的需求。 我現在比較常用的方法如下: 這種方法只適合刪除具有唯一標識的對象。 有沒有想要脫單的小伙伴,加入我們的脫單星球,認識更多優秀的小哥哥小姐姐 特此聲明,星球是免費的,但是創建星球的時候說是必須輸入金額,所以只能先私聊,我再加你免費加入!...

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