美文网首页
二叉树实现

二叉树实现

作者: lmmy123 | 来源:发表于2019-10-09 17:43 被阅读0次
今天实现一下二叉树
/**
  * 二叉树
  * 二叉链表
  */
 function Node(data){
     this.data = data
     this.left = null
     this.right = null
 }
 
 class Bst {
     constructor(){
         this.root = null
     }
     
     /**
      * 首先创建一个节点,判断是否有根节点
      *  根据值的大小往左右节点查找,直到找到空节点(null)为止
      *  这个新的节点就插在这个空节点的位置
      */
     insert(data){
         let newNode = new Node(data)
         if(this.root === null){
             this.root = newNode
         }else{
             let current = this.root
             let parent
             /**从根节点向下查到,找到空节点 为止, 得到parent */
             while(current){
                 parent = current
                 if(data < current.data){
                     current = current.left
                 }else{
                     current = current.right
                 }
             }
             // 通过上面找到的parent和 新值做对比,决定放在左还是右
             if(data < parent.data){
                 parent.left = newNode
             }else{
                 parent.right = newNode
             }
         }
     }
     // 查找最小值,即在左边树查找, 最大值则相反
     min(){
         if(this.root == null) return null
         let current = this.root
         while(current.left !== null){
             current = current.left
         }
         return current.data
     }

     find(data){
         let current = this.root
         while(current !== null){
             if(current.data == data){
                 return current
             }
             if(current.data > data){
                 current = current.left
             }else{
                 current = current.right
             }
         }
         return null
     }
 }
 // 遍历 ,更加根节点的遍历循序
 function preOrder(node){
     if(node === null) return
     if(typeof node == 'undefined'){
        node = this.root;
     }
     console.log(node.data)
     preOrder(node.left)
     preOrder(node.right)
 }
 function midOrder(node){
    if(node === null) return
    if(typeof node == 'undefined'){
       node = this.root;
    }
     midOrder(node.left)
     console.log(node.data)
     midOrder(node.right)
 }
 function backOrder(node){
    if(node === null) return
    if(typeof node == 'undefined'){
       node = this.root;
    }
    backOrder(node.left)
    backOrder(node.right)
    console.log(node.data)
 }

 
 let a = new Bst()
 a.insert(11);
a.insert(3);
a.insert(5);
a.insert(1);
//  console.log(a,a.root, a.left, a.right)
 console.log(preOrder(a.root))
 console.log(midOrder(a.root))
 console.log(backOrder(a.root))

相关文章

  • python实现二叉树

    递归实现二叉树 堆实现二叉树前序遍历

  • 算法之二叉树

    二叉树之C++实现 创建二叉树 复制二叉树 先序遍历 递归实现 非递归实现 中序遍历 递归实现 非递归实现 后序遍...

  • 数据结构之树的相关问题

    实验要求 实现二叉树的抽象数据类型 实现二叉树的建立的运算 实现二叉树的遍历运算 实现创建哈夫曼树的算法 实验代码...

  • 2. 二叉树 BinTree

    二叉树的实现 BinNode : 二叉树结点 二叉树结点结构代码 : 二叉树常用接口实现 将新结点作为左/右孩子插...

  • 力扣算法 - 翻转二叉树

    翻转二叉树 翻转一棵二叉树。 示例: 输入: 输出: 思路: Java实现 Swift实现

  • 二叉树的实现

    二叉树的节点 二叉树的实现 测试

  • 面试算法--递归/循环实现二叉树的前丶中丶后序遍历

    一丶利用二叉树前序顺序构建二叉树 "#" 代表空结点 二丶递归实现二叉树前中后序遍历 三丶循环实现二叉树前中后序遍...

  • 数据结构之二叉树

    数据结构之二叉树 递归构造二叉树 二叉树节点: 递归构造: 图示: 递归遍历 递归实现先序遍历 图示: 递归实现中...

  • Java二叉树的遍历

    Java二叉树的遍历 利用递归和非递归实现二叉树的先序,中序,后序遍历以及使用队列实现二叉树的层次遍历

  • 二叉树查找与节点删除的javascript实现

    前言 紧接前面说过的 二叉树的实现 和 二叉树的遍历,今天来说一下用javascript实现二叉树的查找和节点删除...

网友评论

      本文标题:二叉树实现

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