數據結構與算法:二叉樹算法

Little_XM 發布于2019-08-22 11:09 / 1710人閱讀

摘要：因此，根據題目給出的先序遍歷和中序遍歷，可以畫出二叉樹選參考數據結構與算法描述實現二叉樹算法淺談數據結構二叉樹慕課網實現二叉樹算法前端樹控件騰訊軟件開發面試題

內容銜接上一章數據結構與算法:常見排序算法

內容提要

什么是樹

　　- 為什么使用樹

二叉樹

二叉查找樹

紅黑樹

Ｂ、Ｂ＋樹

堆

伸展樹

樹

可以點擊鏈接感受下筆者用d3.js畫的tree

https://codepen.io/AlexZ33/pe...

樹是計算機科學中經常用到的一種數據結構。

樹是一種非線性的數據結構，以分層的方式存儲數據。

樹被用來存儲具有層級關系的數據，比如文件系統中的文件

數還被用來存儲有序列表

選擇樹而不是那些基本的數據結構，是因為：

二叉樹上進行查找特別快（而在鏈表上查找每次基本就是遍歷，查找速度很慢）

二叉樹添加或刪除元素也很快（而對數組執行添加或刪除操作則不是這樣）

樹的遍歷

樹的遍歷是樹的一種重要的運算。所謂遍歷是指對樹中所有結點的信息的訪問，即依次對樹中每個結點訪問一次且僅訪問一次。樹的3種最重要的遍歷方式分別稱為前序遍歷、中序遍歷和后序遍歷。以這3種方式遍歷一棵樹時，若按訪問結點的先后次序將結點排列起來，就可分別得到樹中所有結點的前序列表、中序列表和后序列表。相應的結點次序分別稱為結點的前序、中序和后序。

二叉樹

這里我們將研究一種特殊的樹：二叉樹（二叉樹，本質上，是對鏈表和數組的一個折中。）

如上圖，樹是由一組以邊連接的節點組成。

二叉樹是一種特殊的樹，它的子節點個數不超過兩個

通過將子節點的個數限定為2,可以寫出高效的程序在樹中插入、查找和刪除數據。

根節點：二叉樹中最高那個節點沒有父節點。
葉子節點：最低下一層沒有孩子節點的節點
剩下的節點被成為中間節點

二叉查找樹（排序二叉樹）Binary Search Tree

BST（Binary Search Tree）目的是為了提高查找的性能，其查找在平均和最壞的情況下都是logn級別，接近二分查找。

如上圖，相對較小的值保存在左節點中，較大的值保存在右節點中。這樣能夠使查找效率變高。

所有非葉子結點至多擁有兩個兒子（Left和Right）；

所有結點存儲一個關鍵字；

非葉子結點的左指針指向小于其關鍵字的子樹，右指針指向大于其關鍵字的子樹；

有三種遍歷BST的方式：

中序遍歷（in-order）按照節點上的鍵值，以升序訪問BST上的所有節點

先序遍歷（pre-order）先訪問根節點，然后以同樣方式訪問左子樹和右子樹

后序遍歷 (post-order)先訪問葉子節點，從左子樹到右子樹，再到根節點

層次遍歷：只需按層次遍歷即可

function BinaryTree() {
            //二叉查找樹由節點組成，所以我們先定義Node

            //Node
            var Node = function(data,left,right) {
                this.data = data;
                this.left = left;
                this.right = right;
               // this.show = show;
            };
                        
            // var show = function() {
            //         return = this.data;
            // };
            
            var root = null;//設置根節點
              
            //insert()方法，用來向樹中加入新節點
            this.insert = function(data) {
                var newNode = new Node(data,null,null);
                if(root ===null){
                    root = newNode;
                }
                else {
                    insertNode(root,newNode);    
                }
            };

            var insertNode = function(node,newNode) {
                     if(newNode.data < node.data){
                        if(node.left === null){
                          node.left = newNode;
                        }else{
                          insertNode(node.left,newNode);
                        }
                     }else{
                       if(node.right === null){
                         node.right = newNode;
                       }else{
                         insertNode(node.right,newNode);
                       }
                     }
                
            };

            
            

        }


        var nodes = [8,3,10,1,6,14,4,7,13];
        var binaryTree = new BinaryTree();
        nodes.forEach(function(data) {
            binaryTree.insert(data);
        });
     
     //中序遍歷

     //先序遍歷

     //后序遍歷

中序遍歷

function BinaryTree() {
            //二叉查找樹由節點組成，所以我們先定義Node

            //Node
            var Node = function(data,left,right) {
                this.data = data;
                this.left = left;
                this.right = right;
               // this.show = show;
            };
                        
            // var show = function() {
            //         return = this.data;
            // };
            
            var root = null;//設置根節點
              
            //insert()方法，用來向樹中加入新節點
            this.insert = function(data) {
                var newNode = new Node(data,null,null);
                if(root ===null){
                    root = newNode;
                }
                else {
                    insertNode(root,newNode);    
                }
            };

            this.inOrderTraverse = function(callback) {
                inOrderTraverseNode(root,callback);
            }

            var insertNode = function(node,newNode) {
                     if(newNode.data < node.data){
                        if(node.left === null){
                          node.left = newNode;
                        }else{
                          insertNode(node.left,newNode);
                        }
                     }else{
                       if(node.right === null){
                         node.right = newNode;
                       }else{
                         insertNode(node.right,newNode);
                       }
                     }
                
            };

            var inOrderTraverseNode = function(node,callback) {
                if (node!==null) {
                    inOrderTraverseNode(node.left,callback);
                    callback(node.data);
                    inOrderTraverseNode(node.right,callback);
                }
            }

            
            

        }


        var nodes = [8,3,10,1,6,14,4,7,13];
        var binaryTree = new BinaryTree();
        nodes.forEach(function(data) {
            binaryTree.insert(data);
        });
     
     //中序遍歷
      var callback = function(data) {
          console.log(data);
      }
      binaryTree.inOrderTraverse(callback);

前序遍歷(pre-order)

我們看到中序遍歷可以把二叉樹的節點按照從小到大的順序打印出來;
而前序遍歷可以在我們已經擁有一顆二叉樹的時候，高效的復制這顆二叉樹。
通過其前序遍歷去復制一顆二叉樹比重新構造一顆二叉樹要高效得多

前（先）序遍歷：按照最優先順序沿一定路徑經過路徑上所有的站。在二叉樹中，先根后左再右。巧記：根左右。

后序遍歷 紅黑樹

紅黑樹：　處于平衡狀態的特殊二叉查找樹

紅黑樹(Red-Black Tree，簡稱R-B Tree)，它一種特殊的二叉查找樹。紅黑樹是特殊的二叉查找樹，意味著它滿足二叉查找樹的特征：任意一個節點所包含的鍵值，大于等于左孩子的鍵值，小于等于右孩子的鍵值。除了具備該特性之外，紅黑樹還包括許多額外的信息。

紅黑樹的每個節點上都有存儲位表示節點的顏色，顏色是紅(Red)或黑(Black)。紅黑樹的特性: (1) 每個節點或者是黑色，或者是紅色。 (2) 根節點是黑色。 (3) 每個葉子節點是黑色。 (4) 如果一個節點是紅色的，則它的子節點必須是黑色的。 (5) 從一個節點到該節點的子孫節點的所有路徑上包含相同數目的黑節點。

關于它的特性，需要注意的是：第一，特性(3)中的葉子節點，是只為空(NIL或null)的節點。第二，特性(5)，確保沒有一條路徑會比其他路徑長出倆倍。因而，紅黑樹是相對是接近平衡的二叉樹。

要實現起來，需要包含的基本操作是添加、刪除和旋轉。在對紅黑樹進行添加或刪除后，會用到旋轉方法。旋轉的目的是讓樹保持紅黑樹的特性。旋轉包括兩種：左旋和右旋。

紅黑樹的應用比較廣泛，主要是用它來存儲有序的數據，它的查找、插入和刪除操作的時間復雜度是O(lgn)。

B樹、B+樹

維基百科對B樹的定義為“在計算機科學中，B樹（B-tree）是一種樹狀數據結構，它能夠存儲數據、對其進行排序并允許以O(log n)的時間復雜度運行進行查找、順序讀取、插入和刪除的數據結構。B樹，概括來說是一個節點可以擁有多于2個子節點的二叉查找樹。與自平衡二叉查找樹不同，B-樹為系統最優化大塊數據的讀和寫操作。B-tree算法減少定位記錄時所經歷的中間過程，從而加快存取速度。普遍運用在數據庫和文件系統。

堆

高級數據(樹、堆、圖)應該平時多積累，好好理解，比如理解了堆是什么樣的數據結構，在面試中遇見的「查找最大的 K 個數」這類算法問題，就會迎刃而解。

伸展樹 常見面試題

1、已知一顆二叉樹，如果先序遍歷的節點順序是：ＡＤＣＥＦＧＨＢ, 中序遍歷是：CDFEGHAB,則后序遍歷結果是()
A. CFHGEBDA
B. CDFEGHBA
C. FGHCDEBA
D. CFHGEDBA

解答：

對于二叉樹的遍歷方式一般分為三種先序、中序、后序三種方式：

先序遍歷（根左右）
若二叉樹為空，則不進行任何操作：否則
1、訪問根結點。
2、先序方式遍歷左子樹。
3、先序遍歷右子樹。

中序遍歷（左根右）
若二叉樹為空，則不進行任何操作：否則
1、中序遍歷左子樹。
2、訪問根結點。
3、中序遍歷右子樹。

后序遍歷（左右根）
若二叉樹為空，則不進行任何操作：否則
1、后序遍歷左子樹。
2、后序遍歷右子樹。
3、放問根結點。

因此，根據題目給出的先序遍歷和中序遍歷，可以畫出二叉樹：　

選　４

參考

《數據結構與算法Javascript描述》
Javascript實現二叉樹算法
淺談數據結構-二叉樹
慕課網 Javascript實現二叉樹算法
前端 樹控件
2016 騰訊軟件開發面試題
https://www.cnblogs.com/tangx...
https://jovial-snyder-8b8319....
Tree traversal

云服務器 GPU云服務器二叉樹算法最優二叉樹算法圖二叉樹的存儲結構算法與數據結構

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/91890.html

二叉樹的實現

摘要：概念二叉樹是另一種樹型結構，它的特點是每個結點至多只有兩棵子樹即二叉樹中不存在度大于的結點，并且，二叉樹的子樹有左右之分其次序不能任意顛倒。查找最大值查找最小值思路傳入二叉樹，尋找左子樹，直到找到不存在左子樹的節點。概念二叉樹（Binary Tree）是另一種樹型結構，它的特點是每個結點至多只有兩棵子樹（即二叉樹中不存在度大于 2 的結點），并且，二叉樹的子樹有左右之分（其次序不能...

shengguo 2019-08-22 18:12 評論0 收藏0
數據結構與算法——二叉樹（上）

摘要：什么是樹前面說到的幾種數據結構都是線性的，例如鏈表棧隊列等，今天就來學習一種非線性的數據結構樹。在上圖中的幾種二叉樹中，有兩個是比較特殊的，分別是滿二叉樹和完全二叉樹。除了使用數組存儲二叉樹外，最常用的便是使用鏈表法來儲存二叉樹了。 1. 什么是樹？前面說到的幾種數據結構都是線性的，例如鏈表、棧、隊列等，今天就來學習一種非線性的數據結構——樹。先來看看幾種樹的結構： showImg(...

xeblog 2019-08-16 16:13 評論0 收藏0
Java數據結構與算法——二叉樹及操作(包括二叉樹遍歷)

摘要：本篇主要介紹二叉樹的概念二叉樹的表示二叉樹的操作三種遍歷方式實現求二叉樹的子樹求節點的父節點二叉樹高度，可能是考試中的，也可能是面試中的。通常二叉樹的遍歷根據根節點的遍歷次序分為先根遍歷中根遍歷后根遍歷。聲明：碼字不易，轉載請注明出處，歡迎文章下方討論交流。前言：Java數據結構與算法專題會不定時更新，歡迎各位讀者監督。本篇主要介紹二叉樹的概念、二叉樹的表示、二叉樹的操作（三種遍歷...

muddyway 2019-08-16 11:15 評論0 收藏0
Javascript 數據結構與算法——二叉樹

摘要：一個節點可以有多個子節點二叉樹二叉樹是一種特殊的樹，子節點數不超過個。以某種特定的順序訪問樹中所有的節點稱為樹的遍歷樹的層數稱為樹的深度一個父節點的兩個子節點分別稱為左節點和右節點二叉查找樹又稱二叉排序樹是一種特殊的二叉樹。原文地址：http://www.brandhuang.com/article/1564967352592 1、樹一棵樹最上面的節點：根結點一個節點下面連接多個...

shengguo 2019-08-26 10:33 評論0 收藏0