鏈表實作

先創建一個節點類

public class TreeNode {
    int value;//資料
    TreeNode left;//指向左子樹
    TreeNode right;//指向右子樹
    public TreeNode(){}
    public TreeNode(int value){
        this.value=value;
        left=null;
        right=null;
    }
}

利用陣列建立二叉樹

利用遞回一一將陣列中的數全部存盤到二叉樹中建立二叉樹

   public TreeNode create(char[] arr,int index){
        if(index>=arr.length){
            return null;
        }else{
            TreeNode tmpNode=new TreeNode((int)(arr[index]));
            tmpNode.left=create(arr,2*index);
            tmpNode.right=create(arr,2*index+1);
            return tmpNode;
        }
    }

整體代碼實作

```java
public class BinaryTree {
    public TreeNode root;
    public TreeNode(){}
    public BinaryTree(char[] ch,int index){
        root=create(ch,index);
    }
    //將陣串列示法轉換為鏈表表示法
    public TreeNode create(char[] arr,int index){
        if(index>=arr.length){
            return null;
        }else{
            TreeNode tmpNode=new TreeNode((int)(arr[index]));
            tmpNode.left=create(arr,2*index);
            tmpNode.right=create(arr,2*index+1);
            return tmpNode;
        }
    }

直接添加元素，建立二叉排序樹

    public void add(int data){
        TreeNode newNode=new TreeNode(data);
        //建立樹根
        if(root==null){
            root=newNode;
            return;
        }
        TreeNode cur=root;
        while(true){
            if(newNode.value<cur.value){
                if(cur.left==null){
                    cur.left=newNode;
                    return;
                }else{
                    cur=cur.left;
                }
            }else{
                if(cur.right==null){
                    cur.right=newNode;
                    return;
                }else{
                    cur=cur.right;
                }
            }
        }
    }

二叉樹的搜索

可以看到二叉樹的搜索是建立在二叉排序樹的基礎上

    //查找該二叉樹上是否含有該元素
    public boolean findTreeNode(TreeNode root,int value){
        if(root==null){
            return false;
        }else{
            if(root.value==value){
                return true;
            }else{
                if(value<root.value){
                    count++;
                    return findTreeNode(root.left,value);
                }else{
                    count++;
                    return findTreeNode(root.right,value);
                }
            }
        }
    }

二叉運算樹

先創建一個節點類

public class TreeNode {
    int value;
    TreeNode left;
    TreeNode right;
    public TreeNode(){}
    public TreeNode(int data){
        this.value=data;
        left=null;
        right=null;
    }
}

接下來實作二叉運算樹

public class BinaryTree {
    public TreeNode root;
    public BinaryTree(char[] ch,int index){
        root=create(ch,index);
    }
    //添加元素
    public void add(int data){
        TreeNode newNode=new TreeNode(data);
        if(root==null){
            root=newNode;
            return;
        }
        TreeNode cur=root;
        while(true){
            if(newNode.value<cur.value){
                if(cur.left==null){
                    cur.left=newNode;
                    return;
                }else {
                    cur=cur.left;
                }
            }else{
                if(cur.right==null){
                    cur.right=newNode;
                    return;
                }else{
                    cur=cur.right;
                }
            }
        }
    }
    //將陣串列示法轉換為鏈表表示法
    public TreeNode create(char[] arr,int index){
        if(index>=arr.length){
            return null;
        }else{
            TreeNode tmpNode=new TreeNode((int)(arr[index]));
            tmpNode.left=create(arr,2*index);
            tmpNode.right=create(arr,2*index+1);
            return tmpNode;
        }
    }
    //判斷運算式如何運算的方法宣告
    public int condition(char ch,int n1,int n2){
        switch(ch){
            case '+': return n1+n2;
            case '-': return n1-n2;
            case '*': return n1*n2;
            case '/': return n1/n2;
            case '%': return n1%n2;
            default: return -1;
        }
    }
    //計算二叉運算樹的值
    public int answer(TreeNode root){
        int first=0;
        int second=0;
        if(root.left==null&&root.right==null){
            return Character.getNumericValue((char)root.value);
        }else{
            first=answer(root.left);
            second=answer(root.right);
            return condition((char)root.value,first,second);
        }
    }
    //中序表示法
    public void inOrder(TreeNode root){
        if(root!=null){
            inOrder(root.left);
            System.out.print((char)root.value+" ");
            inOrder(root.right);
        }
    }
    //后序表示法
    public void postOrder(TreeNode root){
        if(root!=null){
            postOrder(root.left);
            postOrder(root.right);
            System.out.print((char)root.value+" ");
        }
    }
    //前序表示法
    public void preOrder(TreeNode root){
        if(root!=null){
            System.out.print((char)root.value+" ");
            preOrder(root.left);
            preOrder(root.right);
        }
    }
}

前序遍歷遞回實作

//前序遍歷
    public void preOrder1(TreeNode root){
        if(root!=null){
            System.out.print(root.value+" ");
            preOrder1(root.left);//遍歷左子樹
            preOrder1(root.right);//遍歷右子樹
        }
    }

前序遍歷非遞回實作

解法一

利用堆疊的性質

 //前序遍歷非遞回1
    public void preOrder2(TreeNode cur){

        Stack<TreeNode> stack=new Stack<>();
        while(cur!=null||!stack.isEmpty()){
            while(cur!=null){
                stack.add(cur);
                System.out.print(cur.value+" ");
                cur=cur.left;
            }
            cur=stack.pop();
            cur=cur.right;
        }
    }

解法二

將元素按照前序遍歷的順序壓入堆疊中，再依次彈出即可

  //前序遍歷非遞回2
    public void preOrder3(TreeNode cur){
        Stack<TreeNode> stack=new Stack<>();
        stack.add(cur);
        while(!stack.isEmpty()){
            cur=stack.pop();
            System.out.print(cur.value+" ");
            if(cur.right!=null)
                stack.add(cur.right);
            if(cur.left!=null)
                stack.add(cur.left);
        }
    }

中序遍歷遞回實作

 //中序遍歷
    public void inOrder1(TreeNode root){
        if(root!=null){
            inOrder1(root.left);//處理左子樹
            System.out.print(root.value+" ");
            inOrder1(root.right);//處理右子樹
        }
    }

中序遍歷非遞回實作

和前序遍歷的非遞回實作一樣，只不過是交換了列印順序，

    //中序遍歷非遞回
    public void inOrder2(TreeNode cur){
        Stack<TreeNode> stack=new Stack<>();
        while(cur!=null||!stack.isEmpty()){
            while(cur!=null){
                stack.add(cur);
                cur=cur.left;
            }
            cur=stack.pop();
            System.out.print(cur.value+" ");
            cur=cur.right;
        }
    }

后序遍歷遞回實作

 //后序遍歷
    public void postOrder1(TreeNode root){
        if(root!=null){
            postOrder1(root.left);//處理左子樹
            postOrder1(root.right);//處理右子樹
            System.out.print(root.value+" ");
        }
    }

后序遍歷非遞回實作

后序遍歷較為復雜，需要用到堆疊的性質，且用 cur 來判斷列印樹葉，用 pre 來記錄左或右節點來判斷是否列印父節點

    public void postOrder2(TreeNode cur){
        if(cur==null)
            return;

        Stack<TreeNode> stack=new Stack<>();
        TreeNode pre=null;
        stack.add(cur);
        while(!stack.isEmpty()){
            cur=stack.peek();
            if((cur.left==null&&cur.right==null)||(pre!=null&&(pre==cur.left||pre==cur.right))){ 
                System.out.print(cur.value+" ");
                stack.pop();
                pre=cur;
            }else{
                if(cur.right!=null)
                    stack.add(cur.right);
                if(cur.left!=null)
                    stack.add(cur.left);
            }
        }
    }

層序遍歷遞回實作

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        helper(root, 0, result);
        return result;
    }

    public void helper(TreeNode root, int level, List<List<Integer>> lists) {
        if (root == null) {
            return;
        }
        if (lists.size() < level + 1) {
            lists.add(new ArrayList<Integer>());
        }
        lists.get(level).add(root.val);
        helper(root.left, level + 1, lists);
        helper(root.right, level + 1, lists);
    }
}

層序遍歷非遞回實作

利用佇列先進先出的性質即可，

    //層序遍歷非遞回
    public void levelOrder(TreeNode cur){
        LinkedList<TreeNode> queue=new LinkedList<>();
        queue.add(cur);
        while(!queue.isEmpty()){
            cur=queue.pop();
            System.out.print(cur.value+" ");
            if(cur.left!=null)
                queue.add(cur.left);
            if(cur.right!=null)
                queue.add(cur.right);
        }
    }

線索化二叉樹

學過鏈表的讀者肯定存在雙向鏈表的，也就是節點相連兩個節點之間相互指引，那么二叉樹是否也可以通過特定的遍歷方式變成特殊的“雙向鏈表”呢？
答案是肯定的，

我們選定一種遍歷方式時，遍歷到節點A時，所遍歷到的前一個元素叫位元組點A的前驅元素，遍歷節點A過后，所遍歷到的下一個元素叫節點A的后繼節點，

中序遍歷線索化二叉樹及其遍歷

先定義一個結點類

public class TreeNode {
    int value;
    TreeNode left;
    TreeNode right;
    boolean lef=false;
    boolean rig=false;
    public TreeNode(){}
    public TreeNode(int data){
        this.value=data;
        left=null;
        right=null;
    }
}

實作中序線索化二叉樹

    //中序線索化二叉樹
    public void inThreadOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        //處理左子樹
        inThreadOrder(root.left);
        if (root.left == null) {
            root.left = pre;
            root.lef = true;
        }
        //前一個節點的后繼結點指向當前節點
        if (pre != null && pre.right == null) {
            pre.right = root;
            pre.rig = true;
        }
        pre = root;
        inThreadOrder(root.right);
    }

從后繼節點開始遍歷

    //中序遍歷線索二叉樹，按照后繼方式遍歷
    public void inOrderBlack() {
        TreeNode cur = root;
        while (cur != null && !cur.lef) {
            cur = cur.left;
        }
        while (cur != null) {
            System.out.print(cur.value + " ");
            if (cur.rig) {
                cur = cur.right;
            } else {
                cur = cur.right;
                while (cur != null && !cur.lef)
                    cur = cur.left;
            }
        }
    }

從前驅結點開始遍歷

    //中序遍歷線索二叉樹，按照前驅方式遍歷
    public void inOrderBefore() {
        TreeNode cur = root;
        while (cur.right != null && !cur.rig)
            cur = cur.right;
        while (cur != null) {
            System.out.print(cur.value + " ");
            if (cur.lef) {
                cur = cur.left;
            } else {
                cur = cur.left;
                while (cur.right != null && !cur.rig)
                    cur = cur.right;
            }
        }
    }

先定義一個節點類

public class TreeNode {
    int value;
    TreeNode left;
    TreeNode right;
    boolean lef=false;
    boolean rig=false;
    public TreeNode(){}
    public TreeNode(int data){
        this.value=data;
        left=null;
        right=null;
    }
}

前序線索化二叉樹

    //前序遍歷線索化二叉樹
    public void preOrderBinaryTrree(TreeNode root) {
        if (root == null)
            return;
        //左指標為空，將左指標指向前驅節點
        if (root.left == null) {
            root.left = pre;
            root.lef = true;
        }
        //將前一個節點的后繼節點指向當前節點
        if (pre != null && pre.right == null) {
            pre.right = root;
            root.rig = true;
        }

        pre = root;

        if (!root.lef)
            preOrderBinaryTrree(root.left);
        if (!root.rig)
            preOrderBinaryTrree(root.right);
    }

遍歷前序線索化二叉樹

 //前序遍歷線索二叉樹
    public void preOrderblack() {
        TreeNode cur = root;
        while (cur != null) {
            while (!cur.lef) {
                System.out.println(cur.value + " ");
                cur = cur.left;
            }
            System.out.println(cur.value + " ");
            cur = cur.right;
        }
    }

后序線索化二叉樹

后序線索化二叉樹的節點類

后序線索化二叉樹創建的節點類，與前面有所不同，需要一個parent記錄父節點

public class TreeNode {
    int value;
    TreeNode left;
    TreeNode right;
    TreeNode parent;
    boolean lef=false;
    boolean rig=false;
    public TreeNode(){}
    public TreeNode(int data){
        this.value=data;
        left=null;
        right=null;
    }
}

實作后序線索化二叉樹

    //后序遍歷線索化二叉樹
    public void postThreadOrder(TreeNode root) {
        if (root == null)
            return;
        //處理左子樹
        postThreadOrder(root.left);
        //處理右子樹
        postThreadOrder(root.right);

        if (root.left == null) {
            root.left = pre;
            root.lef = true;
        }
        if (pre != null && pre.right == null) {
            pre.right = root;
            pre.rig = true;
        }
        pre = root;
    }

遍歷后序線索化二叉樹

    //遍歷后序遍歷線索化的二叉樹
    public void postOrderBinaryTree() {
        pre = null;
        TreeNode cur = root;
        while (cur != null && !cur.lef)
            cur = cur.left;

        while (cur != null) {
            if (cur.lef) {
                System.out.println(cur.value + " ");
                pre = cur;
                cur = cur.right;
            } else {
                if (cur.right == pre) {

                    System.out.println(cur.value + " ");

                    if(cur==root)
                        return;

                    pre=cur;
                    cur=cur.parent;
                }else{
                    if(cur==root&&cur.right==null)
                        return;

                        cur=cur.right;
                        while(cur!=null&&!cur.lef)
                            cur=cur.left;
                }
            }
        }
    }

陣列實作

通陣列的下標一樣，可以將二叉樹的各節點下標化

添加元素,利用陣列建立二叉搜索樹

可以發現規律，左子樹索引值為父節點索引值2+1
右子樹索引值為父節點索引值2+2
故有：

        //添加元素
        public void add(){
            int level=1;
            for(int i=0;i<data.length;i++){
                for(level=1;btree[level]!=0; ){
                    if(data[i]<btree[level])
                        level=level*2;
                    else
                        level=level*2+1;
                }
                btree[level]=data[i];
            }
        }

遍歷陣列實作的二叉樹

因為陣列是連續存盤的，所以直接列印就行，

 //遍歷二叉樹
        public void ergodic(){
            System.out.println("二叉樹的內容");
            for(int i=1;i<btree.length;i++)
                System.out.print(btree[i]+" ");
            System.out.println();
        }

整體代碼實作

public class BinaryTreeByArray {
        int[] data;
        int[] btree=new int[300];
        public BinaryTreeByArray(int[] arr){
            data=arr;
        }
        //添加元素
        public void add(){
            int level=1;
            for(int i=0;i<data.length;i++){
                for(level=1;btree[level]!=0; ){
                    if(data[i]<btree[level])
                        level=level*2;
                    else
                        level=level*2+1;
                }
                btree[level]=data[i];
            }
        }
        //遍歷二叉樹
        public void ergodic(){
            System.out.println("二叉樹的內容");
            for(int i=1;i<btree.length;i++)
                System.out.print(btree[i]+" ");
            System.out.println();
        }
}