数据结构150-二叉搜索树-删除节点没有子节点代码-阿里云开发者社区

数据结构150-二叉搜索树-删除节点没有子节点代码

2023-02-11 108

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 数据结构150-二叉搜索树-删除节点没有子节点代码

<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta http-equiv="X-UA-Compatible" content="IE=edge" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>封装二叉搜索树</title>
  </head>
  <body>
    <script>
      function BinarySearchTree() {
        function Node(key) {
          this.key = null;
          this.left = null;
          this.right - null;
        }
        this.root = null;
        BinarySearchTree.prototype.insert = function (key) {
          var newNode = new Node(key);
          //判断节点是否有值
          if (this.root == null) {
            this.root = newNode;
          } else {
            this.insertNode(this.root, newNode);
          }
        };
        BinarySearchTree.prototype.insertNode = function (node, newNode) {
          if (newNode.key < node.key) {
            if (node.left == null) {
              node.left = newNode;
            } else {
              this.insertNode(node.left, newNode);
            }
          } else {
            if (node.right == null) {
              node.right = newNode;
            } else {
              this.insertNode(node.right, newNode);
            }
          }
        };
        //先序遍历
        BinarySearchTree.prototype.preOrderTraversal = function (handler) {
          this.preOrderTraversalNode(this.root, handler);
        };
        BinarySearchTree.prototype.preOrderTraversalNode = function (
          node,
          handler
        ) {
          if (node != null) {
            //处理经过的节点
            handler(node.key);
            this.preOrderTraversalNode(node.left, handler);
            this.preOrderTraversalNode(node.right, handler);
          }
        };
        //中序遍历
        BinarySearchTree.prototype.middleOrderTraversal = function (handler) {
          this.middleOrderTraversalNode(this.root, handler);
        };
        BinarySearchTree.prototype.middleOrderTraversalNode = function (
          node,
          handler
        ) {
          if (node != null) {
            //处理经过的节点
            handler(node.key);
            this.preOrderTraversalNode(node.left, handler);
            handler(node.key)
            this.preOrderTraversalNode(node.right, handler);
          }
        };
        //中序遍历
        BinarySearchTree.prototype.postOrderTraversal = function (handler) {
          this.postOrderTraversalNode(this.root, handler);
        };
        BinarySearchTree.prototype.postOrderTraversalNode = function (
          node,
          handler
        ) {
          if (node != null) {
            //处理经过的节点
            handler(node.key);
            this.postOrderTraversalNode(node.left, handler);
            this.postOrderTraversalNode(node.right, handler);
            handler(node.key)
          }
        };
        BinarySearchTree.prototype.max = function (){
            var node=this.root
            var key=null
            while(node!=null){
                key=node.key
                node=node.right
            }
            return key
        }
        BinarySearchTree.prototype.min = function (){
            var node=this.root
            var key=null
            while(node!=null){
                key=node.key
                node=node.left
            }
            return key
        }
        BinarySearchTree.prototype.search = function (){
            var node=this.root
            while(node!=key){
                if(key<node.key){
                    node=node.left
                }else if(key>node.key){
                    node=node.key
                }else{
                  return  true
                }
            }
            return false
        }
        BinarySearchTree.prototype.remove = function (key){
            //
            var current=this.root
            var parent=null
            var isLeftChild=true
            while(current.key!=key){
                parent=current
                if(key<current.key){
                    isLeftChild=true
                    current=current.left
                }else{
                    isLeftChild=false
                    current=current.right
                }
                //已经找最后节点
                if(current==null) return false
            }
            //
            if(current.left==null&¤t.right==null){
                if(current==this.root){
                    this.root=null
                }else if(isLeftChild){
                    parent.left=null
                }else{
                    parent.right=null
                }
            }
        }
      }
    </script>
  </body>
</html>

数据结构150-二叉搜索树-删除节点没有子节点代码

热门文章

最新文章

相关课程

相关电子书

探索云世界

热门

云计算

大数据

云原生

人工智能

数据库

开发与运维

活动广场

任务中心

训练营

直播

乘风者计划

下载

镜像站

技术资料

数据结构150-二叉搜索树-删除节点没有子节点代码

热门文章

最新文章

相关课程

相关电子书