美文网首页
二叉树

二叉树

作者: _旁观者_ | 来源:发表于2018-11-19 17:51 被阅读0次

本文内容学习自JavaScript实现二叉树

二叉树

  • 二叉树是每个节点最多有两个子树的树结构。通常子树被称左子树和右子树。

  • 二叉树的每个结点至多只有二棵子树(不存在度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒。

  • 二叉树的第i层至多有2^{i-1} 个结点（顶层为第一层）

二叉树遍历

  • 前序遍历就是先访问树的根节点，再访问树的左子节点，再访问右子节点。

  • 中序遍历就是先访问树的左子节点，再访问树的根节点，再访问右子节点。

  • 后序遍历就是先访问树的左子节点，再访问树的右子节点，再访问根节点。

创建二叉树

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

        //创建节点
        var Node = function (key) {
          this.key = key;
          this.left = null;
          this.right = null;
        }

        //创建根节点
        var root = null;
        this.insert = function (key) { //创建二叉树数据结构
          var newNode = new Node(key);
          if (root === null) {
            root = newNode;
          } else {
            insertNode(root, newNode);
          }
        }
        var insertNode = function (node, newNode) { // 比较节点，插入到相应节点的左右节点上
          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;
          }
        }

删除末节点

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

删除节点 包括末节点和中间节点 

        this.remove = function (key) {
          root = removeNode(root, key);
        }
        var removeNode = function (node, key) {
          if (node === null) {
            return null;
          }
          if (key < node.key) { // 小于此节点的key，node赋值为 node.left 继续遍历
            node.left = removeNode(node.left, key);
            return node;
          } else if (key > node.key) { // 大于此节点的key，node赋值为 node.right 继续遍历
            node.right = removeNode(node.right, key);
            return node;
          } else { // 等于此节点的key ， 1 末节点 ， 2 中间节点

            // 末节点直接把此key赋值为null
            if (node.left === null && node.right === null) {
              node = null;
              return node;
            }
            // 中间节点
            // 1，有right 或 left时，把此节点的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 ， 找到此节点右侧的最小值赋值  node = node.right的最小值
            var aux = findMinNode(node.right);
            node.key = aux.key;
            node.right = removeNode(node.right, aux.key);
            return node;
          }
        }
        //找到最小节点
        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() {

        //创建节点
        var Node = function (key) {
          this.key = key;
          this.left = null;
          this.right = null;
        }

        //创建根节点
        var root = null;
        this.insert = function (key) { //创建二叉树数据结构
          var newNode = new Node(key);
          if (root === null) {
            root = newNode;
          } else {
            insertNode(root, newNode);
          }
        }
        var insertNode = function (node, newNode) { // 比较节点，插入到相应节点的左右节点上
          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;
          }
        }

        // 删除末节点
        // 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;
        //     }
        //   }
        // }

        // 删除节点
        this.remove = function (key) {
          root = removeNode(root, key);
        }
        var removeNode = function (node, key) {
          if (node === null) {
            return null;
          }
          if (key < node.key) { // 小于此节点的key，node赋值为 node.left 继续遍历
            node.left = removeNode(node.left, key);
            return node;
          } else if (key > node.key) { // 大于此节点的key，node赋值为 node.right 继续遍历
            node.right = removeNode(node.right, key);
            return node;
          } else { // 等于此节点的key ， 1 末节点 ， 2 中间节点

            // 末节点直接把此key赋值为null
            if (node.left === null && node.right === null) {
              node = null;
              return node;
            }
            // 中间节点
            // 1，有right 或 left时，把此节点的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 ， 找到此节点右侧的最小值赋值  node = node.right的最小值
            var aux = findMinNode(node.right);
            node.key = aux.key;
            node.right = removeNode(node.right, aux.key);
            return node;
          }
        }
        //找到最小节点
        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('------删除末节点‘1’值---------')
      // binaryTree.remove(1);
      // binaryTree.postOrderTraverse(callback);
      console.log('------删除节点3---------')
      binaryTree.remove(3);
      binaryTree.postOrderTraverse(callback);
    </script>
  </body>
</html>

相关文章

  • 数据结构与算法-二叉树02

    二叉树的定义 二叉树的特点 二叉树的五中基本形态 其他二叉树 斜二叉树 满二叉树 完全二叉树图片.png满二叉树一...

  • 二叉树

    二叉树 高度 深度真二叉树 满二叉树 完全二叉树 二叉树遍历前序 中序 后序层序遍历 翻转二叉树 递归法...

  • 二叉树 基础操作

    二叉树的使用 二叉树结构 先序创建二叉树 DFS 先序遍历二叉树 中序遍历二叉树 后序遍历二叉树 BFS 层次遍历...

  • 树与二叉树

    **树 ** 二叉树 满二叉树 完全二叉树 三种遍历方法 树与二叉树的区别 二叉查找树 平衡二叉树 红黑二叉树

  • 二叉树的宽度优先搜索（层次遍历，BFS）

    二叉树结构： 二叉树宽度优先搜索： 按照二叉树的层数依次从左到右访问二叉树的节点；例如：给定一个二叉树： 按照宽度...

  • 剑指 offer：39、平衡二叉树

    39. 平衡二叉树 题目描述 输入一棵二叉树，判断该二叉树是否是平衡二叉树。 解题思路： 平衡二叉树：Wiki:在...

  • Algorithm小白入门 -- 二叉树

    二叉树二叉树构造二叉树寻找重复子树 1. 二叉树 基本二叉树节点如下： 很多经典算法，比如回溯、动态规划、分治算法...

  • 14-树&二叉树&真二叉树&满二叉树

    一、树 二、二叉树 三、真二叉树 四、满二叉树

  • 二叉树的应用

    完美二叉树（满二叉树） 除了最下一层的节点外，每层节点都有两个子节点的二叉树为满二叉树 完全二叉树 除二叉树最后一...

  • 12.树Tree（2）

    目录:1.二叉树的基本概念2.二叉树的性质3.二叉树的创建4.二叉树的遍历 1.二叉树的基本概念 2.二叉树的性质...

网友评论

      本文标题：二叉树

      本文链接：https://www.haomeiwen.com/subject/xcpafqtx.html

      延伸阅读

      深度阅读

      • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

      栏目导航

      热点阅读

      关于我们|服务条款|联系我们|二叉树|投稿指南|网站地图|RSS订阅|排版工具|手机版

      提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

      Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

      备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

      本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

      所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！