关于树的结构，在此不多做说明。一般常见的树结构可为以下形式：
一般是操作的二叉树，下图非二叉树，删掉叶子节点D即可。
遍历方式
对于树的遍历，一般分为：前序，中序， 后序，层次遍历。
前序：根节点 – 左子树 – 右子树
中序：左子树 – 根节点 – 右子树
后序：左子树 – 右子树 – 根节点
层次：按层次遍历
前中后序遍历，虽然名称不同，但是代码实现的基本方法是一样的。
遍历方法
对于前中后序三种遍历方式，在遍历方法上面都可以使用递归的遍历方法。其主要区别就是在于访问的时间节点的不同。
递归可以使用一个栈来模拟效果。使用一个栈来动态的保存所遍历过的路径上的元素。栈内元素是先进后出的，将之前遍历经过的节点放入到栈中。再获得栈内一个元素之后，按照当前是哪类遍历方法进行节点遍历，结束后，再弹出栈内元素，继续进行遍历。
对于层次遍历。使用一个队列来保存之前遍历过的节点。队列元素是先进先出的，将遍历过之后的节点加入到队列中。
复杂度
正常遍历时间复杂度是 O(n) ，空间复杂度是递归栈的大小 O(logN) 。如果想降低空间复杂度为 O(1) ，则需要使用Morris遍历方法，这个方法不需要为每个节点额外分配指针指向其前驱和后继节点，而是利用叶子节点中的右空指针指向中序遍历下的后继节点就可以了。节省需要用栈来记录前驱或者后继节点的额外空间，所以可以达到 O(1) 的空间复杂度。