树的定义和表示
二叉树
1、树的基本概念
树：n个结点构成的有限集合。当n=0时，称为空树；
- 子树是不相交的；
- 除了根节点外，每个结点有且仅有一个父节点；
- 一颗N个结点的树有N-1条边。
2、树的一些基本术语
-
结点的度：结点的子树个数；
-
树的度：树的所有结点中最大的度数；
-
叶结点：度为0的结点；
-
兄弟结点：具有同一父结点的各结点彼此是兄弟结点。
-
路径和路径长度：从结点n1到nk的路径为一个结点序列n1,n2,…,nk,ni是ni+1的父结点。路径所包含边的个数为路径的长度；
-
结点的层次：规定根结点在1层，其他任意结点的层数是其父结点的层数加1；
-
树的深度：树中所有结点中的最大层次是这颗树的深度。
3、树的表示
链表表示法：这个会造成指针域的浪费。
左儿子-右兄弟表示法：对于n个结点的树，需要2n个指针域，其中有n-1条边，意味着有n-1个指针需要用，那么浪费了n+1个指针。
将上面的表示法向右旋转45度：得到了二叉树。