完美二叉树（满二叉树）
除了最下一层的节点外，每层节点都有两个子节点的二叉树为满二叉树
完全二叉树
除二叉树最后一层外，其余各层节点都为2，且最后一层从左向右的叶节点连续存在，只缺右侧若干节点
完美二叉树与完全二叉树
常见的题目
- 一个二叉树第i层的最大节点数为：2^(i-1)，i>=1
- 深度为k的二叉树最大节点数总数为：2^k-1，k>=1
- 对任何非空二叉树，n1表示叶节点个数，n2是度为2的非叶节点个数，那么两者满足关系：n1 = n2 + 1
二叉搜索树(BST)
BST：Binary Search Tree
特性：
1.非空左子树的所有键值小于其根节点的键值
2.非空右子树的所有键值大于其根节点的键值
二叉搜索树的三种遍历
前序遍历：树根->左子树->右子树(ABDGHCEIF)
前序遍历
中序遍历：左子树->树根->右子树(GDHBAEICF)
中序遍历
后序遍历：左子树->右子树->树根(GHDBIEFCA)
后续遍历
二叉搜索树的常见操作
insert(key)：向树中插入一个新的键
search(key)：在树中查找某个键，返回布尔值
preOrderTraversal：先序遍历所有节点
midOrderTraversal()：中序遍历所有节点
postOrderTraversal()：后序遍历所有节点>min()：返回树中最小值/键
max()：返回树中最大值/键
remove(key)：从树中移除一个键
代码实现
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<meta http-equiv="X-UA-Compatible" content="ie=edge">
<title>Document</title>
</head>
<body>
<script>
//封装二叉搜索树
function BinarySerachTree() {
//内部类
function Node(key) {
this.key = key
this.left = null
this.right = null
}
//属性
this.root = null
//方法
//插入数据
BinarySerachTree.prototype.insert = function (key) {
//1.根据key创建节点
var newNode = new Node(key)
//2.判断根节点是否有值
if (this.root == null) {
this.root = newNode
} else {
this.insertNode(this.root, newNode)
}
//递归插入
BinarySerachTree.prototype.insertNode = function (node, NewNode) {
if (newNode.key < node.key) {
//向左查找
if (node.left == null) {
node.left = newNode
} else {
this.insertNode(node.left, newNode)
}
} else {
//向右查找
if (node.right == null) {
node.right = newNode
} else {
this.insertNode(node.right, newNode)
}
}
}
//先序遍历
BinarySerachTree.prototype.preOrderTraversal = function (handler) {
this.preOrderTraversalNode(this.root, handler)
}
BinarySerachTree.prototype.preOrderTraversalNode = function (node, handler) {
if (node !== null) {
//处理经过的节点
handler(node.key)
//处理经过的节点的左子节点
this.preOrderTraversalNode(node.left, handler)
//处理经过的节点的右子节点
this.preOrderTraversalNode(node.right, handler)
}
}
//中序遍历
BinarySerachTree.prototype.midOrderTraversal = function (handler) {
this.midOrderTraversalNode(this.root, handler)
}
BinarySerachTree.prototype.midOrderTraversalNode = function (node, handler) {
if (node !== null) {
//处理经过的节点的左子节点
this.midOrderTraversalNode(node.left, handler)
//处理经过的节点
handler(node.key)
//处理经过的节点的右子节点
this.midOrderTraversalNode(node.right.handler)
}
}
//后序遍历
BinarySerachTree.prototype.postOrderTraversal = function (handler) {
this.postOrderTraversalNode(this.root, handler)
}
BinarySerachTree.prototype.postOrderTraversalNode = function (node, handler) {
if (node !== null) {
//处理经过的节点的左子节点
this.postOrderTraversalNode(node.left, handler)
//处理经过的节点的右子节点
this.postOrderTraversalNode(node.right.handler)
//处理经过的节点
handler(node.key)
}
}
//寻找最大值
BinarySerachTree.prototype.max = function () {
//获取根节点
var node = this.root
var key = null
//依次向右查找，直到节点为null
while(node != null){
key = node.key
node = node.right
}
return key
}
//寻找最小值
BinarySerachTree.prototype.min = function () {
//获取根节点
var node = this.root
var key = null
//依次向左查找，直到节点为null
while(node != null){
key = node.key
node = node.left
}
return key
}
//寻找是否存在某节点
BinarySerachTree.prototype.search = function(key){
return this.searchNode(this.root,key)
}
BinarySerachTree.prototype.searchNode = function(node,key){
//如果传入的node值为null，就退出递归
if(node == null){
return false
}
//判断node节点的值和传入的key的大小
if(node.key > key){
//传入的key较小,向左查找
return this.searchNode(node.left,key)
}else if(node.key < key){
//传入的key较大,向左查找
return this.searchNode(node.right,key)
}else{
//key相同,找到了
return true
}
}
//删除节点
BinarySerachTree.prototype.remove = function(key){
//寻找要删除的节点
var current = this.root
var parent = null
var isLeftChild = true
while(current.key != key){
parent = current
if(ket < current.key){
//在左边
isLeftChild = true
current = current.left
}else{
isLeftChild = false
current = current.right
}
//没有找到
if(current == null) return false
}
//删除节点
//1.叶子节点
if(current.left == null && current.right == null){
if(current == this.root){
this.root = null
}else if(isLeftChild){
parent.left = null
}else{
parent.right = null
}
}
//根节点且有一个子节点
else if(current.right == null){
if(current == this.root){
this.root = current.left
}else if(isLeftChild){
parent.left = current.left
}else{
parent.right = current.left
}
}else if(current.left == null){
if(current == this.root){
this.root = current.right
}else if(isLeftChild){
parent.left = current.right
}else{
parent.right = current.right
}
}
//根节点且有两个子节点
else{
//获取后继节点
var successor = this.getSuccssor(current)
if(current == this.root){
//是根节点
this.root = successor
}else if(isLeftChild){
parent.left = successor
}else{
parent.right = successor
}
successor.left = current.left
}
}
//找后继方法
BinarySerachTree.prototype.getSuccssor = function(delNode){
var successor = delNode
var current = delNode.right
var successorParent = delNode
//循环查找
while(current != null){
successorParent = successor
successor = current
current = current.left
}
//后继节点是delNode的right节点
if(successor != delNode.right){
successorParent.left = successor.right
successor.right = delNode.right
}
return successor
}
}
}
</script>
</body>
</html>
END
网友评论