大话数据结构-树 _前序遍历

1 概述
树（Tree）是n（n >= 0）个结点的有限集。n = 0时称为空树。在任意一棵非空树中：
(1) 有且仅有一个特定的称为根（root）的结点；
(2) 当n > 1时，其余结点可分为m（m > 0）个互不相交的有限集T1、T2、…、Tm ，其中每一个集合本身又是一棵树，并且称为根的子树（）。
2 结点分类
树的结点包含一个数据元素及若干指向其子树的分支。结点拥有的子树数称为结点的度（）。度为0的结点称为叶结点（Leaf）或终端结点；度不为0的结点称为非终端结点或分支结点。除根结点之外，分支结点也称为内部结点。树的度是树内各结点的度的最大值。
3 结点间关系
结点的子树的根称为该结点的孩子（Child），相应地，该结点称为孩子的双亲（）。同一个双亲的孩子之间互称兄弟（），结点的祖先是从根到该结点所经分支上的所有结点。以某结点为根的子树中的任一结点都称为该结点的子孙。
4 树的其他相关概念
结点的层次（Level）从根开始定义起，根为第一层，根的孩子为第二层。其双亲在同一层的结点互为堂兄弟。树中结点的最大层次称为树的深度（Depth）或高度。
如果将树中结点的各子树看成从左至右是有次序的，不能互换的，则称该树为有序树，否则称为无序树。森林（）是m（m >= 0）棵互不相交的树的集合。对树中每个结点而言，其子树的集合即为森林。
5 抽象数据类型
6 树的存储结构
首先，需要知道，在一棵树中，每个结点都是有编号的，从第一层开始依次从左向右、从上向下，从0开始计算编号，如下图所示：
6.1 双亲表示法
在结点中定义一个指针，指向其（双亲）结点的存储结构，称为双亲表示法。
/*** 双亲表示法结点** @author Korbin* @date 2023-01-18 11:11:13**/@Datapublic class ParentTreeNode {/*** 数据元素**/private T data;/*** 双亲指针**/private int parent;}
没有双亲的结点，即根结点，其双亲指针指向-1 。
双亲表示法中，树结构会定义结点数组，以及根结点位置、总结点数等信息：
/*** 树的双亲表示法** @author Korbin* @date 2023-01-18 10:21:28**/public class ParentTree {/*** 结点**/private ParentTreeNode nodes;/*** 最大结点数量**/private int maxSize;/*** 根结点指针**/private int root;/*** 结点数量**/private int length;}
对于如下一棵树，按照双亲表示法，可得到其data和信息：
下标
0
A
-1
1
【大话数据结构-树】B
0
2
C
0
3
D
1
4
E
1
5
F
2
6
G
2
7
H
2
8
I
5
9
J
6
10
K
7
这样的存储结构，我们可以根据结点的指针很容易找到它的双亲结点，所用的时间复杂度为O(1) ，直到为-1时，表示找到了树结点的根。
可如果我们要知道结点的孩子是什么，那就只能遍历树了。这种情况下，可以考虑增加一个域，表示最左边的孩子位置，也叫长子域，对于没有孩子的结点，这个长子域就设置为-1 ，那么树的结点信息就变成了：
下标
0
A
-1