数据结构(一) —— 树的基本概念(树的节点、度、高度、深度..)

说明：遍历方式都是相对于父节点而言的。
1.前序遍历
父节点 => 左孩子 => 右孩子

2.中序遍历
左孩子 => 父节点 =>右孩子

3.后序遍历
左孩子 => 右孩子 => 父节点

每个节点最多只能有两个节点。

设二叉树的深度为k，除第k层外，其他各层(0 ~ k-1)的节点数都达到最大个数，第k层所有节点都连续集中在最左边。

如果二叉树的层数为k，且节点总数为2^(k+1) - 1，则该二叉树就是满二叉树。

左子树上的值都小于父节点的值，右子树上的值都大于或等于父节点的值。（中序遍历有序）

一棵AVL树是每个节点的左子树和右子树的高度最多差1的二叉查找树。
平衡因子 = |左子树高度 - 右子树高度|

本章内容只是简单介绍了树的一些基本概念以及一些常见的树，关于AVL树，红黑树，B树，B+树等等会以独立的篇章详细说明。

~