JS 实现二叉树

Yu_Huang 发布于2019-08-21 17:34 / 703人阅读

摘要：二叉树定义二叉排序树二叉平衡树二叉树定义二叉树是每个节点最多只有两个分支不存在分支度大于的节点的树结构。通常分支被称为左子树和右子树。二叉树的分支具有左右次序，不能颠倒。

① 二叉树定义
② 二叉排序树
③ 二叉平衡树

① 二叉树定义

二叉树（Binary tree）是每个节点最多只有两个分支(不存在分支度大于2的节点)的树结构。通常分支被称为「左子树」和「右子树」。二叉树的分支具有左右次序，不能颠倒。

② 二叉排序树

简单定义
二叉排序树又称为二叉搜索树或二叉查找树
特征
(1) 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值
(2) 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值
(3) 它的左、右子树也分别为二叉查找树
Javascript实现

function BinarySearchTree(keys){
  //Node构造函数
  let Node = function (key){
     this.key = key
     this.left = null
     this.right = null
  }
  let root = null
  let insertNode = (node,newNode)=>{
     if(newNode.key < node.key){
       if(node.left === null){
         node.left = newNode
       }else {
         insertNode(node.left,newNode)
       }
     }else {
       if (node.right === null) {
         node.right = newNode
       }else {
         insertNode(node.right,newNode)
       }
     }
  }
  this.insert = (key)=>{
     let newNode = new Node(key)
     if (root === null) {
       root = newNode
     }else {
       insertNode(root,newNode)
     }
  }
  keys.forEach((key)=>{
   this.insert(key)
  })
  return root
}
const keys = [8,3,10,1,6,14,4,7,13]
BinarySearchTree(keys)

chrome中打印如下：

效果图：

中序遍历
中序遍历的递归定义：先左子树，后根节点，再右子树

let inOrderTraverseFunction =(node,cb)=>{
   if(node!==null){
      inOrderTraverseFunction(node.left,cb)
      cb(node.key)
      inOrderTraverseFunction(node.right,cb)
   }
} 
let callback =(key)=>{
  console.log(key)
}
//BST的中序遍历
inOrderTraverseFunction(BinarySearchTree(keys),callback)

chrome中打印如下：

结果：整颗二叉树节点以从小到大依次显示

前序遍历
前序遍历的递归定义：先根节点，后左子树，再右子树

let preOrderTraverseFunction =(node,cb)=>{
   if(node!==null){
      cb(node.key)
      preOrderTraverseFunction(node.left,cb)
      preOrderTraverseFunction(node.right,cb)
   }
} 
//BST前序遍历
preOrderTraverseFunction(BinarySearchTree(keys),callback)

chrome打印如下

后序遍历
后序遍历的递归定义：先左子树，后右子树，再根节点

let postOrderTraverseFunction =(node,cb)=>{
   if(node!==null){
      postOrderTraverseFunction(node.left,cb)
      postOrderTraverseFunction(node.right,cb)
      cb(node.key)
   }
} 
//BST后序遍历
postOrderTraverseFunction(BinarySearchTree(keys),callback)

chrome打印如下

查找BST最小值
白话:即二叉树左子树最左侧的那个没有左子树的节点

let minNode =(node)=>{
  if(node){
    while (node&&node.left !== null){
       node = node.left
    }
    return node.key
  }
  return null
}
//查找BST最小值
console.log("the min node is "+minNode(BinarySearchTree(keys)))

chrome打印如下

查找BST最大值
白话:即二叉树右子树最右侧的那个没有右子树的节点

let maxNode =(node)=>{
  if(node){
    while (node&&node.right !== null){
       node = node.right
    }
    return node.key
  }
  return null
}
//查找BST最大值
console.log("the max node is "+maxNode(BinarySearchTree(keys)))

chrome打印如下

查找BST某个值
即将该值和每个节点比较如果该值比此节点小则进入左子树再递归比较反之如果该值比此节点大则进入右子树再递归比较

let searchNode = (node,key)=>{
  if(node === null){
    return false   
  }
  if(keynode.key) {
    return searchNode(node.right,key)
  }else{
    return true
  }
}
//BST查找某个值
console.log(searchNode(BinarySearchTree(keys),3)?"node 3 is found":"node 3 is not found")
console.log(searchNode(BinarySearchTree(keys),5)?"node 5 is found":"node 5 is not found")

chrome打印如下:

删除BST某个叶子节点
叶子节点：没有左子树和右子树的节点

let removeNode = (node,key)=>{
  if(node === null){
    return null
  }
  if(keynode.key){
    node.right = removeNode(node.right,key)
    return node
  } else{
    if(node.left === null && node.right === null){
      node = null
      return node
    }
  }
}
//BST删除某个叶子节点
console.log(removeNode(BinarySearchTree(keys),1),BinarySearchTree(keys))

chrome打印如下:

效果图：

删除BST某个度为1的节点

let removeNode = (node,key)=>{
  if(node === null){
    return null
  }
  if(keynode.key){
    node.right = removeNode(node.right,key)
    return node
  } else{
    if(node.left === null && node.right === null){
      node = null
      return node
    }
    if(node.left === null){
      node = node.right
      return node
    }else if (node.right === null) {
      node = node.left
      return node     
    }
  }
}
//BST删除某个度为1的子节点
console.log(removeNode(BinarySearchTree(keys),10),BinarySearchTree(keys))

chrome打印如下:

效果图：

删除BST某个度为2的节点

let findMinNode = (node) =>{
  if(node){
    while(node&& node.left !== null){
      node = node.left
    }
    return node 
  }
  return null
}
let removeNode = (node,key)=>{
  if(node === null){
    return null
  }
  if(keynode.key){
    node.right = removeNode(node.right,key)
    return node
  } else{
    if(node.left === null && node.right === null){
      node = null
      return node
    }
    if(node.left === null){
      node = node.right
      return node
    }else if (node.right === null) {
      node = node.left
      return node     
    }
    let minNode = findMinNode(node.right) 
    node.key = minNode.key
    node.right = removeNode(node.right,minNode.key)
    return node
  }
}
//BST删除某个度为2的子节点
console.log(removeNode(BinarySearchTree(keys),3),BinarySearchTree(keys))

chrome打印如下:

效果图：

未完待续

云服务器 GPU云服务器实现二叉树 JS二叉树遍历 js怎么建二叉树二叉树

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/89704.html

js数据结构和算法（三）二叉树

摘要：同样结点树的二叉树，完全二叉树的深度最小。二叉树每个结点最多有两个孩子，所以为它设计一个数据域和两个指针域是比较自然的想法，我们称这样的链表叫做二叉链表。二叉树的概念二叉树（Binary Tree）是n（n>=0）个结点的有限集合，该集合或者为空集（空二叉树），或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。 showImg(https://seg...

DesGemini 2019-08-21 10:20 评论0 收藏0
js 中二叉树的深度遍历与广度遍历(递归实现与非递归实现)

摘要：树中结点的最大层次称为树的深度或高度。二叉树有深度遍历和广度遍历，深度遍历有前序中序和后序三种遍历方法。二叉树的前序遍历可以用来显示目录结构等中序遍历可以实现表达式树，在编译器底层很有用后序遍历可以用来实现计算目录内的文件及其信息等。树的简介栈、队列、链表等数据结构，都是顺序数据结构。而树是非顺序数据结构。树型结构是一类非常重要的非线性结构。直观地，树型结构是以分支关系定义的层次结...

Yuanf 2019-08-23 11:38 评论0 收藏0
用JS实现数据结构----排序二叉树

摘要：代码实现创建一个排序二叉树节点类根节点插入节点以上便是创建排序二叉树的实现方式重点在于插入节点的具体实现，即注释的代码片段。排序二叉树 showImg(https://segmentfault.com/img/bVbfdbp?w=1047&h=472); 如上图为典型的排序二叉树，左孩子的值比节点的值小，右孩子的值比节点的值大，关于具体的树的定义及二叉树的定义可以百度或查阅相关资料。...

ispring 2019-08-23 11:00 评论0 收藏0
js数据结构-二叉树（二叉搜索树）

摘要：前言可能有一部分人没有读过我上一篇写的二叉堆，所以这里把二叉树的基本概念复制过来了，如果读过的人可以忽略前面针对二叉树基本概念的介绍，另外如果对链表数据结构不清楚的最好先看一下本人之前写的数据结构链表二叉树二叉树是一种树形结构，它的特点是前言可能有一部分人没有读过我上一篇写的二叉堆，所以这里把二叉树的基本概念复制过来了，如果读过的人可以忽略前面针对二叉树基本概念的介绍，另外如果对链...

codeKK 2019-08-23 14:34 评论0 收藏0
二叉树的递归遍历（JS实现）

摘要：本文讨论二叉树的遍历，对节点的访问通过打印节点的值体现出来。从二叉树的根节点出发，遍历可分为三个环节访问节点打印节点的值遍历节点的左子树遍历节点的右子树不同环节执行的先后顺序产生了不同的遍历方式。至于二叉树的非递归遍历，且听下回分解。相关概念「树的遍历」指按照一定规则不重复地访问树中所有节点的过程。「访问」指针对节点的操作，如打印节点的值，更新节点的值等。本文讨论二叉树的遍历，...

ethernet 2019-08-21 17:07 评论0 收藏0
二叉树js的生成

摘要：二叉树的生成二叉树的概念二叉树概念及相关操作本文是顺序二叉树及其操作的实现，非顺序二叉树应该也差不多，这里没有实现基本二叉树的实现添加元素查找元素删除元素具体使用方法二叉树的js生成二叉树的概念二叉树概念及相关操作本文是顺序二叉树及其操作的js实现，非顺序二叉树应该也差不多，这里没有实现 //基本二叉树的实现 function BT(){ this.root=null; ...

anyway 2019-08-20 14:02 评论0 收藏0