前言
整理的关于二叉树的概念、类型和常见算法的内容非常详细,涵盖了二叉树的基本知识和常见操作。下面是文章的内容概要:
背景
- 介绍了二叉树在程序中的广泛应用,如React中的协调过程。
- 简要介绍了React中的协调过程和相关的概念。
- 补充了对二叉树的认识和学习的重要性。
二叉树概念
- 定义了二叉树作为一种数据结构,包括根节点、左子树和右子树。
- 描述了二叉树的特性,包括唯一根节点、父节点和节点间不能形成闭环的限制。
二叉树类型
- 介绍了三种常见的二叉树类型:完全二叉树、满二叉树和平衡二叉树。
- 对每种类型进行了图示和解释。
二叉树的遍历
- 介绍了三种常见的二叉树遍历方式:前序遍历、中序遍历和后序遍历。
- 对每种遍历方式进行了图示和解释。
- 提供了递归和非递归两种实现方式的代码示例。
二叉树常见算法
- 介绍了二叉搜索树的概念和操作,包括创建和搜索节点的代码示例。
- 介绍了镜像二叉树的概念和操作,包括递归和非递归两种实现方式的代码示例。
背景
二叉树作为程序的一种数据结构,应用广泛,比如React中的reconcile过程,Fiber树的调和过程。确实,在React中,Fiber树是通过child和sibling连接子节点和兄弟节点的方式来表示的,这与普通的二叉树有所不同。
在React中,reconcile过程是将虚拟DOM转化为实际DOM的过程。通过比较新旧两棵树的差异,React可以高效地更新实际DOM,而不是每次都完全重新渲染整个DOM树。这个过程中会涉及到对Fiber树的遍历和调整,确保更新只发生在需要更新的部分。
Fiber树作为一种数据结构,可以帮助React跟踪组件的状态和变化,以及进行调度和渲染。它使用链表的形式来组织组件树,使得遍历和更新变得更加高效。Fiber树的调和过程涉及到了遍历Fiber树的节点,执行副作用和收集需要更新的节点等操作,以实现高效的更新和渲染。
下面是我找的图:(很详细)
reconcile 的过程是协调fiber tree的过程,字面的意思是说让fiber tree变得更加协调,fiber tree的本质其实类似于一棵二叉树,所以整个的协调过程就是二叉树的调整过程。不过和通常的二叉树不一样的地方在于,fiber tree 是通过child 和 sibling 连接孩子节点和兄弟节点的。
在整个协调的过程,主要干了三件事情,第一件事情是在fiber tree中找到fiber node , 第二件事情是在标记有副作用的fiber node , 最后收集带有副作用的node。
无论是对于reconcile【协调】,还是面试题,有时看到二叉树这种数据结构时,很头疼难理解,但正是react reconcile 过程
使我对二叉树这种数据结构有了新的认识,所以我重新整理了二叉树的知识点,重新进行了学习。
这篇文章整理了二叉树的概念、类型与常见算法,希望对你有帮助。
二叉树概念
二叉树是n个有限元素的集合,该集合或者为空、或由一个称为根(root)的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成。
二叉树特性:
- 仅有唯一一个根节点,没有节点则为空树
- 除根节点外,每个节点都有并仅有唯一一个父节点
- 节点间不能形成闭环
图:
二叉树特点:
- 节点的深度 :从根节点到该节点所经历的边的个数。
- 节点的高度 :节点到叶节点的最长路径。
二叉树类型
二叉树类型:
- 完全二叉树
- 满二叉树
- 平衡二叉树
完全二叉树
一棵二叉树,假设其深度为d(d>1)。除了第d层外,其它各层的节点数目均已达最大值,且第d层所有节点从左向右连续地紧密排列,第d层节点的可以小于2,并且最下层的叶节点集中在靠左的位置上。
满二叉树
所有叶节点都在最底层的完全二叉树。
一棵满二叉树必定是一棵完全二叉树,而完全二叉树不一定是满二叉树。
平衡二叉树
任何节点的两棵子树的高度差不大于1的二叉树。
对于平衡二叉树要特别注意的是,不要求非叶节点都有两个子结点,仅要求两个子树的高度差的绝对值不超过1,或者为空树。
二叉树的遍历
二叉树的遍历:
- 前序遍历
- 中序遍历
- 后序遍历
前序遍历
对于二叉树中的任意一个节点,先打印该节点,然后是它的左子树,最后右子树。
根结点 -> 左子树 -> 右子树
输入: [1,null,2,3]
1
\
2
/
3
输出: [1,3,2]
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {number[]}
*/
let preorderTraversal = (root) => {
var res = [];
dfs(root);
function dfs(root){
if(!root) return;
res.push(root.val);
dfs(root.left);
dfs(root.right);
}
return res;
}
// 非递归
var preorderTraversal = function(root) {
let res = []
if(!root) return res;
const stack = [root];
let cur = null;
while(stack.length) {
cur = stack.pop();
res.push(cur.val);
cur.right && stack.push(cur.right);
cur.left && stack.push(cur.left);
}
return res;
};
中序遍历
对于二叉树中的任意一个节点,先打印它的左子树,然后是该节点,最后右子树。
左子树 -> 根结点 -> 右子树
输入: [1,null,2,3]
1
\
2
/
3
输出: [1,3,2]
//递归
function inOrder(root) {
const res = []
const rec = (n) => {
if(!n) return
rec(n.left)
res.push(n.val)
rec(n.right)
}
rec(root)
return res
}
//非递归
function inorderTraversal(root) {
const res = []
const stack = []
while(stack.length || root) {
if(root) {
stack.push(root)
root = root.left
} else {
const node = stack.pop()
res.push(node.val)
root = node.right
}
}
return res
}
后序遍历
对于二叉树中的任意一个节点,先打印它的左子树,然后是右子树,最后该节点。
左子树 -> 右子树 -> 根结点
输入: [1,null,2,3]
1
\
2
/
3
输出: [3,2,1]
//递归
function postorderTraversal(root) {
if(!root) return [];
let arr =[];
function preNode(root,arr){
if(!root) return [];
preNode(root.left,arr);
preNode(root.right,arr);
arr.push(root.val);
}
preNode(root,arr);
return arr
}
//非递归
function postorderTraversal(root) {
let res = [];
if(!root){
return res;
}
let stack = [root];
let cur;
while(stack.length){
cur = stack.pop(); //取出中间元素
res.unshift(cur.val);
cur.left && stack.push(cur.left);
cur.right && stack.push(cur.right);
}
return res;
}
二叉树常见算法
二叉搜索树
又称二叉查找树、二叉排序树,其根节点的值大于其左子树中任意一个结点的值,小于其右子树中任意一结点的值,这一规则适用于二叉查找树中的每一个节点。
创建二叉树节点
function insertTree(node, val) {
if(!node){
node = new TreeNode();
node.val = val;
node.left = null;
node.right = null;
return true;
}
if(node.val == val)
return false;
if(node.val > val)
return insertTree(node.left, val);
else
return insertTree(node.right, val)
}
搜索二叉树节点
function SearchTree(node, val) {
if(!node)
return null;
if(node.val == val)
return node;
if(node.val > val)
return SearchTree(node.left, val);
else
return SearchTree(node.right, val);
}
镜像二叉树
映射二叉树的对称节点。
例如输入:
4
/ \
2 7
/ \ / \
1 3 6 9
镜像输出:
4
/ \
7 2
/ \ / \
9 6 3 1
观察发现,镜像可以理解为左右子树互换,同时 其各子树的左右子树再递归互换。
//递归:自下向上换
function Mirror(root) {
if(!root)
return null;
var left = Mirror(root.left);
var right = Mirror(root.right);
root.left = right;
root.right = left;
/*
另一种写法:
Mirror(root.left);
Mirror(root.right);
[root.left, root.right] = [root.right, root.left];
*/
return root;
}
//非递归:从上向下换
function Mirror(root) {
if(!root) //不加这个root为null时会报错
return root;
var a = []; //队列
a.push(root);
while(a.length != 0){
var l = a.length;
for(var i = 0; i < l; i++){
var node = a.shift(); //压出第一个元素
if(node.left)
a.push(node.left);
if(node.right)
a.push(node.right);
//左右指针交换
[node.left, node.right] = [node.right, node.left];
}
}
return root;
}
判断是否为镜像
function isMirror(node1, node2) {
if(node1 == null && node2 == null)
return true;
if(node1 == null || node2 == null)
return false;
if(node1.val != node2.val)
return false;
return isMirror(node1.left, node2.right) && isMirror(node1.right, node2.left);
}
isMirror(root.left, root.right);
重建二叉树
输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树
思路
- 确定根结点,前序遍历的第一个结点为根节点
- 确定两种遍历方式的左右子树顺序
- 在左子树中递归步骤1和2
- 在右子树中递归步骤1和2
- 打印当前根
function reConstructBinaryTree(pre, vin) {
// write code herepre
if(pre.length == 0 || vin.length == 0)
return null;
var index = vin.indexOf(pre[0]); //根结点在中序遍历中的位置
var vinLeft = vin.slice(0, index); //中序左子树
var vinRight = vin.slice(index+1); //中序右子树
var preLeft = pre.slice(1, index+1); //前序右子树
var preRight = pre.slice(index+1); //前序左子树
var root = new TreeNode(pre[0]);
root.left = reConstructBinaryTree(preLeft, vinLeft);
root.right = reConstructBinaryTree(preRight, vinRight);
return root;
}
二叉树深度
//递归
function depth(node) {
if(!node)
return 0;
return Math.max(depth(node.left), depth(node.right))+1;
}
//非递归
function depth(root) {
var queue = [];
queue.push(root);
var count = 0;
while(queue.length != 0) {
var l = queue.length;
for(let i = 0; i < l; i++){
var node = queue.shift();
if(node.left)
queue.push(node.left);
if(node.right)
queue.push(node.right);
}
count++;
}
return count;
}
二叉树结点总数
function getNodeNumber(root) {
if (!root) return 0;
const queqe = [root];
let index = 0;
while(queqe.length > 0) {
let p = queqe.shift();
index++;
if (p.left) queqe.push(p.left);
if (p.right) queqe.push(p.right);
}
return index;
}
叶子结点数
function getLeafNum(node) {
if(!node)
return 0;
if(!node.left && !node.right)
return 1;
return getLeafNum(node.left)+getLeafNum(node.right);
}
层序恢复二叉树
var arr = [5,3,6,2,4,null,8,1,null,null,null,7,9]
function reconstructTree(arr) {
if (arr.length == 0) return null;
let root = new TreeNode(arr[0]);
let q = [root];
let idx = 1;
while (q.length > 0 && idx < arr.length) {
let cur = q.shift();
if (arr[idx] !== null) {
cur.left = new TreeNode(arr[idx]);
q.push(cur.left);
}
idx++;
if (arr[idx] !== null && idx < arr.length) {
cur.right = new TreeNode(arr[idx]);
q.push(cur.right);
}
idx++;
}
return root;
}