首页 > 其他 > 详细

二叉树

时间:2020-06-16 15:32:57      阅读:42      评论:0      收藏:0      [点我收藏+]
function BrnarySearchTree() {
      //创建节点
      function Node(key) {
        this.key = key;
        this.left = null;
        this.right = null;
      }
      //跟节点
      this.root = null;

      //插入节点
      BrnarySearchTree.prototype.insert = function (key) {
        var node = new Node(key);
        if (!this.root) {
          this.root = node
        } else {
          this.insertNode(this.root, node)
        }
      }
      //插入节点方法
      BrnarySearchTree.prototype.insertNode = function (node, newNode) {
        if (node.key > newNode.key) {
          if (!node.keft) {
            node.left = newNode
          } else {
            this.insertNode(node.left, newNode)
          }
        } else {
          if (node.key < newNode.key) {
            if (!node.right) {
              node.right = newNode
            } else {
              this.insertNode(node.right, newNode)
            }
          }
        }
      }

      //前序遍历
      BrnarySearchTree.prototype.preTree = function (node, handler) {
        if (node == null) {
          return;
        }
        handler(node.key)
        this.preTree(node.left, handler)
        this.preTree(node.right, handler)
      }

      //中序遍历
      BrnarySearchTree.prototype.midTree = function (node, handler) {
        if (node == null) {
          return;
        }
        this.midTree(node.left, handler)
        handler(node.key)
        this.midTree(node.right, handler)
      }

      //后序遍历
      BrnarySearchTree.prototype.aftTree = function (node, handler) {
        if (node == null) {
          return;
        }
        this.aftTree(node.left, handler)
        this.aftTree(node.right, handler)
        handler(node.key)
      }

      //寻找最大值
      BrnarySearchTree.prototype.max = function () {
        var node = this.root;
        var key = null;
        while (node != null) {
          key = node.key;
          node = node.right;
        }
        return key
      }

      //寻找最小值
      BrnarySearchTree.prototype.min = function () {
        var node = this.root;
        var key = null;
        while (node != null) {
          key = node.key;
          node = node.left;
        }
        return key;
      }

      //查找特定值
      BrnarySearchTree.prototype.search = function (key) {
        var node = this.root;
        while (node != null) {
          if (key > node.key) {
            node = node.right;
          } else if (key < node.key) {
            node = node.left;
          } else {
            return true
          }
        }
        return false;
      }

      //删除节点
      BrnarySearchTree.prototype.delete = function (key) {
        var node = this.root;
        var parent = this.root;
        var isLeftChild = true;

        while (node.key != key) {
          parent = node;
          if (key < node.key) {
            isLeftChild = true;
            node = node.left;
          } else {
            isLeftChild = false;
            node = node.rigth
          }
          if (node == null) {
            return false;
          }
        }

      }

      //二叉树层数
      BrnarySearchTree.prototype.getNum = function (node) {
        if (!node) return 0;
        return Math.max(this.getNum(node.left), this.getNum(node.right)) + 1
      }

    }

    var tree = new BrnarySearchTree();
    tree.insert(5)
    tree.insert(6)
    tree.insert(1)
    tree.insert(7)

    console.log(tree.root)

 

二叉树

原文:https://www.cnblogs.com/wangyisu/p/13141058.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!