解密二叉树:探索概念、类型与常见算法的奥秘(顺带说一下React中的reconcile)

简介: 二叉树作为程序的一种数据结构,应用广泛,比如React中的reconcile过程,Fiber树的调和过程。确实,在React中,Fiber树是通过child和sibling连接子节点和兄弟节点的方式来表示的,这与普通的二叉树有所不同。在React中,reconcile过程是将虚拟DOM转化为实际DOM的过程。通过比较新旧两棵树的差异,React可以高效地更新实际DOM,而不是每次都完全重新渲染整个DOM树。这个过程中会涉及到对Fiber树的遍历和调整,确保更新只发生在需要更新的部分。Fiber树作为一种数据结构,可以帮助React跟踪组件的状态和变化,以及进行调度和渲染。它使用链表的形

u=2845516294,195367212&fm=30&app=106&f=PNG.png

前言

整理的关于二叉树的概念、类型和常见算法的内容非常详细,涵盖了二叉树的基本知识和常见操作。下面是文章的内容概要:

背景

  • 介绍了二叉树在程序中的广泛应用,如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. 确定两种遍历方式的左右子树顺序
    3. 在左子树中递归步骤1和2
    4. 在右子树中递归步骤1和2
    5. 打印当前根
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;
}
目录
相关文章
|
27天前
|
存储 算法
数据结构与算法学习二二:图的学习、图的概念、图的深度和广度优先遍历
这篇文章详细介绍了图的概念、表示方式以及深度优先遍历和广度优先遍历的算法实现。
43 1
数据结构与算法学习二二:图的学习、图的概念、图的深度和广度优先遍历
|
3天前
|
机器学习/深度学习 JSON 算法
二叉树遍历算法的应用场景有哪些?
【10月更文挑战第29天】二叉树遍历算法作为一种基础而重要的算法,在许多领域都有着不可或缺的应用,它为解决各种复杂的问题提供了有效的手段和思路。随着计算机科学的不断发展,二叉树遍历算法也在不断地被优化和扩展,以适应新的应用场景和需求。
8 0
|
27天前
|
存储 算法 关系型数据库
数据结构与算法学习二一:多路查找树、二叉树与B树、2-3树、B+树、B*树。(本章为了解基本知识即可,不做代码学习)
这篇文章主要介绍了多路查找树的基本概念,包括二叉树的局限性、多叉树的优化、B树及其变体(如2-3树、B+树、B*树)的特点和应用,旨在帮助读者理解这些数据结构在文件系统和数据库系统中的重要性和效率。
16 0
数据结构与算法学习二一:多路查找树、二叉树与B树、2-3树、B+树、B*树。(本章为了解基本知识即可,不做代码学习)
|
27天前
|
存储 算法 搜索推荐
数据结构与算法学习十七:顺序储存二叉树、线索化二叉树
这篇文章主要介绍了顺序存储二叉树和线索化二叉树的概念、特点、实现方式以及应用场景。
17 0
数据结构与算法学习十七:顺序储存二叉树、线索化二叉树
|
1月前
|
存储 算法
【二叉树】—— 算法题
【二叉树】—— 算法题
【二叉树】—— 算法题
|
27天前
|
存储 算法
数据结构与算法学习十六:树的知识、二叉树、二叉树的遍历(前序、中序、后序、层次)、二叉树的查找(前序、中序、后序、层次)、二叉树的删除
这篇文章主要介绍了树和二叉树的基础知识,包括树的存储方式、二叉树的定义、遍历方法(前序、中序、后序、层次遍历),以及二叉树的查找和删除操作。
22 0
|
3月前
|
前端开发 JavaScript 数据处理
如何学习React的高级概念?
【8月更文挑战第26天】如何学习React的高级概念?
39 2
|
3月前
|
存储 前端开发 JavaScript
React 中的 Memoization 概念
【8月更文挑战第31天】
35 0
|
3月前
|
前端开发
React 中的 Hook 概念
【8月更文挑战第31天】
29 0
|
3月前
|
前端开发 API
React 中 Context 的概念
【8月更文挑战第31天】
37 0