百度搜索 二叉樹
頭兩個鏈接就是這倆

JavaScript二叉樹深入理解

javascript實現(xiàn)數(shù)據(jù)結(jié)構(gòu)： 樹和二叉樹,二叉樹的遍歷和基本操作

第二個博客的內(nèi)容應(yīng)該算第一個博客的基礎(chǔ)知識.
第一個比較好懂,第二個比較難,代碼量也多.

function Node (data,left,right) {
        this.data = data;
        this.left = left;
        this.right = right;
      }
      function BST () {
        this.root = null;
        this.insert = insert;
        this.find = find;
        this.remove = remove;
      }
      
      function insert (data) {
        var node = new Node(data,null,null);
        if(this.root == null) {
          this.root = node;
        } else {
          var current = this.root;
          while(true) {
            if(current.data > data) {
              if(current.left === null) {
                current.left = node;
                break;
              }
              current = current.left;
            }else {
              if(current.right === null) {
                current.right = node;
                break;
              }
              current = current.right;
            }
          }
        }
      }
      
      
      //二叉樹查節(jié)點
      function find (data) {
        var current = this.root;
        while (true){
            if(data == current.data) {
              return current;
            }
            current = data < current.data ? current.left : current.right;
            if(current === null) {
              return null;
            }
        }
      }
      
      //二叉樹刪除節(jié)點(只刪除葉子節(jié)點, 只有一個子節(jié)點的Node)
      
      function remove (data) {
        this.root = removeNode(this.root,data);
      }
      
      function removeNode (node, data) {
        if(node === null) {
          return null;
        }
        
        if(data === node.data) {
          if(node.left == null && node.right == null) {
            return null;
          }
          if(node.left === null) {
            return node.right;
          }
          if(node.right === null) {
            return node.left;
          }
          //這里有疑問, 如果node.left !== null && node.right !== right 這種情況怎么處理?
          //怪不得 上面說,只刪除只有一個子節(jié)點的Node
          //邏輯上來講, 可以把左子樹 return 給 右子樹, 
          //右子樹 return 給 刪除節(jié)點的 parent 是不是就可以保持結(jié)構(gòu)了? 
        }else if (data < node.data) {
          node.left = removeNode(node.left,data);
          return node;
        }else {
          node.right = removeNode(node.right,data);
          return node;
        }
      }
      抄寫第二遍時,感覺 remove() removeNode() 這個遞歸用得實在是太巧妙了, 
      當(dāng)初第一人到底是怎么想到這個結(jié)構(gòu)的?

      第一個感覺是,每次遞歸的執(zhí)行,不依賴遞歸返回的值?
      第二個感覺是,遞歸的過程當(dāng)中,他的返回值很自然的又形成了一個對象,
      一個二叉樹.怎么去的就怎么返回?

      也許我應(yīng)該問, 如果 remove 和 removeNode 非要寫在一個函數(shù),是不是會變得很復(fù)雜?
      他是怎么想到要分離開的?

      或者我應(yīng)該問,寫這個的核心邏輯出發(fā)點在哪里?
      需求是: 刪除節(jié)點,返回子節(jié)點,沒有就返回自身?
      因為我沒看懂,所以是我想復(fù)雜了嗎?
      


      var bst = new BST();
      bst.insert(5);
      bst.insert(8);
      bst.insert(9);
      bst.insert(1);
      bst.insert(3);
      console.log(bst);
      // 這個二叉樹,根節(jié)點取決于,頭一個放誰進(jìn)去.
      // 同樣的一組數(shù)據(jù),根據(jù)根節(jié)點放誰, 二叉樹的結(jié)構(gòu)也可能不同

在抄第二篇博客之前,發(fā)現(xiàn),
第二篇博客和第一篇博客的內(nèi)容完全不一樣,
應(yīng)該是第一篇的基礎(chǔ)內(nèi)容,

    樹狀結(jié)構(gòu)可以有很多種, 二叉樹是其中一種.

    二叉樹結(jié)構(gòu)的數(shù)據(jù)存儲有三種

  1.一種是數(shù)組.數(shù)組當(dāng)中的順序,反映二叉樹中的位置.
      具體這個順序和位置的關(guān)系,看博客,我也不是很清楚.
      (這個叫順序存儲結(jié)構(gòu))

  2.一種是二叉鏈表,
      每個節(jié)點有三個存儲結(jié)構(gòu)? 一個放left,一個放data,一個放right
      沒錯博客一,實際上就是二叉鏈表的形式.
      (這個叫鏈?zhǔn)酱鎯Y(jié)構(gòu))          

  3.一種是三叉鏈表,
      在left,data,right,之外放一個parent,用來指向parent.

下面是第二個博客的完整版代碼.

(function () {
        // 順序存儲結(jié)構(gòu)的遍歷
        var tree = [1,2,3,4,5,,6,,,7];
        // 先序遍歷
        console.log('preOrder');
        void function preOrderTraverse (x, visit) {
            visit(tree[x]);
            tree[2 * x + 1] && preOrderTraverse(2 * x + 1,visit);
            tree[2 * x + 2] && preOrderTraverse(2 * x + 2,visit);
        }(0, function (value) {
            console.log(value);
        })
         
         //中序遍歷
         console.log('inOrder:');
         void function inOrderTraverse (x, visit) {
          tree[2 * x + 1] && inOrderTraverse(2 * x + 1,visit);
          visit(tree[x]);
          tree[2 * x + 2] && inOrderTraverse(2 * x + 2,visit);
         }(0, function (value) {
          console.log(value);
        })
         
         console.log('postOrder:');
         void function postOrderTraverse (x, visit) {
          tree[2 * x + 1] && postOrderTraverse(2 * x + 1,visit);
          tree[2 * x + 2] && postOrderTraverse(2 * x + 2,visit);
          visit(tree[x]);
         }(0, function (value) {
          console.log(value);
        })
      })()
      
      
      var Stack = require('../Stack/stack');// 這就很尷尬了, 我不知道具體 Stack,Queue 怎么寫的
      var Queue = require('../Queue/Queue').Queue;
      
      
      function BinaryTree (data, leftChild, rightChild) {
        this.data = data || null;
        // 左右孩子節(jié)點
        this.leftChild = leftChild || null;
        this.rihgtChild  rightChild || null;
      }
      
      exports.BinaryTree = BinaryTree;// 這是為了導(dǎo)出?
      
      BinaryTree.prototype = {// 這個跟 博客一上的區(qū)別是,把函數(shù)定義在原型鏈上, 調(diào)用方式是一樣的.
        constructor : BinaryTree,
        // 判斷兩棵樹是否相似
        
        isSimilar : function (tree) {// tree 是另一個節(jié)點數(shù),也就是一個二叉樹對象.假定是跟 this相同的結(jié)構(gòu)就好理解
            return tree && 
               this.leftChild && isSimilar.call(this.leftChild,tree.leftChild) && this.rightChild &&
               isSimilar.call(this.rightChild,tree.rightChild);
               // 真是各種遞歸用得太巧妙了. 
               // 想到一個題目, 如何比較兩個 地址不同的 對象的內(nèi)容是否相同? 回頭想一下,
        },
        
        // 把一個數(shù)組,變成二叉樹鏈?zhǔn)酱鎯Y(jié)構(gòu)
        createBinaryTree: function (tree) {// 在一個函數(shù)里面遞歸另一個函數(shù)? 真是各種秀
          // 這尼瑪,這個tree 很明顯跟上面那個 tree 的數(shù)據(jù)類型應(yīng)該不一樣, 這個應(yīng)該是個 數(shù)組,順序存儲結(jié)構(gòu).
            void function preOrderTraverse (node, x, vist) {
                visit (node,tree[x]);
                tree[2 * x + 1] && preOrderTraverse(node.leftChild = new BinaryTree(), 2 * x + 1,visit);
                tree[2 * x + 2] && preOrderTraverse(node.rightChild = new BinaryTree(), 2 * x + 2,visit); 
            }(this,0,function (node,value) {
                node.data = value;
            })
        },
        //上面這段代碼,能讀懂, 但一時很難熟悉這種結(jié)構(gòu), 練習(xí)到后面,真的有可能隨手就能寫出這種結(jié)構(gòu)?
        
        //先序遍歷二叉樹的非遞歸算法
        
        preOrder_stack: function  (visit) {// 所以我們可以把visit 看成是一個回調(diào)函數(shù).
            var stack = new Stack();// 這就懵逼了,他沒具體寫 Stack
            //https://www.npmjs.com/package/stackjs 網(wǎng)上說這是個第三方 js
            stack.push(this);
            
            while (stack.top) {// stack.js 沒有top 屬性或方法啊
              var p;
              // 向左走到盡頭
              while ((p = stack.peek())){// stack.peek() 返回的應(yīng)該是 stack 中 最后一個push進(jìn)來的元素.
                p.data && visit(p.data);// 放進(jìn)一個stack,遍歷一個,
                stack.push(p.leftChild);
              }
              
              stack.pop();// 把上面循環(huán)之后的 最后一個 leftChild 清空.
              
              if (stack.top) {// top 依然不知道是什么東西 應(yīng)該是指 跟節(jié)點, 或者頭一個 push 進(jìn)去的節(jié)點.
                p = stack.pop();// 把 最后倒數(shù)第二個 leftChild刪除的同時拿出來, 因為一定會有 rightChild
                stack.push(p.rightChild);// 把rightChild拿出來.放進(jìn)stack里.
                //這個循環(huán)的出口在哪里? 出口就是, stack.pop() 把this也給 刪除的時候, stack.pop 就會false;
              }
            }
        },
        // 勉強(qiáng)看懂了, 真是天秀. 程序員世界里,沒有最裝逼的, 只有更裝逼的.
        preOrder_stack2: function (visit) {
            var stack = new Stack();
            var p = this;
            // 用了一個類似數(shù)組的 stack ,不止能遍歷一個 if 還能遍歷 else 
            // 也就是 能遍歷兩個方向?
            while (p || stack.top){
                if (p) {
                  stack.push(p);
                  p.data && visit(p.data);
                  p = p.leftChild;
                }else {
                  p = stack.pop();
                  p = p.rightChild;
                }
            }
        },
        // 能不能直接用兩個循環(huán)進(jìn)行遍歷? 不用 stack
        preOrder_stack3 : function (visit) {
            var p = this;
            while (p){
                p.data && visit(p.data);
                p = p.leftChild;
            }
            
            p = this.rightChild;
            while (p){
                p.data && visit(p.data);
                p = p.rightChild;
            }
            // 寫到一半我就知道這個不行了, 因為這樣只能遍歷最左一條鏈,和最右的一條鏈,中間的就遍歷不了.
            // 也就是必須要兩個循環(huán)嵌套..
        },
        
        //中序排序 非遞歸方法.
        inOrder_stack1: function (visit) {
            var stack = new Stack();
            stack.push(this);
            
            while (stack.top){
                var p;
                // 向左走到盡頭
                while ((p = stack.peek())){
                    stack.push(p.leftChild);
                }
                stack.pop();
                
                if(stack.top) {
                  p = stack.pop();
                  p.data && visit(p.data);
                  stack.push(p.rightChild);
                }
            }
        },
        inOrder_stack2: function (visit) {
            var stack = new Stack();
            var p = this;
            
            while (p || stack.top){
                if (p) {
                  stack.push(p);
                  p = p.leftChild;
                }else {
                  p = stack.pop();
                  p.data && visit(p.data);
                  p = p.rightChild;
                }
            }
        },
        // 為了區(qū)分兩次過棧的不同處理方式, 在堆棧中增加一個mark域,
        // mark = 0 表示剛剛訪問此節(jié)點, mark = 1 表示左子樹處理結(jié)束返回,
        // mark = 2 表示右子樹處理結(jié)束返回. 每次根據(jù)棧頂?shù)膍ark域決定做何動作
        
        postOrder_stack: function (visit) {
            var stack = new Stack();
            stack.push([this,0]);
            
            while (stack.top){
                var a = stack.pop();
                var node = a[0];
                
                switch (a[1]){
                    case 0:
                      stack.push([node,1]);// 修改 mark 域
                      if(node.leftChild) stack.push([node.leftChild,0]);
                        break;
                    case 1:
                      stack.push([node,2]);
                      if (node.rightChild) stack.push([node.rightChild,0]);
                      break;
                    case 2:
                       node.data && visit(node.data);
                      break;
                    default:
                        break;
                }
            }
        },
        // 還是很秀..消化困難.
        
        
        //遞歸版本 先序
        preOrderTraverse: function (visit) {
            visit(this.data);
            if (this.leftChild) preOrderTraverse.call(this.leftChild,visit);
            if (this.rightChild) preOrderTraverse.call(this.rightChild,visit);
        },
        // 遞歸版 中序
        inOrderTraverse : function (visit) {
          if (this.leftChild) inOrderTraverse.call(this.leftChild,visit);
          visit(this.data);
          if (this.rightChild) inOrderTraverse.call(this.rightChild,visit);
        },
        // 遞歸版 后序
        postOrderTraverse : function (visit) {
          if (this.leftChild) postOrderTraverse.call(this.leftChild,visit);
          if (this.rightChild) postOrderTraverse.call(this.rightChild,visit);
          visit(this.data);
        },
        // 原來遞歸真的比循環(huán)更簡潔嗎?
        
        levelOrderTraverse : function (visit) {
            var queue = new Queue();// 這個js也沒見過.
            // 這個似乎是 系統(tǒng)自帶的一個模塊之一. 系統(tǒng)組件之一.
            // 用來創(chuàng)建,先入先出的東西?
            //https://msdn.microsoft.com/zh-cn/library/system.collections.queue(v=vs.110).aspx
            // 好像還不是上面這個組件.
            // enQueue 就先簡單理解成push
            // queue 是隊列的意思..
            // 講解 https://blog.csdn.net/dengpei187/article/details/51880491
            // 隊列（Queue）是只允許在一端進(jìn)行插入工作，而在另一端進(jìn)行刪除操作的線性表岁经。隊列是一種先進(jìn)先出（First In First Out）的線性表汁蝶，簡稱FIFO着帽。允許插入的一端稱為隊尾揣钦，允許刪除的一端稱為隊頭获询。
            queue.enQueue(this);
            while (queue.rear){ // 最后一個元素的下一個元素,循環(huán),所以是第一個元素. 不深究,咱先把本篇抄錄一下再說.
                var p = queue.deQueue ();// 就相當(dāng)于 shift 方法?
                p.data && visit(p.data);
                p.leftChild && queue.enQueue(p.leftChild);
                p.rightChild && queue.enQueue(p.rightChild);
            }
        },
        
        //求先序序列為k的節(jié)點的值
        getPreSequence : function (k) {
            var count = 0;
            
            void function recurse (node) {
                if (node) {
                  if (++count === k) {
                    console.log('Value is: ' + node.data);
                  } else {
                    recurse(node.leftChild);
                    recurse(node.rightChild);
                  }
                }
            }(this);
        },
        
        // 求二叉樹中葉子節(jié)點的數(shù)目.
        
        countLeaves: function () {
            return function recurse (node) {
                if (!node) return 0;
                else if (!node.leftChild && !ndoe.rightChild) return 1;
                else return recurse(node.leftChild) + recurse(node.rightChild);
            }(this);
        },
        
        // 交換所有節(jié)點的左右子樹
        revoluteBinaryTree : function revoluteBinaryTree () {
            var temp = this.leftChild;
            this.leftChild = this.rightChild;
            this.rightChild = temp;
            
            if (this.leftChild) revoluteBinaryTree.call(this.leftChild);
            if (this.rightChild) revoluteBinaryTree.call(this.rightChild);
        },
        
        // 求二叉樹中以值為x的節(jié)點為根的子樹深度
        getSubDepth : function getSubDepth (x) {
            if (this.data === x) {
                console.log('subDepth: ' + this.getDepth());// 這個函數(shù)應(yīng)該在下面定義了.
            } else{
                if (this.leftChild) getSubDepth.call(this.leftChild, x);
                if (this.rightChild) getSubDepth.call(this.rightChild, x);
            }
        },
        // 返回二叉樹的深度.
        getDepth: function getDepth () {
            if (this === global) return 0;
            else {
              var m = getDepth.call(this.leftChild);
              var n = getDepth.call(this.rightChild);
              return (m > n ? m : n) + 1;// 我了個擦, 這個 + 1 是神來之筆嗎?
            }
        },
        // 刪除所有以元素x為根的子樹
        delSubX : function delSubX (x) {
            if (this.data === x) {
                this.leftChild = null;
                this.rightChild = null;
            } else {
              if (this.leftChild) delSubX.call(this.leftChild,x);// 原文應(yīng)該是忘了傳這個x了.
              if (this.rightChild) delSubX.call(this.rightChild,x);
            }
            // 這個版本和 博客一相比, 博客一里的需求是把后面的樹給連上, 這里是直接刪除整個樹.
        },
        // 非遞歸賦值二叉樹
        copyBinaryTree_stack : function () {
            // 用來存放本體節(jié)點的棧
            var stack1 = new Stack();
            // 用來存放新二叉樹節(jié)點的棧
            var stack2 = new Stack();
            stack1.push(this);
            var newTree = new BinaryTree();
            var q = newTree;
            stack2.push(newTree);
            var p;
            
            while (stack1.top){
                // 向左走到盡頭
                while ((p = stack1.peek())){
                    if (p.leftChild) q.leftChild = new BinaryTree();
                    q = q.leftChild;
                    stack1.push(p.leftChild);
                    stack2.push(q);
                }
                
                p = stack1.pop();
                q = stack2.pop();
                
                if (stack1.top) {
                  p = stack1.pop();
                  q = stack2.pop();
                  if (p.rightChild) q.rightChild = new BinaryTree();
                  q.data = p.data;
                  q = q.rightChild;
                  stack1.push(p.rightChild); // 向右一步
                  stack2.push(q);
                }
            }
            return newTree;
        },
        // 求二叉樹中節(jié)點p和q的最先祖先
        findNearAncient : function (pNode,qNode) {
            var pathP = [];
            var pathQ = [];
            findPath(this, pNode, pathP, 0);
            findPath(this, qNode, pathQ, 0);
            
            for (var i = 0; pathP[i] == pathQ[i] && pathP[i];i++);
            // 這又是什么秀操作? 明白了..
            return pathP[--i];
        },
        toString : function () {
            // 這是用來干嘛的?
        },
        // 求一顆二叉樹的繁茂度.
        // 繁茂度的定義：各層節(jié)點數(shù)的最大值與樹的高度的乘積 
        lunshDegree : function () {
            var countArr = [];
            var queue = new Queue();
            queue.enQueue({
              node: this,
              layer: 0// 用來表示在幾層.
            });
            // 利用層序遍歷來統(tǒng)計各層的節(jié)點數(shù)
            var r;
            while (queue.rear){
                r = queue.deQueue();// deQueue 就相當(dāng)于是  pop來著? 
                countArr[r.layer] = (countArr[r.layer] || 0) + 1;
                // 2.只要同一層級的再次出現(xiàn),就 +1;
                // 我剛開始錯誤的認(rèn)為 countArr[r.layer] = r.layer//導(dǎo)致我一直想不通,覺得max只能是countArr[last]
                if (r.node.leftChild) {
                  queue.enQueue({
                    node:r.node.leftChild,
                    layer:r.layer + 1
                  });
                }
                if (r.node.rightChild) {
                  queue.enQueue({
                    node: r.node.rightChild,
                    layer: r.layer + 1
                  });
                }
                // 1.先給在同一層級的節(jié)點進(jìn)行標(biāo)記,在幾層. 2在上面
            }
            //最后一個隊列元素所在層就是樹的高度
            var height = r.layer;
            for (var max = counArr[0],i = 1;countArr[i];i++) {
              //求層最大節(jié)點數(shù)
              if(countArr[i] > max) max = countArr[i];
            }
            return height * max;// 繁茂度的定義就是這個..
            //真是,從頭到尾一直秀..難道是我基礎(chǔ)太差了?
        },
        // 求深度等于樹的高度減一的最靠左的節(jié)點.
        printPath_maxDepthS1: function () {
            var maxh = this.getDepth();
            var path = [];
            
            if (maxh < 2) return false;//表示只有一個節(jié)點.
            
            find_h(this,1);
            
            function find_h (tree,h) {
                path[h] = tree;
                
                if (h == maxh - 1) {
                  var s = ' ';
                  for (var i = 1; path[i]; i++) s += path[i].data + (path[i + 1] ? '->' : '');
                  // 這什么鬼? 無論 if 還是 for 來個空格就可以把 {} 省略? 測試發(fā)現(xiàn)確實這樣.
                  // 看來我真實小白..
                  console.log(s);
                  return;
                }else {
                  if (tree.leftChild) find_h(tree.leftChild, h + 1);
                  if (tree.rightChild) find_h(tree.rightChild, h + 1);
                }
                path[h] = null;
                // 
            }
        },
        //求樹節(jié)點的子孫總數(shù)填入descNum域中, 并返回
        descNum : function () {
            return function recurse (node) {
                var d ;
                if (!node) return -1;
                else d = recurse(node.leftChild) + recurse(node.rightChild) + 2;
                
                node.desNum = d;
                return d;
            }(this);
        }
      }// 原型鏈上的結(jié)束
      
      //判斷二叉樹是否完全二叉樹
      BinaryTree.isFullBinaryTree = function (tree) {
        var queue = new Queue();
        var flag = 0;
        queue.enQueue(tree);
        
        while (queue.rear){// 如果隊列不為空, 依然return false,就表明leftChild和rightChild當(dāng)中有一個是null
          // 不對啊, 如果 queue.rear 指的是最后一個元素的下一個,那么這個循環(huán)不合理啊..
            var p = queue.deQueue();// 也就是 非完全二叉樹
            //
            if(!p) flag = 1;
            else if (flag) return false;
            // 為什么  這兩句 不直接改成 if (!p) return false;? 為什么要借助flag,再走一圈?
            // 因為完全二叉樹的最后一個元素
            else {
              queue.enQueue(p.leftChild);// 前面是不是要添加 if(p.leftChild)啊?
              queue.enQueue(p.rightChild);// p.rightChild == null時 應(yīng)該也會放進(jìn)隊列里.
            }
        }
        return true;
        // *** 這個函數(shù)的邏輯沒想通.
      }
      
      
      
      function findPath (tree, node,path,i) {// 這個為什么不放在原型鏈上?因為有可能處理的數(shù)據(jù)和this樹無關(guān)?
        var found = false;
        
        void function recurse (tree, i) {
            if (tree == node) {
                found = true;
                return;// 這個函數(shù)不需要返回? 因為整個過程我們遞歸用的都是同一個path,遞歸結(jié)束之后,path也就生成了.
                // 我現(xiàn)在覺得這篇代碼的價值根本不在什么二叉樹是什么玩意,
                // 這篇代碼的價值是,簡直就是各種花樣寫遞歸的教材嘛..
                // 當(dāng)然還有 for循環(huán).
            }
            
            path[i] = tree;
            if (tree.leftChild) recurse(tree.leftChild, i + 1);
            if (tree.rightChild && !found) recurse(tree.rightChild, i + 1);
            if (!found) path[i] = null;
        }(tree,i);
      }
      
      var global = Function ('return this;')();
      
      // 一下就是測試上面寫的函數(shù)
      void function test () {
        var tree = [1,2,3,4,5,,6,,,7];
        var test = new BinaryTree();
        test.createBinaryTree(tree);
        test.preOrderTraverse(function (value) {
            console.log('preOrder: ' + value);
        });
        test.inOrderTraverse(function (value) {
            console.log('inOrder: ' + value);
        });
        test.postOrderTraverse(function (value) {
            console.log('postOrder: ' + value);
        });
        
        test.preOrder_stack(function (data) {
            console.log('preOrderNonRecusive: ' + data);
        });
        test.preOrder_stack2(function (data) {
            console.log('preOrder_stack2: ' + data);
        });
        test.inOrder_stack1(function (value) {
            console.log('inOrder_stack1: ' + value);
        });
        test.inOrder_stack2(function (value) {
            console.log('inOrder_stack2: ' + value);
        });
        test.postOrder_stack(function (value) {
            console.log('postOrder_stack: ' + value);
        });
        test.getPreSequence(5);
        console.log(test.countLeaves());
        test.getSubDepth(6);
        test.getSubDepth(2);
        test.levelOrderTraverse(function (value) {
            console.log('levelOrderTraverse: ' + value);
        });
        
        var newTree = test.copyBinaryTree_stack();
        
        var node1 = test.leftChild.leftChild;
        var node2 = test.leftChild.rightChild.leftChild;
        var ancient = test.findNearAncient(node1,node2);
        console.log(ancient);
        console.log('expect false: ' + BinaryTree.isFullBinaryTree(newTree));
        console.log('lush degree: ' + test.lunshDegree());
        
        test.printPath_maxDepthS1();
        console.log(test.descNum());
      }