树

树

树的定义

树是n（n>=0）个结点的有限集。当n = 0时，称为空树。在任意一棵非空树中应满足：

• 有且仅有一个特定的称为根的结点
• 当n>1时，其余节点可分为m（m>0）个互不相交的有限集T1,T2,…,Tm，其中每个集合本身又是一棵树，并且称为根的子树
• 树的定义是递归的，树是一种递归的数据结构。

树的性质

n个节点的树中有n-1条边

树转化为二叉树

• 将左孩子作为当前节点的左孩子
• 将右兄弟作为当前节点的右孩子
• 因此，转化后的二叉树，根节点没有右孩子（因为它没有右兄弟）

二叉树

二叉树的性质

• 二叉树第i层上的节点数目最多为 2{i-1} (i≥1)。
• 深度为k的二叉树至多有2{k}-1个节点（k>=1）。
• 包含n个节点的二叉树的高度至少为log2 (n+1)。
• 在任意一颗二叉树中，若终端节点的个数为n0，度为2的节点数为n2，则n0=n2+1。

例子

1. 存在一棵总共有2016个节点的二叉树，其中有16个节点只有一个孩子？

错误，根据树的性质，一条边贡献两个度，树的边数等于结点数-1，设度为0的点（叶子节点）有N0个，度为1的（只有一个孩子）为N1个，度为2的为N2个，则N1+N2+N0=2016，边数为2016-1=2015，共有4030度，2*N2+16=4030，N2=2007，与N1=16相矛盾。

2. 二叉树就是度为2的树

• 错误，二叉树不等于度为2的树
  • 度为2的树，必须有三个节点以上，而二叉树可以为空
  • 二叉树的节点度不一定要为2
  • 二叉树的孩子节点有左右之分，度为2的树没有

各种各样的二叉树

满二叉树

如果一棵二叉树只有度为0的结点和度为2的结点，并且度为0的结点在同一层上，则这棵二叉树为满二叉树。

完全二叉树

在完全二叉树中，除了最底层，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置(必须从左到右排列）。若最底层为第 h 层（h从1开始），则该层包含 1~ 2^(h-1) 个节点。

二叉排序树（二叉搜索树）

• 节点有数值
• 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
• 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
• 它的左、右子树也分别为二叉排序树

平衡二叉树（AVL树）

又被称为AVL（Adelson-Velsky and Landis）树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

C++中map、set、multimap，multiset的底层实现都是平衡二叉搜索树

详情请转

数组存储树

遍历方式：如果父节点的下标是i，左孩子就是2i+1，右孩子是2i+2。

二叉树遍历方式

• 深度优先遍历
  • 前序遍历（中左右）
  • 中序遍历（左中右）
  • 后序遍历（左右中）

• 广度优先遍历
  • 层次遍历：5 4 6 1 2 7 8