这种数据结构真的很像我们现实生活中的“树”,这里面每个元素我们叫作“节点”;用来连线相邻节点之间的关系,我们叫作“父子关系”。

比如下面这幅图,A 节点就是 B 节点的父节点,B 节点是 A 节点的子节点。B、C、D 这三个节点的父节点是同一个节点,所以它们之间互称为兄弟节点。我们把没有父节点的节点叫作根节点,也就是图中的节点 E。我们把没有子节点的节点叫作叶子节点或者叶节点,比如图中的 G、H、I、J、K、L 都是叶子节点。

除此之外,关于“树”,还有三个比较相似的概念:高度(Height)、深度(Depth)、层(Level)。它们的定义是这样的:


二叉树

二叉树,顾名思义,每个节点最多有两个“叉”,也就是两个子节点,分别是左子节点和右子节点。不过,二叉树并不要求每个节点都有两个子节点,有的节点只有左子节点,有的节点只有右子节点。以此类推,你可以想象一下四叉树、八叉树长什么样子。

二叉树的遍历

如何将所有节点都遍历打印出来呢?经典的方法有三种,前序遍历、中序遍历和后序遍历。其中,前、中、后序,表示的是节点与它的左右子树节点遍历打印的先后顺序。

  • 前序遍历是指,对于树中的任意节点来说,先打印这个节点,然后再打印它的左子树,最后打印它的右子树。

  • 中序遍历是指,对于树中的任意节点来说,先打印它的左子树,然后再打印它本身,最后打印它的右子树。

  • 后序遍历是指,对于树中的任意节点来说,先打印它的左子树,然后再打印它的右子树,最后打印这个节点本身。

实际上,二叉树的前、中、后序遍历就是一个递归的过程。比如,前序遍历,其实就是先打印根节点,然后再递归地打印左子树,最后递归地打印右子树。

// 前序遍历
function preOrder(root){
    if(root==null){
        return
    }
    console.log(root); // 伪代码 当前节点的处理
    preOrder(root.left);
    preOrder(root.right);

}

// 中序遍历
function inOrder(root){
    if(root==null){
        return
    }
    // 遍历左子树
    inOrder(root.left);
    // 伪代码 当前节点的处理
    console.log(root);
    // 遍历右子树
    inOrder(root.right)
}

// 后序遍历
function postOrder(root){
    if(root==null){
        return
    }
    // 遍历左子树
    postOrder(root.left);
    // 遍历右子树
    postOrder(root.right)
    // 伪代码 当前节点的处理
    console.log(root);
}

226.翻转二叉树

给你一棵二叉树的根节点 root ,翻转这棵二叉树,并返回其根节点。

从根节点开始,递归地对树进行遍历,并从叶子节点先开始翻转。如果当前遍历到的节点 root 的左右两棵子树都已经翻转,那么我们只需要交换两棵子树的位置,即可完成以 root 为根节点的整棵子树的翻转。

只要把二叉树上的每一个节点的左右子节点进行交换,最后的结果就是完全翻转之后的二叉树。

function invertTree(root){
    if(root==null){
        return null
    }

    var left = invertTree(root.left);
    var right = invertTree(root.right);
    root.left = right;
    root.right = left;
    return root;
}
文档更新时间: 2022-04-27 17:40   作者:张老师