Java中的二叉树，前中后序遍历的递归和迭代写法。

• 一、树是什么？
• • 树的特点
• 二、二叉树
• • 1.概念及特点
  • 2.常见的二叉树
• 三、二叉树的遍历（递归和迭代）
• • 3.1自定义二叉树
  • 3.2 前序遍历(递归)
  • 3.3 前序遍历(迭代)
  • 3.4.中序遍历(递归)
  • 3.5 中序遍历(迭代)
  • 3.6 后序遍历(递归)
  • 3.7 后序遍历(迭代)
• 总结

树是一种非线性的数据结构，它是由n(n >= 0)个有限结点组成的一个具有层次关系的集合。(线性数据结构就是：线性表，数组，栈，链表，队列，字符串…元素之间逻辑上一个挨着一个，呈值直线排列)把它叫做树是因为它看起来像一颗倒着的树，意思就是根朝上，叶子朝下。

1. 有一个特殊的结点，称为根节点，根节点没有前驱结点。
2. 除根节点外，其余节点被分成M(M > 0) 个互不相交的集合T1、T2、…、Tm,其中每一个集合又是一颗子树。每颗子树的根节点有且只有一个前驱，可以有0个或者多个后继。
3. 树是递归定义的。
4. 子树不相交。
5. 除了根节点没有父节点之外，每个节点有且只有一个父节点。
6. 树，边的个数x，和树中节点的个数n，x=n - 1（每个节点都有一个父节点，只有根节点没有父节点）
7. 节点和树的“度” ： 节点的度是指该节点中包含的子树个数称为该节点的度。树的度：树中最大的节点的度就称为子树的度。
8. 叶子节点： 度为0的节点。即该节点没有任何子树。
9. 节点的层次(高度)： 从根节点开始计算，根节点为第一层，根节点的左子树和右子树是第二层，以此类推。
10. 树的高度： 当前树中节点高度最大的即为树的高度。

树中节点最大的度为2的树称之为二叉树。
在二叉树中一个节点最多有两颗子树，二叉树节点的度 <=2；子树有左右之分，左右顺序不能颠倒。

1. 深度为k的二叉树中，最多存在 (2^k )- 1 个节点。
2. 在第k层，该层最多有 2^(k-1) 个节点。
3. 任意二叉树都满足节点个数n和边长x具备 :
   x = n -1

1. 满二叉树： 在该二叉树中，每一层节点个数都是最大值，每一层节点个数都是拉满了。
   

2. 完全二叉树： 除了最深的一层节点不满，其余层都满了。满二叉树就是一种特殊的完全二叉树。完全二叉树中不存在只有右子树，没有左子树的节点。若存在度为1的节点，那么该节点必然只有左子树，且该节点有且只能有一个。完全二叉树的节点编号(根节点为1)和满二叉树完全一致。

3. 二分搜索树(BST)
   节点的值之间有一个大小关系：
   左子树的值 < 根节点的值 < 右子树的值
   如图：
   
   若在BST中查找一个元素，其实就是二分查找。
4. 平衡二叉树
   该树中任意一个节点的左右子树高度差 <= 1。

按照一定的顺序访问这颗树的所有元素，做到不重复，不遗漏。
对于二叉树来说，一共有四种遍历方式

1. 前序遍历(根 左 右) 节点第一次访问的时候就输出。
2. 中序遍历(左 根 右) 节点第二次访问的时候输出。
3. 后序遍历(左 右 根) 节点第三次访问的时候输出。
4. 层序遍历(从根节点开始，一层一层去遍历)
   前三种遍历方式属于深度优先遍历，层序遍历属于广度优先遍历。

• 我们自己定义一个二叉树：
  
  比如我们要手写出这颗二叉树的中序遍历，按照上面所说的第二次访问节点输出，有以下流程：

1. 先一路走到 D ,一路上过来的节点都属第一次访问，不输出，然后访问 D 的左子树，发现为空，倒回来再走到 D ，此时D就是第二次访问，进行输出，然后再访问D的右子树，发现为空，再倒回到D。
2. D这个节访问完毕后，倒回到B节点，此时B是第二次访问，输出B,然后访问B的右子树。
3. E节点是第一次访问，左根右，继续往左走，走到G，继续访问G的左子树，发现为空，倒回去访问G，此时G是第二次访问，进行输出；再去访问G的右子树，节点H是第一次访问，继续往左走，H的左子树为空，倒回去走H此时H是第二次访问，进行输出。
   4.此时我们已经输出了 D B G H,剩下的节点以次类推就行。
   那么上面这颗二叉树的遍历代码应该如何去写呢？我们首相应该想到的是递归，因为二叉树就是一个天然的递归结构。

public void build() {
		//先将所有的节点值保存到node中
        TreeNode node = new TreeNode<>('A');
        TreeNode node1 = new TreeNode<>('B');
        TreeNode node2 = new TreeNode<>('C');
        TreeNode node3 = new TreeNode<>('D');
        TreeNode node4 = new TreeNode<>('E');
        TreeNode node5 = new TreeNode<>('F');
        TreeNode node6 = new TreeNode<>('G');
        TreeNode node7 = new TreeNode<>('H');
        //根据上图连接二叉树
        //A节点的左子树是B,也就是node1，下面的节点以此类推
        node.left = node1;
        node.right = node2;
        node1.left = node3;
        node1.right = node4;
        node2.right = node5;
        node4.left = node6;
        node6.right = node7;
        //根节点是A
        root = node;
        //自定义类型TreeNode类保存树的左右子树和节点值
        private class TreeNode {
        	//当前结点的值
        	E val;
        	//左子树的根
        	TreeNode left;
        	//右子树的根
        	TreeNode right;

        	public TreeNode(E val) {
        
        		this.val = val;
        
        	}
	}
}

代码如下：

	//这里不太明的话可以按照我的代码自己画一下递归展开图，就会容易理解很多
	public void preOrder(TreeNode root) {
		//判断传进来的节点是否为空
        if (root == null) {
            return;
        }
        //前序遍历是根左右
        // 1.先打印根节点的值
        System.out.print(root.val + " ");
        //2.递归去访问左子树
        preOrder(root.left);
        //3.递归访问右子树
        preOrder(root.right);
    }

定义测试类：

public class TreeTest {
	public static void main(String[] args) {
        MyBinTree binTree = new MyBinTree();
        binTree.build();
        System.out.println("前序遍历：");
        binTree.preOrder(binTree.root);
    }
}

运行结果如下：

public List preorderNoRecursion(TreeNode root) {
        List ret = new ArrayList<>();
        if (root == null) {
            return ret;
        }
        Deque stack = new LinkedList<>();
        stack.push(root);
        while(!stack.isEmpty()) {
            TreeNode node = stack.pop();
            //添加根结点
            ret.add((Character) node.val);
            //因为栈是先进后出的，所以先添加右子树，后添加左子树
            //下一次循环开始的时候，先添加到数组ret中的就是左子树的值了
            if (node.right != null) {
                stack.push(node.right);
            }
            if (node.left != null) {
                stack.push(node.left);
            }
        }
        return ret;
    }

定义测试类：

public class TreeTest {
	public static void main(String[] args) {
        MyBinTree binTree = new MyBinTree();
        binTree.build();
        System.out.println("前序遍历：");
        System.out.println(binTree.preorderNoRecursion(binTree.root));
    }
}

运行结果如下:

代码如下：

public void inOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        //先访问左子树
        inOrder(root.left);
        //打印当前根节点的值
        System.out.print(root.val + " ");
        //再访问右子树
        inOrder(root.right);
    }

大家自己在测试类里面调用中序遍历，我这里就不再重复写了

运行结果如下：

public List