摘要：因此，根據(jù)題目給出的先序遍歷和中序遍歷，可以畫出二叉樹選參考數(shù)據(jù)結(jié)構(gòu)與算法描述實現(xiàn)二叉樹算法淺談數(shù)據(jù)結(jié)構(gòu)二叉樹慕課網(wǎng)實現(xiàn)二叉樹算法前端樹控件騰訊軟件開發(fā)面試題

內(nèi)容銜接上一章 數(shù)據(jù)結(jié)構(gòu)與算法:常見排序算法

什么是樹

　　- 為什么使用樹

二叉樹

二叉查找樹

紅黑樹

Ｂ、Ｂ＋樹

堆

伸展樹

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

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

樹 是計算機科學(xué)中經(jīng)常用到的一種數(shù)據(jù)結(jié)構(gòu)。

樹是一種非線性的數(shù)據(jù)結(jié)構(gòu)，以分層的方式存儲數(shù)據(jù)。

樹被用來存儲具有層級關(guān)系的數(shù)據(jù)，比如文件系統(tǒng)中的文件

數(shù)還被用來存儲有序列表

選擇樹而不是那些基本的數(shù)據(jù)結(jié)構(gòu)，是因為：

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

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

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

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

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

二叉樹是一種特殊的樹，它的子節(jié)點個數(shù)不超過兩個

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

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

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

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

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

所有結(jié)點存儲一個關(guān)鍵字；

非葉子結(jié)點的左指針指向小于其關(guān)鍵字的子樹，右指針指向大于其關(guān)鍵字的子樹；

有三種遍歷BST的方式：

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

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

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

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

function BinaryTree() {
            //二叉查找樹由節(jié)點組成，所以我們先定義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;//設(shè)置根節(jié)點
              
            //insert()方法，用來向樹中加入新節(jié)點
            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() {
            //二叉查找樹由節(jié)點組成，所以我們先定義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;//設(shè)置根節(jié)點
              
            //insert()方法，用來向樹中加入新節(jié)點
            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);

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

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

紅黑樹：　處于平衡狀態(tài)的特殊二叉查找樹

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

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

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

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

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

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

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

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

解答：

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

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

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

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

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

選　４

《數(shù)據(jù)結(jié)構(gòu)與算法Javascript描述》
Javascript實現(xiàn)二叉樹算法
淺談數(shù)據(jù)結(jié)構(gòu)-二叉樹
慕課網(wǎng) Javascript實現(xiàn)二叉樹算法
前端 樹控件
2016 騰訊軟件開發(fā)面試題
https://www.cnblogs.com/tangx...
https://jovial-snyder-8b8319....
Tree traversal