树和其他数据结构的对比
数组:
- 优点:数组的主要优点是根据下标值访问效率会很高.
- 缺点:数组在插入和删除数据时, 需要有大量的位移操作(插入到首位或者中间位置的时候), 效率很低.
链表:
- 优点:链表的插入和删除操作效率都很高.
- 缺点:查找效率很低, 需要从头开始依次访问链表中的每个数据项, 直到找到.
而且即使插入和删除操作效率很高, 但是如果要插入和删除中间位置的数据, 还是需要重头先找到对应的数据.
哈希表:
- 优点:哈希表的插入/查询/删除效率都是非常高的
- 缺点:空间利用率不高, 底层使用的是数组, 哈希表中的元素是无序的, 不能按照固定的顺序来遍历哈希表中的元素，不能快速的找出哈希表中的最大值或者最小值这些特殊的值.
树结构:
- 树结构也综合了上面的数据结构的优点(当然优点不足于盖过其他数据结构, 比如效率一般情况下没有哈希表高), 并且也弥补了上面数据结构的缺点。比如空间利用率高，查找效率高，删除和添加也比较方便，可以快速找到最大值和最小值等。
树的认识
术语
- 结点的度（Degree）：结点的子树个数.
- 树的度：树的所有结点中最大的度数.
- 叶结点（Leaf）：度为0的结点. (也称为叶子结点)
- 父结点（Parent）：有子树的结点是其子树的根结点的父结点
- 子结点（Child）：若A结点是B结点的父结点，则称B结点是A结点的子结点；子结点也称孩子结点。
- 兄弟结点（Sibling）：具有同一父结点的各结点彼此是兄弟结点。
- 路径和路径长度：从结点n1到nk的路径为一个结点序列n1 , n2,… , nk, ni是 ni+1的父结点。路径所包含边的个数为路径的长度。
- 结点的层次（Level）：规定根结点在1层，其它任一结点的层数是其父结点的层数加1。
- 树的深度（Depth）：树中所有结点中的最大层次是这棵树的深度。
二叉树
所有的树本质上都可以使用二叉树模拟出来
- 二叉树的定义
- 二叉树可以为空, 也就是没有结点.
- 若不为空，则它是由根结点和称为其左子树TL和右子树TR的两个不相交的二叉树组成。
- 二叉树的特性
- 一个二叉树第 i 层的最大结点数为：2^(i-1), i >= 1;
- 深度为k的二叉树有最大结点总数为： 2^k – 1, k >= 1;
- 对任何非空二叉树 T，若n0表示叶结点的个数、n2是度为2的非叶结点个数，那么两者满足关系n0 = n2 + 1。
特殊的二叉树
- 完美二叉树：在二叉树中, 除了最下一层的叶结点外, 每层节点都有2个子结点, 就构成了满二叉树.
- 完全二叉树：除二叉树最后一层外, 其他各层的节点数都达到最大个数。且最后一层从左向右的叶结点连续存在, 只缺右侧若干节点.
二叉树的存储
常见方式是数组和链表
- 数组
- 完全二叉树：从上往下，从左到右
- 非完全二叉树：转成完全二叉树才能按上面的方案存储，但是会造成很大的空间浪费
- 使用链表（二叉树最常见的方式）
- 每个节点封装成一个node，node中包含存储的数据，左节点的引用，右节点的引用
二叉搜索树
定义
- 二叉搜索树是一颗二叉树, 可以为空；如果不为空，满足以下性质：
- 非空左子树的所有键值小于其根结点的键值。
- 非空右子树的所有键值大于其根结点的键值。
- 左、右子树本身也都是二叉搜索树。
特性
- 二叉搜索树的特点就是相对较小的值总是保存在左结点上, 相对较大的值总是保存在右结点上.
二叉搜索树的封装
实现了插入、查找、先序遍历、中序遍历、后序遍历、返回最值、删除节点等操作。
class Node {
constructor(key) {
this.key = key;
this.left = null;
this.right = null;
}
}
class BinarySearchTree {
constructor() {
this.root = null;
}
//插入数据
insert(key) {
//根据传进来的key创建节点
let newNode = new Node(key);
//判断根节点是否为空
if (this.root == null) {
this.root = newNode;
} else {
this.insertNode(this.root, newNode);
}
}
insertNode(node, newNode) {
//判断被比较的节点和新节点的key大小
if (newNode.key > node.key) {
if (node.right == null) {
node.right = newNode;
} else {
this.insertNode(node.right, newNode);
}
} else {
if (node.left == null) {
node.left = newNode;
} else {
this.insertNode(node.left, newNode);
}
}
}
//先序遍历
preOrderTraversal() {
this.preOrderTraversalNode(this.root);
}
preOrderTraversalNode(node) {
if (node != null) {
console.log(node.key);
this.preOrderTraversalNode(node.left);
this.preOrderTraversalNode(node.right);
}
}
//中序遍历
midOrderTraversal() {
this.midOrderTraversalNode(this.root);
}
midOrderTraversalNode(node) {
if (node != null) {
this.midOrderTraversalNode(node.left);
console.log(node.key);
this.midOrderTraversalNode(node.right);
}
}
//后序遍历
postOrderTraversal() {
this.postOrderTraversalNode(this.root);
}
postOrderTraversalNode(node) {
if (node != null) {
this.postOrderTraversalNode(node.left);
this.postOrderTraversalNode(node.right);
console.log(node.key);
}
}
//查找key对应的节点
search(key) {
let node = this.root;
while (node != null) {
if (key > node.key) {
node = node.right;
} else if (key < node.key) {
node = node.left;
} else {
return true;
}
}
return false;
}
//删除数据
remove(key) {
//1.1定义变量保存信息
let parent = null;
let current = this.root;
let isLeftChild = true;
//1.2查找要删除的节点
while (current.key != key) {
parent = current;
if (key > current.key) {
current = current.right;
isLeftChild = false;
} else {
current = current.left;
isLeftChild = true;
}
if (current == null) {
return false;
}
}
//2.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;
}
}
//2.2删除只有一个子节点的节点
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 if ((current.right = null)) {
if (current == this.root) {
this.root = current.left;
} else if (isLeftChild) {
parent.left = current.left;
} else {
parent.right = current.left;
}
}
//2.3删除有两个子节点的节点
else {
let successor = this.getSuccessor(current);
if (current == root) {
this.root = successor;
} else if (isLeftChild) {
parent.left = successor;
} else {
parent.right = successor;
}
successor.left = current.left;
}
}
getSuccessor(delNode) {
//设置变量保存临时信息
let successor = delNode;
let successorParent = delNode;
let current = delNode.right;
//查找后继节点
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;
}
}
//测试
let bst = new BinarySearchTree();
bst.insert(11);
bst.insert(7);
bst.insert(15);
bst.insert(5);
bst.insert(3);
bst.insert(9);
bst.insert(8);
bst.insert(10);
bst.insert(13);
bst.insert(12);
bst.insert(14);
bst.insert(20);
bst.insert(18);
bst.insert(25);
bst.insert(6);
console.log(bst);
bst.midOrderTraversal();
// bst.postOrderTraversal();
// console.log(bst.search(11));
// console.log(bst.search(2));
bst.remove(18);
bst.midOrderTraversal();
复制代码删除操作的思路
- 查找节点
- 查找需要删除的节点，没找到返回false
- 找到的话分为三种情况：
- 该节点是叶子结点
- 该节点有一个子节点
- 该节点有两个子节点
- 删除节点
- 删除节点是叶子节点和只有一个子节点的情况比较简单，这里只分析删除有两个子节点的节点。
- 如果我们要删除的节点有两个子节点, 甚至子节点还有子节点, 这种情况下我们需要从下面的子节点中找到一个节点, 来替换当前的节点.
- 这个节点怎么找呢?
- 比current小一点点的节点, 一定是current左子树的最大值.
- 比current大一点点的节点, 一定是current右子树的最小值.
- 前驱&后继
在二叉搜索树中, 这两个特别的节点, 有两个特别的名字.
- 比current小一点点的节点, 称为current节点的前驱.
- 比current大一点点的节点, 称为current节点的后继.
也就是为了能够删除有两个子节点的current, 要么找到它的前驱, 要么找到它的后继.
参考coderwhy老师的数据结构与算法记录
复制代码© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![[桜井宁宁]COS和泉纱雾超可爱写真福利集-一一网](https://www.proyy.com/skycj/data/images/2020-12-13/4d3cf227a85d7e79f5d6b4efb6bde3e8.jpg)
![[桜井宁宁] 爆乳奶牛少女cos写真-一一网](https://www.proyy.com/skycj/data/images/2020-12-13/d40483e126fcf567894e89c65eaca655.jpg)
