JavaScript篇（一）二叉樹的插入 (附:可視化)

一、二叉樹概念二叉樹（binary tree）是一顆樹，其中每個節點都不能有多於兩個的兒子。位元組一面，第一道就是二叉樹的插入，在這裡其實是對於一個二叉查找樹的插入。使二叉樹成為二叉查找樹的性質是，對於樹中的每個節點X，它的左子樹中所有項的值小於X中的項目，而它的右子樹所有的項的值大於X中的項。 ...

一、二叉樹概念

二叉樹（binary tree）是一顆樹，其中每個節點都不能有多於兩個的兒子。

位元組一面，第一道就是二叉樹的插入，在這裡其實是對於一個二叉查找樹的插入。

使二叉樹成為二叉查找樹的性質是，對於樹中的每個節點X，它的左子樹中所有項的值小於X中的項目，而它的右子樹所有的項的值大於X中的項。

如下圖，兩顆都是二叉樹，左邊的樹是查找樹，右邊的樹則不是。右邊的樹在其項為6的節點（該節點正好是根節點）的左子樹中，有一個節點的項是7。

接下來我們要實現二叉樹的插入：

eg: 對於[ 2, 5, 4, 1, 3, 6] =>

二、實現思路

　　1.實例化node節點

　　若根節點為空，便將newNode賦給root節點；

　　若根節點存在，則插入新節點。

　　2.插入左子樹或右子樹

　　1) 如果newNode小於node

　　　　1.如果node.left(左孩子)為空，newNode賦給node.left

　　　　2.否則再次比較newNode < node.left

　　2) 如果newNode大於node

　　　　1.如果node.right(右孩子)為空，newNode賦給node.right

　　　　2.否則再次比較newNode> node.right

三、代碼實現

 1 function BinaryTree(){
 2     // 定義節點
 3     var Node = function(key){    
 4         this.key = key;
 5         this.left = null;
 6         this.right = null;
 7     }
 8     // 初始化根節點
 9     var root = null;    
10     // 插入節點
11     this.insert = function(key){    
12         // 實例化node節點
13         var newNode = new Node(key);
14         // 根節點為空，便將newNode賦給root節點
15         if (root === null) {
16             root = newNode;
17         } else {
18         // 根節點存在，插入新節點  
19             insertNode(root, newNode);
20         };
21     }
22     // 插入節點(中序遍歷)
23     var insertNode = function(node, newNode){  
24         // node 當前節點
25         // newNode 新節點
26         // 若newNode小於node，則插入到node的左側
27         if(newNode.key < node.key){ 
28             // 若node的左孩子為空，則插入為node的左孩子
29             if(node.left === null){
30                 node.left = newNode;
31             } else {
32             // 若node的左孩子不為空，則繼續去和node的左孩子比較進行插入
33                 insertNode(node.left, newNode);
34             }
35         }else {    
36             if(node.right === null){
37                 node.right = newNode;
38             }else{
39                 insertNode(node.right, newNode);
40             }
41         }
42     }
43 }

var nodes = [2, 5, 4, 1, 3, 6]; 
var binaryTree = new BinaryTree(); // 將數組中的每個元素插入到二叉樹中 
nodes.forEach(function(key){ 
    binaryTree.insert(key); 
})

附:可視化二叉樹排序，更好去理解!(轉至:https://www.imooc.com/notepad/1fb575)

<!DOCTYPE html>    

<html>    

<title>二叉排序樹</title>    

    <head>    

        <meta http-equiv="Content-Type" content="text/html; charset=UTF-8" />    

    </head>    

    <body >    

        <canvas id="canvas" width="1366" height="768" ></canvas>

    </body>    

</html>    

    

<script type="text/javascript">

        //二叉演算法函數    

       function BinaryTree(){

        //node 節點函數

        var Node=function(key){

            this.key=key;

            this.left=null;

            this.right=null;

            this.x = 0;//圖形繪製坐標

            this.y = 0;//圖形繪製坐標

        };



        /**二叉樹可視圖形描述**/

        this.graphical = [];//圖形數組

        this.lrMove = 100;//左右偏移量

        this.udMove = 100;//上下偏移量

        /**==================**/



        //定義根節點

        var root=null;



        //插入節點 迴圈遞歸函數 左右分插

        this.insertNode=function(node,newNode){

            if(newNode.key < node.key){

                if(node.left===null){

                    var x = node.x;

                    var y = node.y;

                    newNode.x = (x -= this.udMove); 

                    newNode.y = (y += this.lrMove);

                    node.left=newNode;     

                }else{

                    this.insertNode(node.left,newNode);

                }

            }else{

                if(node.right===null){

                    var x = node.x;

                    var y = node.y;

                    newNode.x = (x += this.udMove); 

                    newNode.y = (y += this.lrMove);

                    node.right=newNode;

                }else{

                    this.insertNode(node.right,newNode);

                }

            }

        };



        //入口程式

        this.insert=function(key){

            var newNode= new Node(key);

            if(root===null){

                root=newNode;

                root.x = 500;

                root.y = 100;

                this.graphical.push(root);

            }else{

                this.insertNode(root,newNode);

            }

        };



        var inOrdertraverseNode = function(node,callback){

            if(node !== null){

                inOrdertraverseNode(node.left,callback);

                callback(node.key);

                inOrdertraverseNode(node.right,callback);

            }

        }



        this.inOrdertraverse = function(callback){

            inOrdertraverseNode(root,callback);

        }

    }



    var nodes=[8,3,10,1,6,14,4,15,12,13];

    var binaryTree=new BinaryTree;

    for(var i = 0 ; i < nodes.length ; i++){

         binaryTree.insert(nodes[i]);

    }



    var callback = function(key){

        console.log(key)

    }



    binaryTree.inOrdertraverse(callback);



    /*=====================================================開始繪製================================*/

    var canvas = document.getElementById("canvas");

    var context = canvas.getContext('2d');  //獲取對應的2D對象(畫筆)





    function draw(key,x,y){

        this.counter = 0;

        this.render = function(c){

            c.fillStyle = "hsl("+ this.counter +", 100%, 50%)";

            c.strokeStyle = '#fff'; //設置筆觸的顏色

            c.font = "bold 40px '字體','字體','微軟雅黑','宋體'"; //設置字體

            c.textBaseline = 'hanging'; //在繪製文本時使用的當前文本基線

            c.fillText(key ,x ,y); 

        }

        this.update = function(){

          this.counter += 5;

        }

    }



    var fontCavaseArr = [];



     function init() { 

        loop();//繪製文字        

        setInterval(run, 1000/30);

      }





    function run(x,y){

      context.fillStyle = "rgba(0,0,0,0.1)";

      context.fillRect(0,0,1366,768); //繪製 1366*768 像素的已填充矩形：

      for (i=0; i<fontCavaseArr.length; i++) {

        var particle = fontCavaseArr[i]; 

        particle.render(context); 

        particle.update(); 

      }

      gLine();//繪製線條

    }



    function loop(){

        font(binaryTree.graphical[0]);

    }



    function font(obj){

        if(obj.key != null && obj.key != undefined){

            var drawFont = new draw(obj.key,obj.x,obj.y);

            fontCavaseArr.push(drawFont);

        }

        if(obj.left != null && obj.left != undefined){

            var drawFont = new draw(obj.left.key,obj.left.x,obj.left.y);

            fontCavaseArr.push(drawFont);

            font(obj.left);

        }

        if(obj.right != null && obj.right != undefined){

            var drawFont = new draw(obj.right.key,obj.right.x,obj.right.y);

            fontCavaseArr.push(drawFont);

            font(obj.right);

        }

    }



    function gLine(){

        line(binaryTree.graphical[0]);

    }

    

    function line(obj){

        context.lineJoin="round";  

        context.lineCap="butt";  

        context.beginPath(); 

        if(obj.left != null && obj.left != undefined){

            context.moveTo(obj.x+20,obj.y+20); 

            context.lineTo(obj.left.x+20,obj.left.y+20);

            context.stroke();  

            context.closePath(); 

            line(obj.left);

        }

        if(obj.right != null && obj.right != undefined){

            context.moveTo(obj.x+20,obj.y+20); 

            context.lineTo(obj.right.x+20,obj.right.y+20);

            context.stroke();  

            context.closePath(); 

            line(obj.right);

        }

    }

    

    init();



</script>

View Code