树是一种用于表达层级结构的数据结构。软件开发中，常用树结构来抽象表达文档、组织结构图、图形图像等结构。
关于树结构本文讨论：有根树、二叉树。
有根树：根(root)是唯一一个没有父结点的结点。我们将没有子节点的结点称为外部节点(external node)或者叶节点(leaf)。除叶结点以外的结点称为内部节点(internal node)。
有根树T中结点x的子结点数称为x的度(degree)。如果没有子结点，那么他的度为0。从根r到结点x的路径长度称为x的深度(depth)。另外，结点x到叶结点的最大路径长度称为结点x的高(height)。一棵树中根结点的高度最大，我们称其为树的高。
有根树的表示：首先我们考虑如何存储输入的有根树。由于本题输入完成后，结点树不在发生变化，所以利用“左子右兄弟表示法”来表示树。
左子右兄弟表示法的各节点具有以下信息①结点node的父结点
②结点node最左侧的子结点
③结点node右侧紧邻的兄弟结点
一些输出函数：
获得各点的深度可通过如下算法：求结点node的深度时，需要从node出发逐一寻找父结点，统计node到root一共的边数。
考察：递归计算深度的算法只需将各点遍历一遍，所以算法复杂度为。
输出部分：
二叉树：一个根节点，且所有结点的子结点数不超过2。所以严格区分左右结点。不必通过"左子右兄弟表示法"。
所需数组即变量。
与有根树类似的求深度方法，只不过在找左右结点时deep+1。
遍历左右结点，取路径长的为高。
找兄兄弟结点，需返回父亲结点。
输出格式。
构造方法以及主函数：
输出：
想必你已经拥有了属于自己的二叉树，那么树的遍历操作(Tree Walk)显然是必不可少的。
按照根结点、左子树、右子树的顺序输出结点编号。称为树的前序遍历(Preorder Tree Walk)。
按照左子树、根结点、右子树的顺序输出结点编号。称为树的中序遍历(Inorder Tree Walk)。
按照左子树、右子树、根结点的顺序输出结点编号。称为树的后序遍历(Postorder Tree Walk)。
考察：二叉树遍历会对树的每一个结点进行一次访问，因此算法复杂度为。但是用递归实现遍历算法时要注意，一旦树的结点数量庞大且分布不均，很可能导致递归深度过深。
二叉树的重建(Reconstruction)：知道二叉树的前序遍历和中序遍历的结果，可以得出后序输出的结果。
前序输入pre={1,2,3,4,5,6,7,8,9}
中序输入in={3,2,5,4,6,1,8,7,9}
可得到如下二叉树。
设Preorder遍历的当前结点为c，在in中位置为m，m的左侧就是c的左子树，后侧就是右子树。例如当前结点为1，其在in中的位置为 3 2 5 4 6 [1] 8 7 9,那么当前树的根为1，左右子树就是3 2 5 4 6和8 7 9，以此类推Preorder的下一个结点为2，则其左右子树为3和5 4 6。实现如下。
