数据结构与算法:二叉树算法

摘要：因此，根据题目给出的先序遍历和中序遍历，可以画出二叉树选参考数据结构与算法描述实现二叉树算法浅谈数据结构二叉树慕课网实现二叉树算法前端树控件腾讯软件开发面试题

内容衔接上一章 数据结构与算法:常见排序算法

什么是树

　　- 为什么使用树

二叉树

二叉查找树

红黑树

Ｂ、Ｂ＋树

堆

伸展树

可以点击链接感受下笔者用d3.js画的tree

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

树 是计算机科学中经常用到的一种数据结构。

树是一种非线性的数据结构，以分层的方式存储数据。

树被用来存储具有层级关系的数据，比如文件系统中的文件

数还被用来存储有序列表

选择树而不是那些基本的数据结构，是因为：

二叉树上进行查找特别快（而在链表上查找每次基本就是遍历，查找速度很慢）

二叉树添加或删除元素也很快（而对数组执行添加或删除操作则不是这样）

树的遍历是树的一种重要的运算。所谓遍历是指对树中所有结点的信息的访问，即依次对树中每个结点访问一次且仅访问一次。树的3种最重要的遍历方式分别称为前序遍历、中序遍历和后序遍历。以这3种方式遍历一棵树时，若按访问结点的先后次序将结点排列起来，就可分别得到树中所有结点的前序列表、中序列表和后序列表。相应的结点次序分别称为结点的前序、中序和后序。

这里我们将研究一种特殊的树：二叉树（二叉树，本质上，是对链表和数组的一个折中。）

如上图，树是由一组以边连接的节点组成。

二叉树是一种特殊的树，它的子节点个数不超过两个

通过将子节点的个数限定为2,可以写出高效的程序在树中插入、查找和删除数据。

根节点：二叉树中最高那个节点没有父节点。
叶子节点： 最低下一层没有孩子节点的节点
剩下的节点被成为中间节点

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);

我们看到中序遍历可以把二叉树的节点按照从小到大的顺序打印出来;
而前序遍历可以在我们已经拥有一颗二叉树的时候，高效的复制这颗二叉树。
通过其前序遍历去复制一颗二叉树比重新构造一颗二叉树要高效得多

前（先）序遍历：按照最优先顺序沿一定路径经过路径上所有的站。在二叉树中，先根后左再右。巧记：根左右。

红黑树：　处于平衡状态的特殊二叉查找树

红黑树(Red-Black Tree，简称R-B Tree)，它一种特殊的二叉查找树。 红黑树是特殊的二叉查找树，意味着它满足二叉查找树的特征：任意一个节点所包含的键值，大于等于左孩子的键值，小于等于右孩子的键值。 除了具备该特性之外，红黑树还包括许多额外的信息。

红黑树的每个节点上都有存储位表示节点的颜色，颜色是红(Red)或黑(Black)。 红黑树的特性: (1) 每个节点或者是黑色，或者是红色。 (2) 根节点是黑色。 (3) 每个叶子节点是黑色。 (4) 如果一个节点是红色的，则它的子节点必须是黑色的。 (5) 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。

关于它的特性，需要注意的是： 第一，特性(3)中的叶子节点，是只为空(NIL或null)的节点。 第二，特性(5)，确保没有一条路径会比其他路径长出俩倍。因而，红黑树是相对是接近平衡的二叉树。

要实现起来，需要包含的基本操作是添加、删除和旋转。在对红黑树进行添加或删除后，会用到旋转方法。旋转的目的是让树保持红黑树的特性。旋转包括两种：左旋 和 右旋。

红黑树的应用比较广泛，主要是用它来存储有序的数据，它的查找、插入和删除操作的时间复杂度是O(lgn)。

维基百科对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