树和二叉树知识小结

[xszi]

待更新

[xszi]

树与二叉树

引言

开始之前，请看一下几个问题，然后带着问题进入本章内容：

• 什么是树？
• 树的高度怎么计算？
• 什么是二叉树？
• 什么是平衡二叉树？
• 如何用代码表示一棵二叉树？
• 二叉树的前序，中序，后续遍历是什么？如何实现？

一 ，树

树是一种 非线性结构。它遵循：

• 仅有唯一一个根节点，没有节点则为空树
• 除根节点外，每个节点都有并仅有一个父节点
• 节点间不能形成闭环

关于树的几个概念：

• 节点的深度：从根节点到该节点所经历 边 的个数
• 节点的高度：节点到叶节点的最长路径
• 树的深度：根节点到最远叶子节点的最长路径上的节点数
• 树的高度：根节点的高度

其中， A与B之间的连接称为 边，B的深度为1；B的 高度 为B到叶节点G或H或F的最长路径，所以为2。

高度

树的高度计算公式：

下图每个节点值都代表当前节点的高度：

二，二叉树

最多能分两个叉的树。

• 平衡二叉树

二叉树中，每一个节点的左右子树的高度相差不能大于 1，称为平衡二叉树。

• 完美二叉树（perfect binary tree）：除了叶结点外每一个结点都有左右子叶且叶子结点都处在最底层的二叉树
• 完全二叉树（complete binary tree）：深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第h 层所有的结点都连续集中在最左边（一种 特殊 的平衡二叉树）
• 完满二叉树（full binary tree）：除了叶子节点之外的每一个节点都有两个孩子节点。（只要你有孩子，就必须有两个孩子）

三，用代表表示一棵二叉树

1.链式存储法

每个节点包含三部分

• 当前节点的 val
• 左子节点 left
• 右子节点 right

所以节点可以表示为：

function Node(val) {
	// 保存当前节点key值
    this.val = val
    // 指向左子节点
    this.left = null
    // 指向右子节点
    this.right = null
}

可以由根节点通过左右指针连接起来形成一棵树

function BinaryTree() {
    let Node = function(val) {
        this.val = null
        this.left = null
        this.right = null
    }
    let root = null
}

2. 数组存储法（适用于完全二叉树）

   所有的节点满足三种关系：

   • 位置为 i 的节点，它的父节点位置为 i/2
   • 它的左子节点 2i
   • 它的右子节点 2i+1

因此，可以把完全二叉树存储在数组里（从下标为 1 开始存储），可以通过下标找到任意节点的父子节点。从而完整的构建出这个完全二叉树。这就是数组存储法。

数组存储法相对于链式存储法不需要为每个节点创建它的左右指针，更为节省内存。

四，二叉树的前序，中序，后续遍历（见题）

参考来源：小白都可以看懂的树与二叉树