实现二叉数

你的名字 2021-07-24 18:41 229阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzI5NDU2MA_size_16_color_FFFFFF_t_70]

遍历方式:
    	先序:根左右
    	中序:左根右
    	后续:左右根
    
    二叉查找:
    	左节点较小值,右节点较大值
    
    删除:
    	无子节点直接删除
    	有一个子节点,子节点替换删除的节点
    	有两个子节点,找到左树最大的值或右树最小的值替换删除的节点

代码示例:

function Node(data, left, right) {  //单个节点
      this.data = data;
      this.left = left;
      this.right = right;
    
      this.show = show;
    }
    
    function show() { 
      console.log(this.data);
      return this.data;
    }
    
    function BST() { 
      this.root = null; //根节点
      this.insert = insert; //插入
      this.inOrder = inOrder; //中序遍历
      this.getMin = getMin; //获取最小值
      this.getMax = getMax; //获取最大值
      this.find = find; //查找特定节点
      this.remove = remove; //移除节点
    }
    
    function insert(data) { 
      let n = new Node(data, null, null);
      //判断插入时,是否空树
      if (this.root == null) { 
        this.root = n;
      } else { 
        let current = this.root;
        let parent;
        while (true) { 
          parent = current; //当前节点的父节点
          if (data < current.data) {  //如果值小于当前节点左节点,则向当前节点的左节点查找
            current = current.left; //当前节点变为上一个节点的左节点
            if (current == null) {  //如果当前节点未空,则父节点的左节点指向当前插入的节点
              parent.left = n;
              break;
            } 
          } else { 
            current = current.right //如果值大于当前节点,往当前节点的右子节点查找
            if (current == null) { 
              parent.right = n;
              break;
            }
          } 
        }
      }
    }
    
    function inOrder(node) {  //中序:左根右
      if (!(node == null)) { 
        inOrder(node.left);
        console.log(node.data);
        inOrder(node.right);
      }
      
    }
    
    function getMin(root) { 
      let current = root;
      while (current.left !== null) { 
        current = current.left;
      }
    
      console.log('最小值:'+current.data);
      return current;
    
    }
    
    function getMax(root) { 
      let current = root;
      while (current.right !== null) { 
        current = current.right;
      }
    
      console.log('最大值:'+current.data);
      return current;
    }
    
    function find(data) { 
      let current = this.root;
      while (true&&current!=null) { 
        if (data < current.data) { 
          current=current.left
        } else if (data > current.data) { 
          current=current.right
        } else { 
          return current;
        }
      }
      return false;
    }
    
    function remove(data) { 
      removeNode(this.root, data);
    }
    
    function removeNode(node, data) { 
      if (node == null) { 
        return false;
      }
    
      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;
        }
        
        let tempNode = getMin(node.right); //两个子节点找到左树最大的值或右树最小的值替换删除的节点
        node.data = tempNode.data;
        node.right = removeNode(node.right, tempNode.data);
        return node;
    
      } else if (data < node.data) { 
        node.left = removeNode(node.left, data);
        return node;
      } else { 
        node.right = removeNode(node.right, data);
        return node;
      }
    }
    
    
    let nums = new BST();
    nums.insert(23);
    nums.insert(45);
    nums.insert(16);
    nums.insert(37);
    nums.insert(3);
    nums.insert(99);
    nums.insert(22);
    console.log('遍历节点');
    nums.inOrder(nums.root);
    
    getMin(nums.root);
    getMax(nums.root);
    
    nums.remove(16)
    nums.remove(37)
    
    nums.inOrder(nums.root);

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzI5NDU2MA_size_16_color_FFFFFF_t_70]: /images/20210724/5c1a2ee72df64492a7efed5d9036cf5c.png

发表评论取消回复

表情：

评论列表（有 0 条评论，229人围观）

还没有评论，来说两句吧...

相关阅读

相关对称二叉数[简单]

优质博文：[IT-BLOG-CN][] 一、题目给你一个二叉树的根节点`root`，检查它是否轴对称。示例 1： ![e10f3cfb9764439e84bc

红太狼/ 2024年02月19日 11:03/ 0 赞/ 6 阅读

相关二叉树的边数和节点数关系

问题: 若一棵二叉树具有12个度为2的结点，6个度为1的结点，则度为0的结点个数是（）。 A 10 B 11 C 13 D 不确定正确答案： C 结

小咪咪/ 2023年10月04日 18:33/ 0 赞/ 34 阅读

相关生成二叉数及二叉树的遍历

生成二叉数及二叉树的遍历中序生成满二叉数 linkedQueue<binaryTreeNode<char> > q; void insertByLev

不念不忘少年蓝@/ 2023年06月13日 11:08/ 0 赞/ 25 阅读

相关 C语言实现二叉树---＞二叉查找树

声明代码实现都是自己写的，而且没有借鉴别人的代码，也没有看任何教程，只看了下二叉树的具体定义，知道大概是个什么东西说这些只是为了说明下列代码实现肯定不是最优的，甚

柔情只为你懂/ 2023年01月13日 06:19/ 0 赞/ 232 阅读

相关 python实现mysql二叉树_Python 二叉树实现

\二叉树实现 class Node(): def \_\_init\_\_(self,item): self.elem = item self.lchild = Non

一时失言乱红尘/ 2022年10月31日 15:54/ 0 赞/ 197 阅读

相关【二叉树】二叉搜索树中的众数（leetcode501）

一、题目给定一个有相同值的二叉搜索树（BST），找出 BST 中的所有众数（出现频率最高的元素）。假定 BST 有如下定义：

缺乏、安全感/ 2022年10月18日 12:42/ 0 赞/ 188 阅读

相关求二叉树种数

题：已知一棵二叉树，先序遍历为CABDFGE，后序遍历为BDAEGFC。求数的样子有多少种？思路：先序遍历的首字母和后序遍历的尾字母是树的根。利用试探法确定左右子树的情况。

Myth丶恋晨/ 2022年06月10日 05:09/ 0 赞/ 172 阅读

相关 Java实现二叉树

这里创建二叉树是顺序结构存储二叉树原理，即一个节点 i 的左孩子为 i\2+1,右孩子为 i\2+2。程序创建的二叉树如图所示： ![70][] Demo： im

缺乏、安全感/ 2022年05月14日 07:36/ 0 赞/ 190 阅读

相关二叉树节点数及叶子节点数

继续二叉树系列的代码内容。今天写的是求二叉树节点个数及叶子节点个数的代码。采用了递归的方法求解。代码如下： include "stdafx.h" i

本是古典何须时尚/ 2022年04月10日 01:54/ 0 赞/ 238 阅读

相关实现二叉数

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

你的名字/ 2021年07月24日 18:41/ 0 赞/ 230 阅读