avatar

算法- js 二叉树,二叉查找树的基本实现及递归与循环的版本

二叉树

二叉树是一种属性结构,它的特点是每个节点最多只有两个分支节点,一颗二叉树通常由根节点,分支节点,叶节点组成,而每个分支节点也常常被称作为一颗子树。

image

  • 根节点:二叉树最顶层的节点
  • 分支节点:除了根节点以外且拥有叶子节点
  • 叶节点:除了自身没有其他节点
  • 中节点:当前节点的父节点(中序遍历)
    • 根的层次为0(一般来说),根的直接左右孩子层次为1,以此类推逐渐递增
      1. 二叉树节点的度数指该节点所含子树的个数
      1. 二叉树的深度是指所有节点中最深节点(叶节点)所在层数

常用术语: 在二叉树中,我们常常用父节点和子节点来描述,你如图中的2为6和3的父节点,反之6和3是2的子节点

二叉树的三个性质

  1. 在二叉树的第 i 层上,之多有 2 ^ (i - 1) 个节点
  2. i=1时,只有一个根节点,2^(i-1) = 2^0 = 1
    深度为k的二叉树至多有2^k-1个节点.
  3. i=2时,2^k-1 = 2^2 - 1 = 3个节点
    对任何一棵二叉树T,如果总结点数为n0,度为2(子树数目为2)的节点数为n2,则n0=n2+1

树和二叉树的三个主要区别

  1. 树的节点个数至少为1,而二叉树的节点个数可以为0
  2. 树中节点的最大度数(节点数量)没有限制,而二叉树的节点最大度为 2
  3. 树的节点没有左右之分

二叉树分为完全二叉树(complete binary tree)和 满二叉树

  • 二叉查找树 或 二叉搜索树
  • 满二叉树:一颗深度为 k 且有 2 ^ k - 1个节点二叉树称为满二叉树
  • 完全二叉树:最后一层左边是满的,右边可能满也可能不满,然后其余层都是满的二叉树称为完全二叉树(满二叉树也是一种完全二叉树)

image

二叉树的数组展示

用一个数组来展示二叉树的结构,将一组数组从根节点开始从上到下,从左到右一次填入一颗完全二叉树中

image

通过上图可以分析得到数组表示的完全二叉树有以下几个性质

  • left = index * 2 + 1,例如:根节点的下标为 0,则左节点的值为下标:arrary[0 * 2 + 1] = 1
  • right = idnex * 2 + 2,例如:根节点的下标为 0,则有节点的值为下标:array[index * 2 + 2]
  • 序数 >= floor(N / 2) 都是叶节点,例如:floor(9 / 2) = 4

二叉搜索树

  • 若左子树不为空,则左子树上所有的节点值均小于它的根节点的值;
  • 若有子树不为空,则右子树上所有节点的值均大于它的根节点的值
  • 左右子树也分别为二叉排序树
  • 没有键相等的节点

二叉搜索树

根据上图首先定义相关方法

class BinaryTree {

}

const data = [6, 2, 3, 4, 9, 8, 7, 12, 1, 22];
const tree = new BinaryTree({data});

添加节点

根据上面的特性添加节点

class BinaryTree {
// 定义基础节点
static Node = key => {
return {
key,
left: null,
right: null
}
}

constructor({data = []} = {}) {
this.root = null;
if (data.length) {
data.forEach(key => {
this.insertNode(key);
})
}
}

// 插入节点, 首次判断是否为根节点
insertNode(key) {
const node = BinaryTree.Node(key);
if (this.root === null) {
this.root = node;
} else {
this.insertNodeInTree(this.root, node)
}
}

// 往树中插入节点
// 并约定右子树的值永远大于左子树
insertNodeInTree(node, newNode) {
// 往当前节点的右子树插入
if (newNode.key > node.key) {
// 当前没有右子树
if (node.right === null) {
node.right = newNode
} else {
this.insertNodeInTree(node.right, newNode);
}
} else { // 左边做相同的操作
// 当前没有左子树
if (node.left === null) {
node.left = newNode
} else {
this.insertNodeInTree(node.left, newNode);
}
}
}
}

二叉树的遍历算法

  • 图中中序遍历结果:1 2 3 4 6 7 8 9 12 22
  • 图中前序遍历结果:6 2 1 3 4 9 8 7 12 22
  • 图中后序遍历结果:1 4 3 2 7 8 22 12 9 6

中序遍历(递归和循环)

先处理左节点(左子树),在处理中节点(父节点),最后处理右节点

class BinaryTree {
// 中序遍历
// 先处理左节点(左子树),在处理中节点(当前节点的父节点),最后处理有节点(右子树),递归遍历所有节点
static traverseNodesLDR(node, callback) {
if (node !== null) {
BinaryTree.traverseNodesLDR(node.left, callback);
callback?.(node);
BinaryTree.traverseNodesLDR(node.right, callback)
}
}

// 中序遍历 循环版
static traverseNodesLDRforWhile(node, callback) {
const stack = [];
let currentNode = node;

while (stack.length || currentNode) {
// 判断当前 node,存在就向 stack 中 push 当前的左子节点
if (currentNode) {
stack.push(currentNode);
currentNode = currentNode.left;
} else {
currentNode = stack.pop();
callback?.(currentNode)
currentNode = currentNode.right;
}
}
}


// 中序遍历,左 => 中 => 右
LDR(callback) {
// BinaryTree.traverseNodesLDR(this.root, callback)
BinaryTree.traverseNodesLDRforWhile(this.root, callback)
}
}


// 中序遍历
tree.LDR(function (node) {
console.log(node);
});

前序遍历(先序遍历)

class BinaryTree {
// 前序遍历
// 先处理 中节点(父节点),在处理左节点(左子节点),最后处理右节点(右子节点)
static traverseNodesDLR(node, callback) {
if (node !== null) {
callback?.(node);
BinaryTree.traverseNodesDLR(node.left, callback);
BinaryTree.traverseNodesDLR(node.right, callback);
}
}

// 前序遍历 循环
static traverseNodesDLRforWhile(node, callback) {
let currentNode = node;
const stack = [currentNode];

while (stack.length) {
currentNode = stack.pop();
callback?.(currentNode);
// 先 push right,pop 取得时候 left 即可在前
if (currentNode.right) stack.push(currentNode.right);
if (currentNode.left) stack.push(currentNode.left);
}
}

// 前(先)序遍历 中 => 左 => 右
DLR(callback) {
// BinaryTree.traverseNodesDLR(this.root, callback)
BinaryTree.traverseNodesDLRforWhile(this.root, callback)
}

}
// 先序遍历
tree.DLR(function (node) {
console.log(node);
});

后序遍历

左 => 右 => 中

class BinaryTree {
// 后序列遍历
// 先处理 左节点(右节点),在处理右节点(左节点)最后处理中节点
static traverseNodesLRD(node, callback) {
if (node !== null) {
BinaryTree.traverseNodesLRD(node.left, callback);
BinaryTree.traverseNodesLRD(node.right, callback);
callback?.(node);
}
}

// 后序遍历 左,右,中
static traverseNodesLRDForWhile(node, callback) {
// 标记叶节点,当遇到叶节点将返回他的父节点,标记下次循环时跳过当前叶节点
let currentNode = node;
const stack = [currentNode];
let fNode = null;

while (stack.length) {
fNode = stack[stack.length - 1];
if (fNode.left && currentNode !== fNode.left && currentNode !== fNode.right) {
stack.push(fNode.left);
} else if (fNode.right && currentNode !== fNode.right) {
stack.push(fNode.right)
} else {
callback?.(stack.pop());
currentNode = fNode;
}
}
}


// 后续遍历 左 => 右 => 中
LRD(callback) {
// BinaryTree.traverseNodesLRD(this.root, callback);
BinaryTree.traverseNodesLRDForWhile(this.root, callback);
}
}


// 后序遍历
tree.LRD(function (node) {
console.log(node);
});

查找最大值

因为是搜索树,所以约定了右树是大的一边,所以找到右树中的叶节点即可(最小值同理)

class BinaryTree {
getMaxValue(callback) {
// this.traverseRight(this.root, callback)
this.traverseRightForWhile(this.root, callback)
}

traverseRight(node, callback) {
if (node !== null) {
// 如果有右节点则继续递归,没有那当前就是最大值
if (node.right !== null) {
this.traverseRight(node.right, callback);
} else callback?.(node)
} else {
callback?.('xxxx')
}
}

// 遍历右子树循环版
traverseRightForWhile(node, callback) {
let currentNode = node;

while (currentNode) {
if (currentNode.right) currentNode = currentNode.right;
else {
callback?.(currentNode);
currentNode = null;
}
}
}
}


tree.getMaxValue(function (node) {
console.log(node);
})

查找最小值

class BinaryTree {
// 获取最小值
getMinValue(callback) {
return this.traverseLeft(this.root, callback)
}

traverseLeft(node, callback) {
!callback && console.log(node, 'node');
if (node !== null) {
if (node.left !== null) {
if (callback) this.traverseLeft(node.left, callback);
else return this.traverseLeft(node.left, callback);
}
else {
if (callback) callback?.(node)
else return node
}
} else callback?.('xxxx')
}
}

tree.getMinValue(function (node) {
console.log(node);
})

查找指定的值

当传入的 key 大于根节点则只需在右子树中寻找,反之同理

class BinaryTree {
// 查找指定 key
findNode(targetKey) {
// return this.traverseNode(this.root, targetKey);
return this.traverseNodeForWhile(this.root, targetKey);
}

// 遍历树,如果指定的 key 小于根节点则继续遍历左节点反之亦然
traverseNode(node, targetKey) {
if (node !== null) {
// 目标存在于 右子树
if (targetKey > node.key) {
return this.traverseNode(node.right, targetKey);
} else if (targetKey < node.key) {
return this.traverseNode(node.left, targetKey);
} else {
return node;
}
}
}

// 查找指定的值 循环版
traverseNodeForWhile(node, targetKey) {
let currentNode = node;
let resultNode = null;

while (currentNode) {
if (targetKey > currentNode.key) currentNode = currentNode.right;
else if (targetKey < currentNode.key) currentNode = currentNode.left;
else {
resultNode = currentNode;
currentNode = null;
}
}

return resultNode;
}
}


// 查找指定的值
const target = tree.findNode(22);

删除节点

  • 删除叶节点:把当前节点设为 null
  • 删除仅包含 左子节点 的中节点:把当前节点赋值为左子节点即可(单右节点同理)
  • 删除包含左右节点的值:为了让其继续维持约定,所以被替换的值最合适的为当前节点的右节点中最小的值,赋值的同时并删除右边最小的值
class BinaryTree {
// 删除节点
removeNode(key) {
this.removeNodeByKey(this.root, key)
}

removeNodeByKey(node, key) {
if (node === null) return node;
// 找到指定节点
if (key > node.key) {
node.right = this.removeNodeByKey(node.right, key);
return node;
} else if (key < node.key) {
node.left = this.removeNodeByKey(node.left, key);
return node;
}
// 叶节点处理
if (node.left === null && node.right === null) {
return node = null
}
// 删除只有右子树的节点
// 只要把右子树赋值上去即可
if (node.left === null) {
return node = node.right;
}

// 删除只有左子树的节点
// 操作同上
if (node.right === null) {
return node = node.left;
}

// 删除包含左右子节点的节点
// 为了让继续维持约定,所以被替换的值最合适的为当前节点的右节点中最小的值,赋值的同时并删除右边最小的值
const minValue = this.traverseLeft(node.right)
node.key = minValue.key;
node.right = this.removeNodeByKey(node.right, minValue.key)
return node
}

}

console.log(tree.removeNode(9));

源码

class BinaryTree {
static Node = key => {
return {
key,
left: null,
right: null
}
}

// 中序遍历
// 先处理左节点(左子树),在处理中节点(当前节点的父节点),最后处理有节点(右子树),递归遍历所有节点
static traverseNodesLDR(node, callback) {
if (node !== null) {
BinaryTree.traverseNodesLDR(node.left, callback);
callback?.(node);
BinaryTree.traverseNodesLDR(node.right, callback)
}
}

// 中序遍历 循环版
// 左 => 中 => 右
// 6
// 2 9
// 1 3 8 12
// 4 7 22
//
static traverseNodesLDRforWhile(node, callback) {
const stack = [];
let currentNode = node;

while (stack.length || currentNode) {
// 判断当前 node,存在就向 stack 中 push 当前的左子节点
if (currentNode) {
stack.push(currentNode);
currentNode = currentNode.left;
} else {
currentNode = stack.pop();
callback?.(currentNode)
currentNode = currentNode.right;
}
}
}

// 前序遍历
// 先处理 中节点(父节点),在处理左节点(左子节点),最后处理右节点(右子节点)
static traverseNodesDLR(node, callback) {
if (node !== null) {
callback?.(node);
BinaryTree.traverseNodesDLR(node.left, callback);
BinaryTree.traverseNodesDLR(node.right, callback);
}
}

// 前序遍历 循环
// 中 左 右
// 6
// 2 9
// 1 3 8 12
// 4 7 22
static traverseNodesDLRforWhile(node, callback) {
let currentNode = node;
const stack = [currentNode];

while (stack.length) {
currentNode = stack.pop();
callback?.(currentNode);
// 先 push right,pop 取得时候 left 即可在前
if (currentNode.right) stack.push(currentNode.right);
if (currentNode.left) stack.push(currentNode.left);
}
}

// 后序列遍历
// 先处理 左节点(右节点),在处理右节点(左节点)最后处理中节点
static traverseNodesLRD(node, callback) {
if (node !== null) {
BinaryTree.traverseNodesLRD(node.left, callback);
BinaryTree.traverseNodesLRD(node.right, callback);
callback?.(node);
}
}

// 后序遍历 左,右,中
// 6
// 2 9
// 1 3 8 12
// 4 7 22
static traverseNodesLRDForWhile(node, callback) {
// 标记叶节点,当遇到叶节点将返回他的父节点,标记下次循环时跳过当前叶节点
let currentNode = node;
const stack = [currentNode];
let fNode = null;

while (stack.length) {
fNode = stack[stack.length - 1];
if (fNode.left && currentNode !== fNode.left && currentNode !== fNode.right) {
stack.push(fNode.left);
} else if (fNode.right && currentNode !== fNode.right) {
stack.push(fNode.right)
} else {
callback?.(stack.pop());
currentNode = fNode;
}
}
}

constructor({data = []} = {}) {
this.root = null;
if (data.length) {
data.forEach(key => {
this.insertNode(key);
})
}
}

// 插入节点, 首次判断是否为根节点
insertNode(key) {
const node = BinaryTree.Node(key);
if (this.root === null) {
this.root = node;
} else {
this.insertNodeInTree(this.root, node)
}
}

// 往树中插入节点
// 并预定右子树的值永远大于左子树
insertNodeInTree(node, newNode) {
// 往当前节点的右子树插入
if (newNode.key > node.key) {
// 当前没有右子树
if (node.right === null) {
node.right = newNode
} else {
this.insertNodeInTree(node.right, newNode);
}
} else { // 左边做相同的操作
// 当前没有右子树
if (node.left === null) {
node.left = newNode
} else {
this.insertNodeInTree(node.left, newNode);
}
}
}

// 中序遍历,左 => 中 => 右
LDR(callback) {
// BinaryTree.traverseNodesLDR(this.root, callback)
BinaryTree.traverseNodesLDRforWhile(this.root, callback)
}

// 前(先)序遍历 中 => 左 => 右
DLR(callback) {
// BinaryTree.traverseNodesDLR(this.root, callback)
BinaryTree.traverseNodesDLRforWhile(this.root, callback)
}

// 后续遍历 左 => 右 => 中
LRD(callback) {
// BinaryTree.traverseNodesLRD(this.root, callback);
BinaryTree.traverseNodesLRDForWhile(this.root, callback);
}

// 获取树中最大的节点,有限遍历右节点
getMaxValue(callback) {
// this.traverseRight(this.root, callback)
this.traverseRightForWhile(this.root, callback)
}

// 获取最小值
getMinValue(callback) {
return this.traverseLeft(this.root, callback)
}

// 遍历右子树
traverseRight(node, callback) {
if (node !== null) {
// 如果有右节点则继续递归,没有那当前就是最大值
if (node.right !== null) {
this.traverseRight(node.right, callback);
} else callback?.(node)
} else {
callback?.('xxxx')
}
}

// 遍历右子树循环版
traverseRightForWhile(node, callback) {
let currentNode = node;

while (currentNode) {
if (currentNode.right) currentNode = currentNode.right;
else {
callback?.(currentNode);
currentNode = null;
}
}
}

// 遍历左子树
traverseLeft(node, callback) {
!callback && console.log(node, 'node');
if (node !== null) {
if (node.left !== null) {
if (callback) this.traverseLeft(node.left, callback);
else return this.traverseLeft(node.left, callback);
}
else {
if (callback) callback?.(node)
else return node
}
} else callback?.('xxxx')
}

// 查找指定 key
findNode(targetKey) {
// return this.traverseNode(this.root, targetKey);
return this.traverseNodeForWhile(this.root, targetKey);
}

// 遍历树,如果指定的 key 小于根节点则继续遍历左节点反之亦然
traverseNode(node, targetKey) {
if (node !== null) {
// 目标存在于 右子树
if (targetKey > node.key) {
return this.traverseNode(node.right, targetKey);
} else if (targetKey < node.key) {
return this.traverseNode(node.left, targetKey);
} else {
return node;
}
}
}

// 查找指定的值 循环版
traverseNodeForWhile(node, targetKey) {
let currentNode = node;
let resultNode = null;

while (currentNode) {
if (targetKey > currentNode.key) currentNode = currentNode.right;
else if (targetKey < currentNode.key) currentNode = currentNode.left;
else {
resultNode = currentNode;
currentNode = null;
}
}

return resultNode;
}

// 删除节点
removeNode(key) {
this.removeNodeByKey(this.root, key)
}

/**
* 1. 删除的节点为 叶节点:直接指向 null
* 2. 删除的节点仅包含一个子节点:
*/
removeNodeByKey(node, key) {
if (node === null) return node;
// 找到指定节点
if (key > node.key) {
node.right = this.removeNodeByKey(node.right, key);
return node;
} else if (key < node.key) {
node.left = this.removeNodeByKey(node.left, key);
return node;
}
// 叶节点处理
if (node.left === null && node.right === null) {
return node = null
}
// 删除只有右子树的节点
// 只要把右子树赋值上去即可
if (node.left === null) {
return node = node.right;
}

// 删除只有左子树的节点
// 操作同上
if (node.right === null) {
return node = node.left;
}

// 删除包含左右子节点的节点
// 为了让继续维持约定,所以被替换的值最合适的为当前节点的右节点中最小的值,赋值的同时并删除右边最小的值
const minValue = this.traverseLeft(node.right)
node.key = minValue.key;
node.right = this.removeNodeByKey(node.right, minValue.key)
return node
}
}

// 6
// 2 9
// 1 3 8 12
// 4 7 11 22
// 21
//
const data = [6, 2, 3, 4, 9, 8, 7, 12, 1, 22, 21, 11];
const tree = new BinaryTree({data});
console.log(tree);

// 中序遍历
tree.LDR(function (node) {
// console.log(node);
});

// 先序遍历
tree.DLR(function (node) {
// console.log(node);
});

// 后序遍历
tree.LRD(function (node) {
// console.log(node);
});

// 查找最大值
tree.getMaxValue(function (node) {
// console.log(node);
})

// 查找 最小值
tree.getMinValue(function (node) {
// console.log(node);
})

// 查找指定的值
const target = tree.findNode(22);

// 删除指定值
console.log(tree.removeNode(9));
文章作者: kshao
文章链接: https://ksh7.com/2020/05/20/ms-binaryTree/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 kshao-blog
打赏
  • 微信
    微信
  • 支付寶
    支付寶

评论