二叉樹的數(shù)據(jù)結(jié)構(gòu)以及前序、中序、后續(xù)遍歷

import java.util.ArrayList;

class BinaryTreeNode {
    char value;
    BinaryTreeNode left;
    BinaryTreeNode right;
    BinaryTreeNode(char value){
        this.value=value;
    }
}

public class binaryTree {
    ArrayList<Character> list = new ArrayList<>();
    //前序遍歷

    
    //中序遍歷
    private ArrayList<Character> midOrderTraver(BinaryTreeNode t){
        if(t!=null) {
            midOrderTraver(t.left);
            list.add(t.value);
            midOrderTraver(t.right);
        }
        return list;
    }
    //后序遍歷
    private ArrayList<Character> postOrderTraver(BinaryTreeNode t){
        if(t!=null) {
            postOrderTraver(t.left);
            postOrderTraver(t.right);
            list.add(t.value);
        }
        return list;
    }

    public static void main(String[] args) {

        char[] a = {'a','b','c','d','e','f','g','h','i'};
        BinaryTreeNode[] b = new BinaryTreeNode[a.length];
        for (int i = 0;i < a.length; i++){
            b[i] = new BinaryTreeNode(a[i]);
        }

        b[0].left = b[1];
        b[0].right = b[2];
        b[1].left = b[3];
        b[1].right = b[4];
        b[2].left = b[5];
        b[2].right = b[6];
        b[4].left = b[7];
        b[4].right = b[8];

        System.out.println("========This is preOrderTraver========");
        for( char x:new binaryTree().preOrderTraver(b[0])){
            System.out.println(x);
        }

        System.out.println("========This is midOrderTraver========");
        for( char x:new binaryTree().midOrderTraver(b[0])){

            System.out.println(x);
        }

        System.out.println("========This is PostOrderTraver========");
        for( char x:new binaryTree().postOrderTraver(b[0])){

            System.out.println(x);
        }
    }
}

二叉樹的下一個(gè)節(jié)點(diǎn)

不管是找前序、中序還是后續(xù)遍歷的下一個(gè)節(jié)點(diǎn)，只要有了遍歷的集合，再查表一次就行了。

import java.util.ArrayList;

public class TreeLinkNode {
    int val;
    TreeLinkNode left = null;
    TreeLinkNode right = null;
    TreeLinkNode next = null;

    TreeLinkNode(int val) {
        this.val = val;
    }
    TreeLinkNode(){

    }
    ArrayList<TreeLinkNode> list = new ArrayList<>();
    private void midOrderTraver(TreeLinkNode t){
        if(t!=null) {
            midOrderTraver(t.left);
            list.add(t);
            midOrderTraver(t.right);
        }
    }
    public TreeLinkNode GetNext(TreeLinkNode pNode)
    {
        TreeLinkNode curNode = new TreeLinkNode();
        curNode = pNode;
        while (pNode.next!=null){
            pNode=pNode.next;
        }
        midOrderTraver(pNode);
        for(TreeLinkNode t:list){
            if (t==curNode){
                System.out.println(list.indexOf(t));
                if (list.indexOf(t)==list.size()-1) return null;
                return list.get(list.indexOf(t)+1);
            }
        }
        return pNode;
    }

    public static void main(String[] args) {
        char[] a = {'a','b','c','d','e','f','g','h','i'};
        TreeLinkNode[] b = new TreeLinkNode[a.length];
        for (int i = 0;i < a.length; i++){
            b[i] = new TreeLinkNode(a[i]);
        }

        b[0].left = b[1];
        b[0].right = b[2];
        b[1].left = b[3];
        b[1].right = b[4];
        b[1].next = b[0];
        b[2].left = b[5];
        b[2].right = b[6];
        b[2].next = b[0];
        b[3].next = b[1];
        b[4].left = b[7];
        b[4].right = b[8];
        b[4].next = b[1];
        b[5].next = b[2];
        b[6].next = b[2];
        b[7].next = b[4];
        b[8].next = b[4];
        System.out.println(new TreeLinkNode().GetNext(b[6]).val);
    }
}

二叉樹的寬度優(yōu)先遍歷

   private ArrayList<Character> BFS(BinaryTreeNode root){
        ArrayList<Character> lists=new ArrayList<Character>();
        if(root==null)
            return lists;
        Queue<BinaryTreeNode> queue=new LinkedList<BinaryTreeNode>();
       //把起始點(diǎn)放入對列
        queue.offer(root);
       //重復(fù)以下的步驟知道對列為空為止
        while (!queue.isEmpty()){
            // 從隊(duì)列中取出對列頭
           BinaryTreeNode node = queue.poll();
            //將其放入已訪問列表
           lists.add(node.value);
            //找到與隊(duì)列頭連接的點(diǎn)，將其放入queue中
           if(node.left!=null)
               queue.offer(node.left);
           if(node.right!=null)
               queue.offer(node.right);
        }
        return lists;
    }

按之字形順序打印二叉樹

偶數(shù)層從右往左遍歷，符合棧先進(jìn)后出的特點(diǎn)

雖然奇數(shù)層從左向右遍歷符合隊(duì)列的特點(diǎn)，但是偶數(shù)層是從右向左遍歷的插入的，不符合隊(duì)列特性。

所以需要兩個(gè)棧

令s1存奇數(shù)層，s2存偶數(shù)層。

ArrayList<ArrayList<Integer>> lists = new ArrayList<>();
    Stack<TreeNode> s1 = new Stack<>();//奇數(shù)層
    Stack<TreeNode> s2 = new Stack<>();//偶數(shù)層
    int layer = 1;
    if (pRoot==null)
        return lists;
    s1.push(pRoot);
    //每層不管是s1還是s2，只要不為空就繼續(xù)向下層遍歷
    while (!s1.empty() || !s2.empty()){
        //每一層都初始化一個(gè)列表用來存儲(chǔ)每列打印順序
        ArrayList<Integer> list = new ArrayList<>();
        //判斷當(dāng)前層是奇數(shù)層
        if (layer % 2 !=0){
            while(!s1.empty()){
                TreeNode t = s1.pop();
                list.add(t.val);
                //棧是先進(jìn)后出的，偶數(shù)層是從右向左遍歷，所以向偶數(shù)層添加節(jié)點(diǎn)是先推入左孩子，再推入右孩子
                //如果該節(jié)點(diǎn)有左孩子，將左孩子放入s2
                if(t.left != null) s2.push(t.left);
                //如果該節(jié)點(diǎn)有右孩子，將右孩子放入s2
                if(t.right != null) s2.push(t.right);
            }
        //當(dāng)前層是偶數(shù)層
        }else{
            while(!s2.empty()){
                //從右向左的順序，往奇數(shù)層添節(jié)點(diǎn)時(shí)不能使用隊(duì)列，要實(shí)現(xiàn)奇數(shù)層從左往右遍歷先把右孩子推進(jìn)去，再推左孩子
                TreeNode t = s2.pop();
                list.add(t.val);
                if(t.right != null) s1.push(t.right);
                if(t.left != null) s1.push(t.left);
            }
        }
        //把每層遍歷的結(jié)果放入總列表
        lists.add(list);
        對下一層進(jìn)行遍歷
        layer++;
    }
    return lists;

序列化二叉樹

public class Solution {
    int index = -1;   //計(jì)數(shù)變量
  //將前序遍歷結(jié)果序列化存到string中
    String Serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        if(root == null){
            sb.append("#,");
            //遞歸出口，遍歷如果碰到節(jié)點(diǎn)為空就返回#，
            return sb.toString();
        }
        //根
        sb.append(root.val + ",");
        //對左節(jié)點(diǎn)進(jìn)行遍歷
        sb.append(Serialize(root.left));
        //對右節(jié)點(diǎn)進(jìn)行遍歷
        sb.append(Serialize(root.right));
        return sb.toString();
  }
    
    // 反序列化不知道怎么做的
    TreeNode Deserialize(String str) {
        index++;
        //int len = str.length();
        //if(index >= len){
        //    return null;
       // }
        String[] strr = str.split(",");
        TreeNode node = null;
        if(!strr[index].equals("#")){
            //創(chuàng)建根節(jié)點(diǎn)
            node = new TreeNode(Integer.valueOf(strr[index]));
            //創(chuàng)建左孩子
            node.left = Deserialize(str);
            //創(chuàng)建右孩子
            node.right = Deserialize(str);
        }
        return node;
  }
}

二叉搜索樹的第k個(gè)節(jié)點(diǎn)

給定一棵二叉搜索樹，請找出其中的第k小的結(jié)點(diǎn)。例如， （5，3，7，2，4，6，8） 中，按結(jié)點(diǎn)數(shù)值大小順序第三小結(jié)點(diǎn)的值為4。

思路：二叉搜索樹的中序遍歷就是排好序的，第k小的節(jié)點(diǎn)在遍歷結(jié)果的（k-1)

public class Solution {
    ArrayList<TreeNode> list = new ArrayList<>();
    TreeNode KthNode(TreeNode pRoot, int k)
    {
        list = midOrderTraver(pRoot);
        if (k-1>=0&&(k-1)<list.size()) return list.get(k-1);
     
         return null;
     
    }
     ArrayList<TreeNode> midOrderTraver(TreeNode t){
        if(t!=null) {
            midOrderTraver(t.left);
            list.add(t);
            midOrderTraver(t.right);
        }
        return list;
    }

}

重建二叉樹

輸入某二叉樹的前序遍歷和中序遍歷的結(jié)果，請重建出該二叉樹。假設(shè)輸入的前序遍歷和中序遍歷的結(jié)果中都不含重復(fù)的數(shù)字。例如輸入前序遍歷序列{1,2,4,7,3,5,6,8}和中序遍歷序列{4,7,2,1,5,3,8,6}，則重建二叉樹并返回。

思路

前序遍歷的第一個(gè)節(jié)點(diǎn)肯定是根節(jié)點(diǎn)，中序遍歷根節(jié)點(diǎn)左邊的是左子樹，右邊的是右子樹 ，題干中說了不含重復(fù)數(shù)字就代表可以通過對中序遍歷的結(jié)果進(jìn)行遍歷以找出根節(jié)點(diǎn)所在的index。找出根節(jié)點(diǎn)后根節(jié)點(diǎn)的左右子樹 root.left root.right 就可以通過遞歸找出（root.left = reConstructBinaryTree()）返回的即是左子樹的根節(jié)點(diǎn)，也就是根節(jié)點(diǎn)的左節(jié)點(diǎn)。

代碼

public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        //數(shù)組長度為0
        if(pre.length == 0){
            return null;
        }

        int rootVal = pre[0];
        TreeNode root = new TreeNode(rootVal);
        //遞歸出口
        if(pre.length == 1){
            return root;
        }

        int rootIndex = 0;
        for (int i=0; i<in.length; i++){
            if (in[i] == rootVal){
                rootIndex = i;
                break;
            }
        }

        root.left = reConstructBinaryTree(Arrays.copyOfRange(pre,1,rootIndex+1),Arrays.copyOfRange(in,0,rootIndex));
        root.right = reConstructBinaryTree(Arrays.copyOfRange(pre,rootIndex+1,pre.length),Arrays.copyOfRange(in,rootIndex+1,in.length));

    return root;

    }

將有序數(shù)組轉(zhuǎn)換為二叉搜索樹

將一個(gè)按照升序排列的有序數(shù)組，轉(zhuǎn)換為一棵高度平衡二叉搜索樹。

本題中，一個(gè)高度平衡二叉樹是指一個(gè)二叉樹每個(gè)節(jié)點(diǎn) 的左右兩個(gè)子樹的高度差的絕對值不超過 1。

示例:

給定有序數(shù)組: [-10,-3,0,5,9],

一個(gè)可能的答案是答案不唯一：[0,-3,9,-10,null,5]，它可以表示下面這個(gè)高度平衡二叉搜索樹：

可以看出每次都是設(shè)置的是mid值
      0
     / \
   -3   9
   /   /
 -10  5

public TreeNode sortedArrayToBST(int[] nums) {
        // 左右等分建立左右子樹，中間節(jié)點(diǎn)作為子樹根節(jié)點(diǎn)，遞歸該過程
        return nums == null ? null : buildTree(nums, 0, nums.length - 1);
    }

    private TreeNode buildTree(int[] nums, int l, int r) {
        if (l > r) {
            return null; // 遞歸出口
        }
        int m = (l + r) / 2;
        TreeNode root = new TreeNode(nums[m]);
        root.left = buildTree(nums, l, m - 1);
        root.right = buildTree(nums, m + 1, r);
        return root;
    }