<ruby id="bdb3f"></ruby>

    <p id="bdb3f"><cite id="bdb3f"></cite></p>

      <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
        <p id="bdb3f"><cite id="bdb3f"></cite></p>

          <pre id="bdb3f"></pre>
          <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

          <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
          <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

          <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                <ruby id="bdb3f"></ruby>

                合規國際互聯網加速 OSASE為企業客戶提供高速穩定SD-WAN國際加速解決方案。 廣告
                [TOC] ## 概述 二叉查找樹,又叫二叉排序樹,二叉搜索樹,是一種有特定規則的二叉樹,定義如下: 1. 它是一棵二叉樹,或者是空樹。 2. 左子樹所有節點的值都小于它的根節點,右子樹所有節點的值都大于它的根節點。 3. 左右子樹也是一棵二叉查找樹。 二叉查找樹可能退化為鏈表,也可能是一棵非常平衡的二叉樹,查找,添加,刪除元素的時間復雜度取決于樹的高度`h`。 1. 當二叉樹是滿的時,樹的高度是最小的,此時樹節點數量`n`和高度`h`的關系為:`h = log(n)`。 2. 當二叉樹是一個鏈表時,此時樹節點數量`n`和高度`h`的關系為:`h = n`。 二叉查找樹的效率來源其二分查找的特征,時間復雜度在于二叉樹的高度,因此查找,添加和刪除的時間復雜度范圍為`log(n)~n`。 為了提高二叉查找樹查找的速度,樹的高度要盡可能的小。AVL樹和紅黑樹都是相對平衡的二叉查找樹,因為特殊的旋轉平衡操作,樹的高度被大大壓低。它們查找效率較高,添加,刪除,查找操作的平均時間復雜度都為`log(n)`,經常在各種程序中被使用。 二叉查找樹是后面要學習的高級數據結構AVL樹,紅黑樹的基礎。 ## 實例 <details> <summary>main.go</summary> ``` package main import "fmt" // 二叉查找樹 type BinarySearchTree struct { Root *BinarySearchTreeNode // 樹根節點 } // 二叉查找樹節點 type BinarySearchTreeNode struct { Value int64 // 值 Times int64 // 值出現的次數 Left *BinarySearchTreeNode // 左子樹 Right *BinarySearchTreeNode // 右字樹 } // 初始化一個二叉查找樹 func NewBinarySearchTree() *BinarySearchTree { return new(BinarySearchTree) } // 添加元素 func (tree *BinarySearchTree) Add(value int64) { // 如果沒有樹根,證明是棵空樹,添加樹根后返回 if tree.Root == nil { tree.Root = &BinarySearchTreeNode{Value: value} return } // 將值添加進去 tree.Root.Add(value) } func (node *BinarySearchTreeNode) Add(value int64) { if value < node.Value { // 如果插入的值比節點的值小,那么要插入到該節點的左子樹中 // 如果左子樹為空,直接添加 if node.Left == nil { node.Left = &BinarySearchTreeNode{Value: value} } else { // 否則遞歸 node.Left.Add(value) } } else if value > node.Value { // 如果插入的值比節點的值大,那么要插入到該節點的右子樹中 // 如果右子樹為空,直接添加 if node.Right == nil { node.Right = &BinarySearchTreeNode{Value: value} } else { // 否則遞歸 node.Right.Add(value) } } else { // 值相同,不需要添加,值出現的次數加1即可 node.Times = node.Times + 1 } } // 找出最小值的節點 func (tree *BinarySearchTree) FindMinValue() *BinarySearchTreeNode { if tree.Root == nil { // 如果是空樹,返回空 return nil } return tree.Root.FindMinValue() } func (node *BinarySearchTreeNode) FindMinValue() *BinarySearchTreeNode { // 左子樹為空,表面已經是最左的節點了,該值就是最小值 if node.Left == nil { return node } // 一直左子樹遞歸 return node.Left.FindMinValue() } // 找出最大值的節點 func (tree *BinarySearchTree) FindMaxValue() *BinarySearchTreeNode { if tree.Root == nil { // 如果是空樹,返回空 return nil } return tree.Root.FindMaxValue() } func (node *BinarySearchTreeNode) FindMaxValue() *BinarySearchTreeNode { // 右子樹為空,表面已經是最右的節點了,該值就是最大值 if node.Right == nil { return node } // 一直右子樹遞歸 return node.Right.FindMaxValue() } // 查找節點 func (tree *BinarySearchTree) Find(value int64) *BinarySearchTreeNode { if tree.Root == nil { // 如果是空樹,返回空 return nil } return tree.Root.Find(value) } func (node *BinarySearchTreeNode) Find(value int64) *BinarySearchTreeNode { if value == node.Value { // 如果該節點剛剛等于該值,那么返回該節點 return node } else if value < node.Value { // 如果查找的值小于節點值,從節點的左子樹開始找 if node.Left == nil { // 左子樹為空,表示找不到該值了,返回nil return nil } return node.Left.Find(value) } else { // 如果查找的值大于節點值,從節點的右子樹開始找 if node.Right == nil { // 右子樹為空,表示找不到該值了,返回nil return nil } return node.Right.Find(value) } } // 查找指定節點的父親 func (tree *BinarySearchTree) FindParent(value int64) *BinarySearchTreeNode { if tree.Root == nil { // 如果是空樹,返回空 return nil } // 如果根節點等于該值,根節點其沒有父節點,返回nil if tree.Root.Value == value { return nil } return tree.Root.FindParent(value) } func (node *BinarySearchTreeNode) FindParent(value int64) *BinarySearchTreeNode { // 外層沒有值相等的判定,因為在內層已經判定完畢后返回父親節點。 if value < node.Value { // 如果查找的值小于節點值,從節點的左子樹開始找 leftTree := node.Left if leftTree == nil { // 左子樹為空,表示找不到該值了,返回nil return nil } // 左子樹的根節點的值剛好等于該值,那么父親就是現在的node,返回 if leftTree.Value == value { return node } else { return leftTree.FindParent(value) } } else { // 如果查找的值大于節點值,從節點的右子樹開始找 rightTree := node.Right if rightTree == nil { // 右子樹為空,表示找不到該值了,返回nil return nil } // 右子樹的根節點的值剛好等于該值,那么父親就是現在的node,返回 if rightTree.Value == value { return node } else { return rightTree.FindParent(value) } } } // 刪除指定的元素 func (tree *BinarySearchTree) Delete(value int64) { if tree.Root == nil { // 如果是空樹,直接返回 return } // 查找該值是否存在 node := tree.Root.Find(value) if node == nil { // 不存在該值,直接返回 return } // 查找該值的父親節點 parent := tree.Root.FindParent(value) // 第一種情況,刪除的是根節點,且根節點沒有兒子 if parent == nil && node.Left == nil && node.Right == nil { // 置空后直接返回 tree.Root = nil return } else if node.Left == nil && node.Right == nil { // 第二種情況,刪除的節點有父親節點,但沒有子樹 // 如果刪除的是節點是父親的左兒子,直接將該值刪除即可 if parent.Left != nil && value == parent.Left.Value { parent.Left = nil } else { // 刪除的原來是父親的右兒子,直接將該值刪除即可 parent.Right = nil } return } else if node.Left != nil && node.Right != nil { // 第三種情況,刪除的節點下有兩個子樹,因為右子樹的值都比左子樹大,那么用右子樹中的最小元素來替換刪除的節點。 // 右子樹的最小元素,只要一直往右子樹的左邊一直找一直找就可以找到,替換后二叉查找樹的性質又滿足了。 // 找右子樹中最小的值,一直往右子樹的左邊找 minNode := node.Right for minNode.Left != nil { minNode = minNode.Left } // 把最小的節點刪掉 tree.Delete(minNode.Value) // 最小值的節點替換被刪除節點 node.Value = minNode.Value node.Times = minNode.Times } else { // 第四種情況,只有一個子樹,那么該子樹直接替換被刪除的節點即可 // 父親為空,表示刪除的是根節點,替換樹根 if parent == nil { if node.Left != nil { tree.Root = node.Left } else { tree.Root = node.Right } return } // 左子樹不為空 if node.Left != nil { // 如果刪除的是節點是父親的左兒子,讓刪除的節點的左子樹接班 if parent.Left != nil && value == parent.Left.Value { parent.Left = node.Left } else { parent.Right = node.Left } } else { // 如果刪除的是節點是父親的左兒子,讓刪除的節點的右子樹接班 if parent.Left != nil && value == parent.Left.Value { parent.Left = node.Right } else { parent.Right = node.Right } } } } // 中序遍歷 func (tree *BinarySearchTree) MidOrder() { tree.Root.MidOrder() } func (node *BinarySearchTreeNode) MidOrder() { if node == nil { return } // 先打印左子樹 node.Left.MidOrder() // 按照次數打印根節點 for i := 0; i <= int(node.Times); i++ { fmt.Println(node.Value) } // 打印右子樹 node.Right.MidOrder() } func main() { tree := NewBinarySearchTree() tree.Add(5) tree.Add(1) tree.Add(2) tree.Add(3) tree.Add(4) tree.Add(6) tree.Add(7) tree.Add(8) tree.Delete(2) tree.MidOrder() /** 1 3 4 5 6 7 8 */ } ``` </details> <br/>
                  <ruby id="bdb3f"></ruby>

                  <p id="bdb3f"><cite id="bdb3f"></cite></p>

                    <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
                      <p id="bdb3f"><cite id="bdb3f"></cite></p>

                        <pre id="bdb3f"></pre>
                        <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

                        <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
                        <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

                        <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                              <ruby id="bdb3f"></ruby>

                              哎呀哎呀视频在线观看