编程语言/二叉树

来自康健生活
跳到导航 跳到搜索

引言

性质

  • 第 i 层最多节点数:
  • 深度为 k 的完全二叉树, 最多节点数:
  • 对任何一棵二叉树 T,如果总结点数为 n0,度为 2 (子树数目为 2 )的节点数为 n2,则

树和二叉树的差别

  • 树的节点个数至少为 1,而二叉树的节点个数可以为 0
  • 树中节点的最大度数(节点数量)没有限制,而二叉树的节点的最大度数为 2
  • 树的节点没有左右之分,而二叉树的节点有左右之分

二叉树分类

满二叉树

一棵深度为 k 且有 个节点的二叉树称为满二叉树。

完全二叉树

完全二叉树是指最后一层左边是满的,右边可能满也可能不满,然后其余层都是满的二叉树称为完全二叉树, 满二叉树 完全二叉树。

平衡树

二叉搜索树

  • 若任意节点的左子树不空,则左子树上所有节点的值均小于它的根节点的值;
  • 若任意节点的右子树不空,则右子树上所有节点的值均大于它的根节点的值;
  • 任意节点的左、右子树也需要满足左边小右边大的性质

(来源摘自互联网示例,作者 accord)

以下不满足搜索二叉树示例:

链式存储结构(三叉链表)

查找

遍历

中序遍历(inorder)
前序遍历(preorder)
后序遍历(postorder)

树的存储

数组

链表

解题

BFS

DFS

其他

参考力扣 第 105 题,根据中序划分二叉树子树,然后递归求解

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {number[]} preorder
 * @param {number[]} inorder
 * @return {TreeNode}
 */
var buildTree = function(preorder, inorder) {
    if (!preorder.length || !inorder.length) {
        return null;
    }

    const rootValue = preorder[0];
    const node = new TreeNode(rootValue);

    let i = 0;
    for (; i < inorder.length; ++i) {
        if (inorder[i] === rootValue) {
            break;
        }
    }

    node.left = buildTree(preorder.slice(1, i + 1), inorder.slice(0, i));
    node.right = buildTree(preorder.slice(i + 1), inorder.slice(i + 1));
    return node;
};

(来源摘自互联网示例,作者 心谭)