|
树：树就是一种非线性的数据结构，存储的是具有“一对多”关系的数据元素集合；【和现实生活中树的形状类似，只不过是倒置的树，从上向下依次扩展开】树是一个有限集合，当集合为空时则称为空树。
树的节点：使用树存储数据的每个元素都是一个节点。
根节点：节点1则称为根节点。
子节点：节点2，节点3是根节点的子节点。
叶子结点：树的末端没有子节点。
子树：根节点所分出来的一个节点，形成的一系列节点和元素构成子树。
节点的度和层次：
节点的度：当前节点，拥有的子树的个数称为节点的度。
树的度：一个树的度是树内各节点的度的最大值。
节点层次：从根节点开始，树根所在层为第一层，根的子节点所在的层为第二层，以此类推。
树的高度：树的层次数；树的高度也称为树的深度。
节点深度：根节点到该节点的路径所包含的边数。
节点高度：该节点到叶子节点的最长路径所包含的边数。
树的特点：
有且仅有一个根节点。
一个树如果有n个节点，那么它就有n-1条边。
树中的任意两个节点，有且仅有唯一的路径连通。
Binary Tree 二叉树
二叉树是特殊的有序树，每个节点最多有两个子节点。
子节点通常被称为“左孩子节点”和“右孩子节点”，并且遵循左小右大的原则。
二叉树的分类：
满二叉树：一个二叉树的所有非叶子结点都存在左右子节点，并且所有叶子结点都在同一层。
完全二叉树：如果二叉树除去最后一层为满二叉树，且最后一层的节点依次从左到右分布。
二叉树的存储：链式存储【链表】和顺序存储【数组】。
二叉树的遍历：
? ? ? ? ? ? ? ? 前序遍历：根节点->左子树->右子树
? ? ? ? ? ? ? ? 中序遍历：左子树->根节点->右子树
? ? ? ? ? ? ? ? 后序遍历：左子树->右子树->根节点
|