二叉樹

本文內容學習自JavaScript實現(xiàn)二叉樹

二叉樹

  • 二叉樹是每個節(jié)點最多有兩個子樹的樹結構。通常子樹被稱左子樹和右子樹。

  • 二叉樹的每個結點至多只有二棵子樹(不存在度大于2的結點)，二叉樹的子樹有左右之分，次序不能顛倒。

  • 二叉樹的第i層至多有2^{i-1} 個結點（頂層為第一層）

二叉樹遍歷

  • 前序遍歷就是先訪問樹的根節(jié)點，再訪問樹的左子節(jié)點，再訪問右子節(jié)點。

  • 中序遍歷就是先訪問樹的左子節(jié)點，再訪問樹的根節(jié)點，再訪問右子節(jié)點。

  • 后序遍歷就是先訪問樹的左子節(jié)點，再訪問樹的右子節(jié)點，再訪問根節(jié)點。

創(chuàng)建二叉樹

<!DOCTYPE html>
<html>
  <head>
    <meta charset="UTF-8">
    <title>二叉樹</title>
  </head>
  <body>
    <script>
      function BinaryTree() {

        //創(chuàng)建節(jié)點
        var Node = function (key) {
          this.key = key;
          this.left = null;
          this.right = null;
        }

        //創(chuàng)建根節(jié)點
        var root = null;
        this.insert = function (key) { //創(chuàng)建二叉樹數(shù)據(jù)結構
          var newNode = new Node(key);
          if (root === null) {
            root = newNode;
          } else {
            insertNode(root, newNode);
          }
        }
        var insertNode = function (node, newNode) { // 比較節(jié)點，插入到相應節(jié)點的左右節(jié)點上
          if (newNode.key < node.key) {
            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);
            }
          }
        }
      }
    </script>
  </body>
</html>

中序遍歷

      // 中序遍歷
        this.inOrderTraverse = function (callback) {
          inOrderTraverseNode(root, callback);
        }
        var inOrderTraverseNode = function (node, callback) {
          if (node !== null) {
            inOrderTraverseNode(node.left, callback);
            callback(node.key);
            inOrderTraverseNode(node.right, callback);
          }
        }
      var callback = function (key) {
        console.log(key);
      }

前序遍歷

// 前序遍歷
        this.preOrderTraverse = function (callback) {
          preOrderTraverseNode(root, callback);
        }
        var preOrderTraverseNode = function (node, callback) {
          if (node !== null) {
            callback(node.key);
            preOrderTraverseNode(node.left, callback);
            preOrderTraverseNode(node.right, callback);
          }
        }
      var callback = function (key) {
        console.log(key);
      }

后序遍歷

        this.postOrderTraverse = function (callback) {
          postOrderTraverseNode(root, callback);
        }
        var postOrderTraverseNode = function (node, callback) {
          if (node !== null) {
            postOrderTraverseNode(node.left, callback);
            postOrderTraverseNode(node.right, callback);
            callback(node.key);
          }
        }
      var callback = function (key) {
        console.log(key);
      }

最小值

        this.min = function () {
          return minNode(root);
        }
        var minNode = function (node) {
          if (node) {
            while (node && node.left !== null) {
              node = node.left;
            }
            return node.key;
          }
          return null;
        }

最大值

        this.max = function () {
          return maxNode(root);
        }
        var maxNode = function (node) {
          if (node) {
            while (node && node.right !== null) {
              node = node.right;
            }
            return node.key;
          }
          return null;
        }

查找某個值

        this.search = function (key) {
          return searchNode(root, key);
        }
        var searchNode = function (node, key) {
          if (node == null) {
            return false;
          }
          if (key < node.key) {
            return searchNode(node.left, key);
          } else if (key > node.key) {
            return searchNode(node.right, key);
          } else {
            return true;
          }
        }

刪除末節(jié)點

        this.remove = function (key) {
          root = removeNode(root, key);
        }
        var removeNode = function (node, key) {
          if (node === null) {
            return null;
          }
          if (key < node.key) {
            node.left = removeNode(node.left, key);
            return node;
          } else if (key > node.key) {
            node.right = removeNode(node.right, key);
            return node;
          } else {
            if (node.left === null && node.right === null) {
              node = null;
              return node;
            }
          }
        }

刪除節(jié)點 包括末節(jié)點和中間節(jié)點 

        this.remove = function (key) {
          root = removeNode(root, key);
        }
        var removeNode = function (node, key) {
          if (node === null) {
            return null;
          }
          if (key < node.key) { // 小于此節(jié)點的key，node賦值為 node.left 繼續(xù)遍歷
            node.left = removeNode(node.left, key);
            return node;
          } else if (key > node.key) { // 大于此節(jié)點的key，node賦值為 node.right 繼續(xù)遍歷
            node.right = removeNode(node.right, key);
            return node;
          } else { // 等于此節(jié)點的key ， 1 末節(jié)點 ， 2 中間節(jié)點

            // 末節(jié)點直接把此key賦值為null
            if (node.left === null && node.right === null) {
              node = null;
              return node;
            }
            // 中間節(jié)點
            // 1，有right 或 left時，把此節(jié)點的left或right賦值為node = node.left 或 node = node.right
            if (node.left === null) {
              node = node.right;
              return node;
            } else if (node.right === null) {
              node = node.left;
              return node;
            }
            // 2，同時有right和left ， 找到此節(jié)點右側的最小值賦值  node = node.right的最小值
            var aux = findMinNode(node.right);
            node.key = aux.key;
            node.right = removeNode(node.right, aux.key);
            return node;
          }
        }
        //找到最小節(jié)點
        var findMinNode = function (node) {
          if (node) {
            while (node && node.left !== null) {
              node = node.left;
            }
            return node;
          }
          return null;
        }

完整代碼

<!DOCTYPE html>
<html>
  <head>
    <meta charset="UTF-8">
    <title>二叉樹</title>
  </head>
  <body>
    <script>
      function BinaryTree() {

        //創(chuàng)建節(jié)點
        var Node = function (key) {
          this.key = key;
          this.left = null;
          this.right = null;
        }

        //創(chuàng)建根節(jié)點
        var root = null;
        this.insert = function (key) { //創(chuàng)建二叉樹數(shù)據(jù)結構
          var newNode = new Node(key);
          if (root === null) {
            root = newNode;
          } else {
            insertNode(root, newNode);
          }
        }
        var insertNode = function (node, newNode) { // 比較節(jié)點，插入到相應節(jié)點的左右節(jié)點上
          if (newNode.key < node.key) {
            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);
            }
          }
        }

        // 中序遍歷
        this.inOrderTraverse = function (callback) {
          inOrderTraverseNode(root, callback);
        }
        var inOrderTraverseNode = function (node, callback) {
          if (node !== null) {
            inOrderTraverseNode(node.left, callback);
            callback(node.key);
            inOrderTraverseNode(node.right, callback);
          }
        }

        // 前序遍歷
        this.preOrderTraverse = function (callback) {
          preOrderTraverseNode(root, callback);
        }
        var preOrderTraverseNode = function (node, callback) {
          if (node !== null) {
            callback(node.key);
            preOrderTraverseNode(node.left, callback);
            preOrderTraverseNode(node.right, callback);
          }
        }

        // 后序遍歷
        this.postOrderTraverse = function (callback) {
          postOrderTraverseNode(root, callback);
        }
        var postOrderTraverseNode = function (node, callback) {
          if (node !== null) {
            postOrderTraverseNode(node.left, callback);
            postOrderTraverseNode(node.right, callback);
            callback(node.key);
          }
        }

        // 最小值
        this.min = function () {
          return minNode(root);
        }
        var minNode = function (node) {
          if (node) {
            while (node && node.left !== null) {
              node = node.left;
            }
            return node.key;
          }
          return null;
        }

        // 最大值
        this.max = function () {
          return maxNode(root);
        }
        var maxNode = function (node) {
          if (node) {
            while (node && node.right !== null) {
              node = node.right;
            }
            return node.key;
          }
          return null;
        }

        // 查找某個值
        this.search = function (key) {
          return searchNode(root, key);
        }
        var searchNode = function (node, key) {
          if (node == null) {
            return false;
          }
          if (key < node.key) {
            return searchNode(node.left, key);
          } else if (key > node.key) {
            return searchNode(node.right, key);
          } else {
            return true;
          }
        }

        // 刪除末節(jié)點
        // this.remove = function (key) {
        //   root = removeNode(root, key);
        // }
        // var removeNode = function (node, key) {
        //   if (node === null) {
        //     return null;
        //   }
        //   if (key < node.key) {
        //     node.left = removeNode(node.left, key);
        //     return node;
        //   } else if (key > node.key) {
        //     node.right = removeNode(node.right, key);
        //     return node;
        //   } else {
        //     if (node.left === null && node.right === null) {
        //       node = null;
        //       return node;
        //     }
        //   }
        // }

        // 刪除節(jié)點
        this.remove = function (key) {
          root = removeNode(root, key);
        }
        var removeNode = function (node, key) {
          if (node === null) {
            return null;
          }
          if (key < node.key) { // 小于此節(jié)點的key，node賦值為 node.left 繼續(xù)遍歷
            node.left = removeNode(node.left, key);
            return node;
          } else if (key > node.key) { // 大于此節(jié)點的key，node賦值為 node.right 繼續(xù)遍歷
            node.right = removeNode(node.right, key);
            return node;
          } else { // 等于此節(jié)點的key ， 1 末節(jié)點 ， 2 中間節(jié)點

            // 末節(jié)點直接把此key賦值為null
            if (node.left === null && node.right === null) {
              node = null;
              return node;
            }
            // 中間節(jié)點
            // 1，有right 或 left時，把此節(jié)點的left或right賦值為node = node.left 或 node = node.right
            if (node.left === null) {
              node = node.right;
              return node;
            } else if (node.right === null) {
              node = node.left;
              return node;
            }
            // 2，同時有right和left ， 找到此節(jié)點右側的最小值賦值  node = node.right的最小值
            var aux = findMinNode(node.right);
            node.key = aux.key;
            node.right = removeNode(node.right, aux.key);
            return node;
          }
        }
        //找到最小節(jié)點
        var findMinNode = function (node) {
          if (node) {
            while (node && node.left !== null) {
              node = node.left;
            }
            return node;
          }
          return null;
        }

      }
      var callback = function (key) {
        console.log(key);
      }

      var nodes = [8, 3, 10, 1, 6, 14, 4, 7, 13];
      var binaryTree = new BinaryTree();
      nodes.forEach(function (key) {
        binaryTree.insert(key);
      })
      console.log('------中序遍歷---------')
      binaryTree.inOrderTraverse(callback);
      console.log('------前序遍歷---------')
      binaryTree.preOrderTraverse(callback);
      console.log('------后序遍歷---------')
      binaryTree.postOrderTraverse(callback);
      console.log('------最小值---------')
      console.log(binaryTree.min());
      console.log('------最大值---------')
      console.log(binaryTree.max());
      console.log('------某個值---------')
      console.log(binaryTree.search(3));
      console.log(binaryTree.search(2));
      // console.log('------刪除末節(jié)點‘1’值---------')
      // binaryTree.remove(1);
      // binaryTree.postOrderTraverse(callback);
      console.log('------刪除節(jié)點3---------')
      binaryTree.remove(3);
      binaryTree.postOrderTraverse(callback);
    </script>
  </body>
</html>
最后編輯于 ：
?著作權歸作者所有,轉載或內容合作請聯(lián)系作者
【社區(qū)內容提示】社區(qū)部分內容疑似由AI輔助生成，瀏覽時請結合常識與多方信息審慎甄別。
平臺聲明：文章內容（如有圖片或視頻亦包括在內）由作者上傳并發(fā)布，文章內容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務。

相關閱讀更多精彩內容

友情鏈接更多精彩內容