树的概念

树是一种用于描述一对多的数据结构，比如文件目录结构就可以用树来描述。树的定义如下：

树是n(n≥0)个结点的有限集合，n=0时称为空树，在任意一棵非空树中：

1. 有且仅有一个特定的称为根的结点。
2. 当n>1时，其余结点可分为m个互不相交的有限集T1,T2,……Tm，每个集合本身又是一棵树，并且称为根的子树。

注意两点，根结点是唯一的，子树互不相交。

二叉树是一种常用的树，它只有两个子结点，除此外多叉树也可能用到。二叉树是一种常用的树，它只有两个子结点，除此外多叉树也可能用到，如果一个集合里包含不止一颗树，则称为森林。

树的存储

树的存储分为顺序存储和链式存储。顺序存储是指通过数组来存储树，分为双亲表示法，孩子表示法，双新孩子表示法，如下：

链式存储使用链表来存储树，分为孩子链表表示法和孩子兄弟表示法，如下：

Image Added

Image Added

树的转换

多叉树转换为二叉树

使用孩子兄弟表示法，长子当左结点，兄弟当右结点。

Image Added

二叉树还原多叉树

左结点作为长子，右斜线作为兄弟。

Image Added

森林转换为二叉树

把森林中的每棵树的根当成兄弟结点，先把每个树转换成二叉树，然后再将每棵树的根连接在右斜线上。

Image Added

二叉树还原为森林

右斜线上的每个结点作为一棵树的根，将每棵二叉树还原为树。

Image AddedImage Removed

1. 二叉树按层遍历。
2. 二叉树前序、中序、后序遍历递归写法，非递归写法。
3. 二叉树的层次遍历，双端队列写法。