1、树的基本定义

2、树的相关术语

3、二叉树的基本定义

4、二叉查找树的创建

5、二叉树的基础遍历

6、二叉树的层序遍历

7、二叉树的最大深度问题

//获取整个树的最大深度
    public int maxDepth(){
        return maxDepth(root);
    }


    //获取指定树x的最大深度
    private int maxDepth(Node x){
        if (x==null){
            return 0;
        }
        //x的最大深度
        int max=0;
        //左子树的最大深度
        int maxL=0;
        //右子树的最大深度
        int maxR=0;

        //计算x结点左子树的最大深度
        if (x.left!=null){
            maxL = maxDepth(x.left);
        }
        //计算x结点右子树的最大深度
        if (x.right!=null){
            maxR = maxDepth(x.right);
        }
        //比较左子树最大深度和右子树最大深度，取较大值+1即可

        max = maxL>maxR?maxL+1:maxR+1;

        return max;
    }

//测试代码
public class Test {
    public static void main(String[] args) throws Exception {
        BinaryTree<String, String> bt = new BinaryTree<>();
        bt.put("E", "5");
        bt.put("B", "2");
        bt.put("G", "7");
        bt.put("A", "1");
        bt.put("D", "4");
        bt.put("F", "6");
        bt.put("H", "8");
        bt.put("C", "3");
        int i = bt.maxDepth();
        System.out.println(i);    
    }
}

8、折纸问题

package cn.itcast.algorithm.test;

import cn.itcast.algorithm.linear.Queue;

public class PagerFoldingTest {

    public static void main(String[] args) {

        //模拟这只过程，产生树
        Node<String> tree = createTree(2);
        //遍历树，打印每个结点
        printTree(tree);

    }

    //通过模拟对折N次纸，产生树
    public static Node<String> createTree(int N){
        //定义根结点
        Node<String> root=null;
        for (int i = 0; i < N; i++) {

            //1.当前是第一次对折
            if (i==0){
                root = new Node<>("down",null,null);
                continue;
            }
            //2.当前不是第一次对折
            //定义一个辅助队列，通过层序遍历的思想，找到叶子结点，叶子结点添加子节点
            Queue<Node> queue = new Queue<>();
            queue.enqueue(root);

            //循环遍历队列
            while(!queue.isEmpty()){
                //从队列中弹出一个结点
                Node<String> tmp = queue.dequeue();
                //如果有左子结点，则把左子结点放入到队列中
                if (tmp.left!=null){
                    queue.enqueue(tmp.left);
                }
                //如果有右子结点，则把右子结点放入到队列中
                if (tmp.right!=null){
                    queue.enqueue(tmp.right);
                }
                //如果同时没有左子结点和右子结点，那么证明该节点是叶子结点，只需要给该节点添加左子结点和右子结点即可
                if (tmp.left==null && tmp.right==null){
                    tmp.left = new Node<String>("down", null,null);
                    tmp.right = new Node<String>("up",null,null);
                }
            }
        }
        
        return root;
    }


    //打印树中每个结点到控制台
    public static void printTree(Node<String> root){
        //需要使用中序遍历完成
        if (root==null){
            return;
        }

        //打印左子树的每个结点
        if (root.left!=null){
            printTree(root.left);
        }
        //打印当前结点
        System.out.print(root.item+" ");
        //打印右子树的每个结点
        if (root.right!=null){
            printTree(root.right);
        }

    }



    //结点类
    private static class Node<T>{
        public T item;//存储元素
        public Node left;
        public Node right;

        public Node(T item, Node left, Node right) {
            this.item = item;
            this.left = left;
            this.right = right;
        }
    }


}