实现二叉数

你的名字 2021-07-24 18:41 215阅读 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 条评论，215人围观）

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

相关阅读

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

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

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

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

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

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

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

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

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

相关求二叉树种数

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

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

相关二叉树代码实现

package cn.dataStructures.BinarySerachTree; import java.util.LinkedList;

比眉伴天荒/ 2022年05月23日 01:20/ 0 赞/ 151 阅读

相关 Python实现二叉搜索

1、什么是二叉搜索二叉搜索是在一个有序的列表中，寻找目标元素。因此我们需要对半查找即可。当目标元素比中间元素小，则在中间元素的左边查找；反之，则在目标元素的右边查找。直

桃扇骨/ 2022年05月20日 07:47/ 0 赞/ 124 阅读

相关二叉搜索树实现

本文给出二叉搜索树介绍和实现首先说它的性质：所有的节点都满足，左子树上所有的节点都比自己小，右边的都比自己大。那这个结构有什么有用呢？首先可以快速二分查找。还可以中

傷城~/ 2022年05月16日 05:29/ 0 赞/ 151 阅读

相关 Java实现二叉树

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

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

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

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

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

相关实现二叉数

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

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