二叉樹的定義

class TreeNode  
{  
    int value;  
    TreeNode parent;  
    TreeNode left;  
    TreeNode right;  
    public TreeNode(int value, TreeNode parent, TreeNode left, TreeNode right) {  
        this.value = value;  
        this.parent = parent;  
        this.left = left;  
        this.right = right;  
    }      
}  

向二叉樹中插入節(jié)點(diǎn)

public BinaryNode insert(T data,BinaryNode root){
    //終止條件
    if(root==null){
        root=new BinaryNode(data,null,null);
    }

    //比較插入結(jié)點(diǎn)的值橡淆，決定向左子樹還是右子樹搜索
   if (data < root.data){//左
        root.left=insert(data,root.left);
    }
    else if(data > root.data){//右
        root.right=insert(data,root.right);
    }
    else {
        ;//已有元素就沒必要重復(fù)插入了
    }
    return root;
}

搜索二叉樹中最大值和最小值

public BinaryNode findMin(BinaryNode root){
   if (root==null)//終止條件
       return null;
   else if (root.left==null)//如果沒有左結(jié)點(diǎn),那么t就是最小的
       return root;
   return findMin(root.left);
}

private BinaryNode findMax(BinaryNode root){
   if (root==null)//終止條件
       return null;
   else if (root.right==null)
       return root;
   return findMax(root.right);
}

搜索二叉樹的深度（height）和節(jié)點(diǎn)數(shù)（size）

public int height(BinaryNode root){
    if (root==null){
        return 0;
    }
    else {
        int l=height(root.left);
        int r=height(root.right);
        return (l>r) ? (l+1):(r+1);//返回并加上當(dāng)前層
    }
}

public int size(BinaryNode root){
       if (root == null)
           return 0;
       else
       {
           //對比漢諾塔:H(n)=H(n-1) + 1 + H(n-1)
           return size(root.left) + 1 + size(root.right);
       }
    }

二叉搜索樹的遍歷算法

（前根）前序遍歷：根節(jié)點(diǎn)->左子樹->右子樹
（中根）中序遍歷：左子樹->根節(jié)點(diǎn)->右子樹
（后根）后序遍歷：左子樹->右子樹->根節(jié)點(diǎn)

1. 前序遍歷（先根遍歷）

①遞歸算法

public void preOrder(BinaryNode root){
    if (root!=null) {//遞歸結(jié)束條件
        //先訪問根結(jié)點(diǎn)
        System.out.println(root.data);
        //遍歷左子樹
        preOrder(root.left);
        //遍歷右子樹
        preOrder(root.right);
    }
}

②非遞歸算法

public void preOrder(BinaryNode root){
    //構(gòu)建用于存放結(jié)點(diǎn)的棧
    LinkedStack<BinaryNode> stack=new LinkedStack<>();

    //邊循環(huán)邊輸出中節(jié)點(diǎn)母赵，一直到最低逸爵，然后開始搜索其對應(yīng)的右子樹
    while (root!=null||!stack.isEmpty()){
        if (root!=null){
            //訪問該結(jié)點(diǎn)
            System.out.println(root.data);
            //將已訪問過的結(jié)點(diǎn)入棧
            stack.push(root);

            //繼續(xù)訪問其左孩子凹嘲，直到root為null
            root=root.left;
        }
        else { 
            //若p=null 棧不為空,則說明已沿左子樹訪問完一條路徑, 從棧中彈出棧頂結(jié)點(diǎn),并訪問其右孩子
            root=stack.pop();//獲取已訪問過的結(jié)點(diǎn)記錄
            root=root.right;
        }
    }
}

中續(xù)遍歷（中根遍歷）

特點(diǎn)：二叉搜索樹的中序遍歷是按照節(jié)點(diǎn)值依次遞增的搜索順序遍歷

①遞歸算法

public void inOrder(BinaryNode root) {
    if (root!=null) {//遞歸結(jié)束條件
        //先遍歷左子樹
        inOrder(root.left);
        //再遍歷根結(jié)點(diǎn)
        System.out.println(root.data);
        //最后遍歷右子樹
        inOrder(root.right);
    }
}

②非遞歸算法

public void inOrder(BinaryNode root){
   //構(gòu)建用于存放結(jié)點(diǎn)的棧
   LinkedStack<BinaryNode> stack=new LinkedStack<>();
  
    //需要從最低左子樹開始輸出，所以循環(huán)至最低
   while (root!=null||!stack.isEmpty()){
       while (root!=null){//把左孩子都入棧,至到左孩子為null
           stack.push(root);
           root=root.left;
       }
       //如果棧不為空,因?yàn)榍懊孀蠛⒆右讶咳霔?       if(!stack.isEmpty()){
           root=stack.pop();
           //訪問p結(jié)點(diǎn)
           System.out.println(root.data);
           //訪問p結(jié)點(diǎn)的右孩子
           root=root.right;
       }
   }
}

后續(xù)遍歷（后根遍歷）

①遞歸算法

public void postOrder(BinaryNode root) {
   if (root!=null) {//遞歸結(jié)束條件
       //先遍歷左子樹
       postOrder(root.left);

       //再遍歷右子樹
       postOrder(root.right);

       //最后遍歷根結(jié)點(diǎn)
       System.out.println(root.data);
   }
}

②非遞歸算法

public void postOrder(BinaryNode root){
   //構(gòu)建用于存放結(jié)點(diǎn)的棧
   LinkedStack<BinaryNode> stack=new LinkedStack<>();

   BinaryNode<T> currentNode =root;
   BinaryNode<T> prev=root;

    //需要從最低葉子節(jié)點(diǎn)開始輸出結(jié)果
   while (currentNode!=null||!stack.isEmpty()){
       //把左子樹加入棧中,直到左子樹最低處的葉子結(jié)點(diǎn)周蹭，終止條件是葉子節(jié)點(diǎn)的左子樹為null
       while (currentNode!=null){
           stack.push(currentNode);
           currentNode=currentNode.left;
       }

       //開始訪問當(dāng)前結(jié)點(diǎn)的父結(jié)點(diǎn)的右孩子
       if(!stack.isEmpty()){
           //獲取右孩子趋艘，先不彈出
           BinaryNode temp=stack.peek().right;
           //先判斷是否有右孩子或者右孩子是否已被訪問過
           if(temp==null||temp==prev){  //沒有右孩子||右孩子已被訪問過
               
               //如果沒有右孩子或者右孩子已被訪問,則彈出父結(jié)點(diǎn)并訪問
               currentNode=stack.pop();
               //當(dāng)前節(jié)點(diǎn)左右子樹為null則輸出，因?yàn)榇斯?jié)點(diǎn)為葉子節(jié)點(diǎn)或者已經(jīng)被訪問過了
               System.out.println(currentNode.data);
               //記錄已訪問過的結(jié)點(diǎn)
               prev=currentNode;
               //訪問過的節(jié)點(diǎn)置為null
               currentNode=null;
            }
            else {  //有右孩子,則開始遍歷右子樹               
               currentNode=temp;
            }
       }
   }

層續(xù)遍歷

public void levelOrder(BinaryNode root) {
     //存放需要遍歷的結(jié)點(diǎn),左結(jié)點(diǎn)一定優(yōu)先右節(jié)點(diǎn)遍歷
    
   LinkedQueue<BinaryNode> queue=new LinkedQueue<>();
   StringBuffer sb=new StringBuffer();

   while (root!=null){
       //記錄經(jīng)過的結(jié)點(diǎn)
       System.out.println(root.data);

       //先按層次遍歷結(jié)點(diǎn),左結(jié)點(diǎn)一定在右結(jié)點(diǎn)之前訪問
       if(root.left!=null){
           //孩子結(jié)點(diǎn)入隊(duì)
           queue.add(root.left);
       }
       if (root.right!=null){
           queue.add(root.right);
       }
       //訪問下一個(gè)結(jié)點(diǎn)
       root=queue.poll();
   }
}

利用中序遍歷和前序遍歷或/后序遍歷構(gòu)建二叉樹

前序遍歷和中序遍歷[3]

建樹思想：

1. 選取前序遍歷的第一個(gè)val構(gòu)建樹節(jié)點(diǎn)作二叉樹的根root，然后在中序遍歷中找到root.val值棚愤，返回此值在中序遍歷的索引位置，前序遍歷數(shù)組索引加一宛畦，因?yàn)槊恳粋€(gè)數(shù)值都能成為根；
2. 以中序遍歷返回的索引分割中序遍歷數(shù)組反肋，左子數(shù)組為左子樹斯够，右子數(shù)組為右子樹喧锦，遞歸放入到創(chuàng)建節(jié)點(diǎn)的函數(shù)中。
3. 返回的結(jié)果為每一個(gè)創(chuàng)建的根root燃少，即利用前序遍歷創(chuàng)建的每一個(gè)節(jié)點(diǎn)，中序遍歷只是用于分割左右子樹的作用碍遍。

public class CreateTreeByInOrderAndPreOrder {
    int[] inOrderResult ={4,2,5,1,6,3};
    int[] preOrderResult ={1,2,4,5,3,6};
    static int preIndex = 0;
    public TreeNode createTreeNode(int[] preOrder, int preStart, int preEnd) {
        if (preStart > preEnd){return null;}
        //為當(dāng)前數(shù)據(jù)創(chuàng)建一個(gè)新的樹節(jié)點(diǎn)
        TreeNode root = new TreeNode(preOrder[preIndex++]);
        if (preStart == preEnd){return root;}

        //在中序遍歷中找到當(dāng)前節(jié)點(diǎn)的位置索引
        int inOrderIndex = finIndexInInorder(root.val);
        root.left = createTreeNode(preOrder, preOrderStart + 1, inOrderIndex );
        root.right = createTreeNode(preOrder, inOrderIndex + 1, preOrderEnd);
        return root;
    }
    private int finIndexInInorder(int rootValue) {
        for (int i = 0; i < inOrderResult.length; i++) {
            if (rootValue == inOrderResult[i]) {
                return i;
            }
        }
        return -1;
    }
}

后序遍歷與中序遍歷

public class CreateTreeByPostOrderAndInOrder {
    int[] inOrderResult ={4,8,2,5,1,6,3,7};
    int[] postOrderResult = {8,4,5,2,6,7,3,1};

    int postOderIndex = inOrderResult.length -1;

    public TreeNode createTreeNode(int[] postOrder, int postStart, int postEnd) {
        if (postStart > postEnd){return null;}

        TreeNode root = new TreeNode(postOrder[postOrderIndex--]);
        if (postStart == postEnd){return root;}

        int inOrderIndex = finIndexInInorder(root.val);
        root.right = createTreeNode(postOrder,inOrderIndex, postEnd-1);
        root.left = createTreeNode(postOrder, postStart, inOrderIndex-1);

        return root;
    }

    private int finIndexInInorder(int rootValue) {
        for (int i = 0; i < inOrderResult.length; i++) {
            if (rootValue == inOrderResult[i]) {
                return i;
            }
        }
        return -1;
    }
}

參考文獻(xiàn)：

[1] java數(shù)據(jù)結(jié)構(gòu)與算法之樹基本概念及二叉樹（BinaryTree）的設(shè)計(jì)與實(shí)現(xiàn)
[2] 數(shù)據(jù)結(jié)構(gòu)（六）——二叉樹 前序怕敬、中序、后序东跪、層次遍歷及非遞歸實(shí)現(xiàn) 查找、統(tǒng)計(jì)個(gè)數(shù)丁恭、比較、求深度的遞歸實(shí)現(xiàn)
[3] 中序遍歷+先/后序遍歷創(chuàng)建二叉樹