js 判断一棵树 是否为平衡二叉树

简介: js 判断一棵树 是否为平衡二叉树
// 二叉树的生成
function NodeTree(value) {
    this.value = value;
    this.left = null;
    this.right = null;
}
let ta = new NodeTree('a');
let tb = new NodeTree('b');
let tc = new NodeTree('c');
let td = new NodeTree('d');
let te = new NodeTree('e');
let tf = new NodeTree('f');
let tg = new NodeTree('g');
ta.left = tb;
ta.right = tc;
tb.left = td;
tb.right = te;
tc.left = tf;
tc.right = tg;
如上面的数据结构,ta是一颗满二叉树,也是一颗平衡二叉树,
平衡二叉树的定义是啥呢?
 条件一:它必须是二叉查找树(二叉搜索树)。
 条件二:每个节点的左子树和右子树的高度差至多为1
// 获取一颗二叉树的深度
function getDeep(doubleTree) {
    if (doubleTree.value === null) return 0;
    let left = 0, right = 0;
    if (doubleTree.left) left = getDeep(doubleTree.left)
    if (doubleTree.right) right = getDeep(doubleTree.right);
    return Math.max(left, right) + 1;
}
/**
 * 判断一棵树是否为平衡二叉树
 * 1.条件, 二叉树里面的左右子树相差不能超过1
 * 2.
 */
function balanceTree(doubleTree){
    // 如果传入的数据,为空,则平衡
  if (!doubleTree|| doubleTree === '') return true;
  let leftNum = 0, rightNum = 0;
  if (doubleTree.left) {
      leftNum =  getDeep(doubleTree.left);
  }
  if (doubleTree.right){
      rightNum =  getDeep(doubleTree.right);
  }
  if (Math.abs(leftNum - rightNum) <= 1){
      return balanceTree(doubleTree.left) && balanceTree(doubleTree.right)
  }else {
      // 大于1,改二叉树不平衡
      return false;
  }
}
console.log(balanceTree(ta)) // 结果是true
那我们来一颗非平衡的二叉树,如下:
let ba = new Node('ba');
let bb = new Node('bb');
let bc = new Node('bc');
let bd = new Node('bd');
let be = new Node('be');
let bf = new Node('bf');
ba.left = bb;
ba.right = bc;
bb.left = bd;
bd.right = be;
be.left = bf;
console.log(balanceTree(ba)) // 结果是false
相关文章
|
6月前
|
算法 JavaScript
JS 【详解】树的遍历(含深度优先遍历和广度优先遍历的算法实现)
JS 【详解】树的遍历(含深度优先遍历和广度优先遍历的算法实现)
86 0
JS 【详解】树的遍历(含深度优先遍历和广度优先遍历的算法实现)
|
7月前
|
JavaScript 前端开发 算法
虚拟DOM是React的关键技术,它是个轻量的JS对象树,模拟实际DOM结构。
【6月更文挑战第27天】虚拟DOM是React的关键技术,它是个轻量的JS对象树,模拟实际DOM结构。当状态改变,React不直接修改DOM,而是先构建新的虚拟DOM树。通过 diff 算法比较新旧树,找到最小变更,仅更新必要部分,提高性能,避免频繁DOM操作。虚拟DOM还支持跨平台应用,如React Native。它优化了更新流程,简化开发,并提升了用户体验。
47 1
|
6月前
|
JavaScript
js 解析和操作树 —— 获取树的深度、提取并统计树的所有的节点和叶子节点、添加节点、修改节点、删除节点
js 解析和操作树 —— 获取树的深度、提取并统计树的所有的节点和叶子节点、添加节点、修改节点、删除节点
157 0
|
8月前
|
前端开发 JavaScript 算法
JavaScript 中实现常见数据结构:栈、队列与树
JavaScript 中实现常见数据结构:栈、队列与树
|
JavaScript
使用JS 实现二叉查找树(Binary Search Tree)
使用JS 实现二叉查找树(Binary Search Tree)
78 0
|
8月前
|
JavaScript
理解DOM树的加载过程(js的问题)
理解DOM树的加载过程(js的问题)
34 0
|
8月前
|
JSON JavaScript 前端开发
js(递归函数)实现树型菜单
js(递归函数)实现树型菜单
59 0
antd+js 目录树实现
antd+js 目录树实现
112 0
|
JavaScript 前端开发 程序员
《剑指 Offer(第 2 版)》树部分JavaScript题解
《剑指 Offer(第 2 版)》树部分JavaScript题解
《剑指 Offer(第 2 版)》树部分JavaScript题解
|
自然语言处理 JavaScript 前端开发
浏览器原理 21 # DOM树:JavaScript是如何影响DOM树构建的?
浏览器原理 21 # DOM树:JavaScript是如何影响DOM树构建的?
161 0
浏览器原理 21 # DOM树:JavaScript是如何影响DOM树构建的?