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

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

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

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

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

二叉樹(shù)是一種特殊的樹(shù)，它的子節(jié)點(diǎn)個(gè)數(shù)不超過(guò)兩個(gè)

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

根節(jié)點(diǎn)：二叉樹(shù)中最高那個(gè)節(jié)點(diǎn)沒(méi)有父節(jié)點(diǎn)。
葉子節(jié)點(diǎn)： 最低下一層沒(méi)有孩子節(jié)點(diǎn)的節(jié)點(diǎn)
剩下的節(jié)點(diǎn)被成為中間節(jié)點(diǎn)

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

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

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

所有結(jié)點(diǎn)存儲(chǔ)一個(gè)關(guān)鍵字；

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

有三種遍歷BST的方式：

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

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

后序遍歷 (post-order)先訪問(wèn)葉子節(jié)點(diǎn)，從左子樹(shù)到右子樹(shù)，再到根節(jié)點(diǎn)

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

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

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

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

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

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

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

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

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

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

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

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

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

解答：

對(duì)于二叉樹(shù)的遍歷方式一般分為三種先序、中序、后序三種方式：

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

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

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

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

選?。?/p> 參考

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