二叉树
是什么
二叉树：树中的每个结点最多只能有两个结点，通常我们使用 Object 来模拟一个二叉树,二叉树的遍历有先、中、后序遍历三种
满二叉树：除最后一层无任何子结点外，每一层所有的节点都有两个子节点的二叉树，如果一个二叉树层数为 n,那么满二叉树的结点总数为 2^k - 1 个
完全二叉树：二叉树（除最后一层）的每一个结点必须全部填满，在最后一层所有结点连续集中在最左边
怎么做
class Node {
constructor(key){
this.key = key
this.left = null
this.right = null
}
}
class Tree{
constructor(){
this.root = null
}
// 增:添加节点1
insert(key){
const newNode = new Node(key)
if(!this.root){
this.root = newNode
}else{
// 递归添加节点2
this.insertNode(this.root,newNode)
}
}
// 递归添加节点2
insertNode(node,newNode){
// console.log(node.key,newNode.key)
if(newNode.key < node.key ){ // 小
if(!node.left){
node.left = newNode
}else{
this.insertNode(node.left,newNode)
}
}else{ // 大
if(!node.right){
node.right = newNode
}else{
this.insertNode(node.right,newNode)
}
}
}
// 先序遍历
preOrderTraversal(arr){
this.preOrderTraversalNode(this.root,arr)
}
// 先序遍历节点
preOrderTraversalNode(node,arr){
if(node !==null){
arr.push(node.key)
this.preOrderTraversalNode(node.left,arr)
this.preOrderTraversalNode(node.right,arr)
}
}
// 中序遍历
middlerOrderTraversal(arr){
this.middlerOrderTraversalNode(this.root,arr)
}
// 中序遍历节点
middlerOrderTraversalNode(node,arr){
if(node !==null){
this.preOrderTraversalNode(node.left,arr)
arr.push(node.key)
this.preOrderTraversalNode(node.right,arr)
}
}
// 后序遍历
epiOrderTraversal(arr){
this.epiOrderTraversalNode(this.root,arr)
}
// 中序遍历节点
epiOrderTraversalNode(node,arr){
if(node !==null){
this.epiOrderTraversalNode(node.left,arr)
this.epiOrderTraversalNode(node.right,arr)
arr.push(node.key)
}
}
// 最大值:递归
getMax(){
let current = this.root
while(current.right){
current = current.right
}
return current.key
}
// 最小值：递归
getMin(){
let current = this.root
while(current.left){
current = current.left
}
return current.key
}
// 搜索特定的值
search(key){
return this.searchNode(this.root,key)
}
searchNode(node,key){
if(node){
// 从left递归查找
if(node.key > key){
return this.searchNode(node.left,key)
}else if(node.key < key){
// 从right递归查找
return this.searchNode(node.right,key)
}else{
// 最终找到
return node
}
}else{
return undefined
}
}
// 删除节点
// 1. 没有子节点
// 2. 只有一边节点
// 3. 两边都有节点
delete(key){
// 对应节点
let current = this.root
// 对应节点父级
let parent = null
// 判断子节点左方向
let isLeftChild = true
// 遍历：获取对应节点
while(current && current.key !==key){
// 获取对应节点父级
parent = current
if(current.key < key){ // right大
current = current.right
// 子节点的方向
isLeftChild = false
}else{//left小
current = current.left
// 子节点的方向
isLeftChild = true
}
}
// 防御性
if(!current)return undefined;
// 获取子节点方向
const replacePosition = isLeftChild ? 'left' :'right'
// 检查子节点个数
const twoSonExit = current.left && current.right
if(twoSonExit){
// 3. 两个子节点都存在
//const preNode = this.getPreNode(current) // 前驱:获取最小的子节点来代替
const preNode = this.getEpiNode(current) // 后继：获取最大的子节点代替（使用)
parent[replacePosition] = preNode
preNode.left = current.left
preNode.right = current.right
}else if(current.left || current.right){
// 2.一个子节点
const isLeft = !!current.left
parent[replacePosition] = current[isLeft ? 'left' :'right']
}else{
// 1. 无子节点
parent[replacePosition] = null
}
}
// 前驱:获取最小的子节点来代替
getPreNode(node){
let preNode = node.left
let parent = node
while(preNode && preNode.right){
parent = preNode
preNode = node.right
}
if(parent === node){
parent.left = null
}else{
parent.right = null
}
return preNode
}
// 后继：获取最大的子节点代替（使用)
getEpiNode(node){
let preNode = node.right
let parent = node
while(preNode && preNode.left){
parent = preNode
preNode = node.left
}
if(parent === node){
parent.right = null
}else{
parent.left = null
}
return preNode
}
}
const t = new Tree()
t.insert(4)
t.insert(3)
t.insert(6)
t.insert(2)
t.insert(3.5)
t.insert(5)
// 前序遍历
// const arr = []
// t.preOrderTraversal(arr)
// console.log(arr) // [4, 3, 2, 3.5, 6, 5]
// 中序遍历
// const arr2 = []
// t.middlerOrderTraversal(arr2)
// console.log(arr2) // [3, 2, 3.5, 4, 6, 5]
// 后序遍历
// const arr3 = []
// t.epiOrderTraversal(arr3)
// console.log(arr3) // [2, 3.5, 3, 5, 6, 4]
// console.log(t.getMax())
// console.log(t.getMin())
// console.log(t.search(3))
// t.delete(2) // 无子节点
// t.delete(6) // 一个子节点
// t.delete(3) // 两个子节点
console.log(t)