一、二叉树的基本概念
从逻辑结构角度来看,前面说的链表、栈、队列都是线性结构;而今天要了解的“二叉树”属于树形结构。
1.1 多叉树的基本概念,以上图中“多叉树”为例说明
节点:多叉树中的每一个点都叫节点;其中最上面的那个节点叫“根节点”;
父节点:节点1是节点2/3/4/5/6的父节点,然后节点2/3/4/5/6是节点1的子节点;节点2/3/4/5/6又是互为兄弟节点,因为它们有父节点为同一个节点;
空树:一个没有任何节点的树叫空树;一棵树可以只有一个节点,也就是只有根节点;
子树:子节点及子节点的后台节点形成的一个节点集合叫子树;对于只有两个子节点的节点,其左边的子节点叫左子树,右边的叫右子树;
叶子节点(leaf):子树为0的节点;其他子树不为0的节点叫“非叶子节点”;
层数(level):根节点在第1层,根节点的子节点在第2层,以此类推(有些说法也从第0层开始结算);
节点的深度(depth):从根节点到当前节点的唯一路径上的节点总数;
节点的高度(height):从当前节点到最远叶子节点的路径上的节点总数;
树的深度:所有节点深度中的最大值;
树的高度:所以节点高度中的最大值;数的深度等于数的高度
有序树:树中任意节点的子节点之间有顺序关系;
无序树:树中任意节点的子节点之间没有顺序关系,也叫“自由树”;
森林:由n(n >= 0) 颗不相交的树组成的集合;
1.2 二叉树的特点
1.3 真二叉树/满二叉树/完全二叉树
面试题:如果一颗完全二叉树有768个节点,求叶子节点的个数?
分析:假设叶子节点个数为n0,度为1的节点个数为n1,度为2的节点个数为n2。
则总节点个数n = n0 + n1 + n2,而且n0 = n2 + 1 ;
则n = 2n0 + n1 -1
根据完全二叉树的定义我们知道,n1要么为0,要么为1:
当n1为1时, n = 2n0, n必然为偶数。叶子节点个数n0 = n / 2,非叶子节点个数 n1 + n2 = n / 2 ;
当n1为0,n = 2n0 - 1,n必然为奇数。叶子节点个数n0 = (n + 1) / 2, 非叶子节点个数 n1 + n2 = (n - 1) / 2
因此可以判断出来当这个完全二叉树有768个节点时,它的叶子节点个数为:384
二、二叉查找树
二叉查找树是一种特殊的二叉树,较小的值保存在左节点中,较大的值保存在右节点中。这一特性使得查找的效率很高,对于数值型和非数值型的数据,如单词和字符串,都是如此。
2.1 二叉查找树的插入逻辑
2.1.1 设根节点为当前节点
2.1.2 如果待插入节点保存的数据小于当前节点,则设新的当前节点为原节点的左节点;反之,执行第2.1.4步
2.1.3 如果当前节点的左节点为null, 就将新的节点插入这个位置,退出循环;反之,继续执行下一次循环
2.1.4 设新的当前节点为原节点的右节点
2.1.5 如果当前节点的右节点为null, 就将新的节点插入这个位置,退出循环;反之,继续执行下一次循环
//插入元素
function insertBST(element){
var node = new Node(element, null, null);
//根节点判断
if (root == null){
root = node;
}
else{ //非根节点
var current = root;
while(true){
if (element < current.element){ //往左节点方向放
if (current.left == null){
current.left = node;
break;
}
current = current.left;
}
else if (element > current.element){ //往右节点方向放
if (current.right == null){
current.right = node;
break;
}
current = current.right;
}
else { //相等,替换
current.element = element;
return;
}
}
}
size++;
}
2.2 二叉查找树的遍历,遍历有三种方式:中序、前序、后序
中序指以升序的方式遍历所有节点;前序是指先访问根节点,再以同样的方式访问左子树和右子树;后序指的是先访问叶子节点,再从左子树到右子树,最后到根节点。
先看个效果图
遍历走势分析图:
遍历代码:
//二叉树中序遍历:以升序方式访问二叉树中所有节点
function inOrder(){
return inOrderByNode(root);
}
function inOrderByNode(node){
if (node){
var str = "";
str += inOrderByNode(node.left);
str += node.element + ", ";
str += inOrderByNode(node.right);
return str;
}
return "";
}
//前序遍历:先访问根节点,再访问左子树和右子树
function preOrder(){
return preOrderByNode(root);
}
function preOrderByNode(node){
if (node){
var str = '';
str += node.element + ", "; //先访问根节点
str += preOrderByNode(node.left); //再访问左子树
str += preOrderByNode(node.right); //再访问右子树
return str;
}
return "";
}
//后序遍历:先访问叶子节点,再左子树,再右子树,再到根节点
function postOrder(){
return postOrderByNode(root);
}
function postOrderByNode(node){
if (node){
var str = "";
str += postOrderByNode(node.left);
str += postOrderByNode(node.right);
str += node.element + ", ";
return str;
}
return "";
}
2.3 查找二叉查找树的最大值、最小值、是否存在某个值
最大值:因为较大的值都是在右子树上,则最大值一定是在右子树的最后一个节点上;
最小值:较小的值都是在左子树上,则最小值一定在左子树的最后一个节点上;
是否存在某个值,则是遍历查找
//查找最小值:因为较小的值都在左边,所以最小值一定是左子树的最后一个节点
function getMin(){
var minNode = getMinNode(root);
if (minNode) {
return minNode.element;
}
return null;
}
//查找最小节点
function getMinNode(node){
var current = node;
while(current){
if (current.left == null){
return current;
}
current = current.left;
}
return null;
}
//查找最大值:因为较大的值都在右边,所以最大值一定是在右子树的最后一个节点
function getMax(){
var maxNode = getMaxNode(root);
if (maxNode){
return maxNode.element;
}
return null;
}
//查找最大节点
function getMaxNode(node){
var current = node;
while(current){
if (current.right == null){
return current;
}
current = current.right;
}
return null;
}
//查找指定值,是否存在这个元素
function isExist(element){
var current = root;
while(current){
if (element < current.element){ //左子树寻找
current = current.left;
}
else if (element > current.element){ //右子树寻找
current = current.right;
}
else{ //存在
return true;
}
}
return false;
}
2.4 删除二叉查找树中的指定元素
从二叉查找树上删除节点的操作最复杂,其复杂程度取决于删除哪个节点。如果删除没有子节点 的节点,那么非常简单。如果节点只有一个子节点,不管是左子节点还是右子节点,就变 得稍微有点复杂了。删除包含两个子节点的节点最复杂。
//删除元素
function remove(element){
root = removeNode(root, element);
}
function removeNode(node, element){
if (node == null) {
return null;
}
if (node.element == element){
size--;
//node没有左子树
if (node.left == null){
return node.right;
}
else if (node.right == null){ //node没有右子树
return node.left;
}
/**
* node有左子树和右子树,这个时候要找出最接近node节点值的节点
* 1、如果找出比node节点的element稍大的节点,则从node右节点的最小节点
* 2、如果找出比node节点的element稍小的节点,则从node左节点的最大节点
*/
//第一种方式,找出比node的element稍微大点的节点
var minNode = getMinNode(node.right);
node.element = minNode.element;
node.right = removeNode(node.right, minNode.element);
// //第二种方式, 找出比node的element稍微小点的节点
// var maxNode = getMaxNode(node.left);
// node.element = maxNode.element;
// node.left = removeNode(node.left, maxNode.element);
return node;
}
else if(element < node.element){ //往左子树方向继续找
node.left = removeNode(node.left, element);
return node;
}
else{
//往右子树方向继续找
node.right = removeNode(node.right, element);
return node;
}
}