二叉樹序列化和反序列化的兩種方式-有解無憂

介紹

二叉樹的序列化和反序列化，有兩種方式：

第一種方式在將二叉樹序列化為陣列的時候，需要標記空指標為特殊符號，這樣在反序列化的時候，就可以根據這些符號和序列方式來確定一顆二叉樹，
第二種方式在序列化的時候，不需要標記特殊符號，這樣序列化出來的就是一個純陣列或者字串，但是這樣的陣列即使知道序列方式，也是無法反序列化出來的，必須使用中序+先序，或者中序+后續的兩個陣列，才能將其反序列化，

二叉樹的序列化
- 按層遍歷二叉樹輸出陣列
- S形遍歷二叉樹輸出陣列
- 先序遍歷二叉樹輸出陣列
- 中序遍歷二叉樹輸出陣列
- 后序遍歷二叉樹輸出陣列
- 先序遍歷二叉樹輸出陣列(特殊符號)
- 中序遍歷二叉樹輸出陣列(特殊符號)
- 后序遍歷二叉樹輸出陣列(特殊符號)
二叉樹的反序列化
- 將按層次遍歷的方式輸入的陣列構造成一個二叉樹
- 將按先序遍歷的方式輸入的陣列構造成一個二叉樹
- 將按中序遍歷的方式輸入的陣列構造成一個二叉樹
- 將按后序遍歷的方式輸入的陣列構造成一個二叉樹
- 將按照完全二叉樹輸入的陣列構造成一個完全二叉樹
- 根據先序遍歷序列和中序遍歷序列，構建唯一一棵確定的二叉樹
- 根據后序遍歷序列和中序遍歷序列，構建唯一一棵確定的二叉樹
二叉樹轉鏈表
- 全部轉左孩子
- 全部轉右孩子
本文原始碼
- Array2BinaryTreeImpl 和測驗案例
- BinaryTree2ArrayImpl 和測驗案例
- BinaryTree2LinkedList和測驗案例

二叉樹的序列化

按層遍歷二叉樹輸出陣列

設計思路
- 通過佇列的先進先出來構建父節點的彈出順序
- 通過雙指標的對比來判斷層級順序
主要代碼

public void Binary2ArrayLevel_print(BinaryTreeImpl root) {
    if (check(root)) {
        return;
    }
    Queue<BinaryTreeImpl> queue = new LinkedList<>();
    queue.offer(root);
    BinaryTreeImpl front = root;
    BinaryTreeImpl tail = root;
    while (!queue.isEmpty()) {
        BinaryTreeImpl binaryTree = queue.poll();
        System.out.print(binaryTree.value + " ");
        if (binaryTree.left != null) {
            queue.offer(binaryTree.left);
            tail = binaryTree.left;
        }
        if (binaryTree.right != null) {
            queue.offer(binaryTree.right);
            tail = binaryTree.right;
        }
        if (binaryTree == front) {
            front = tail;
            System.out.println();
        }
    }
}

注意事項
- where的判斷條件
- 子節點判空
- 輸出層級的位置

S形遍歷二叉樹輸出陣列

設計思路
- 利用雙堆疊的特點，來交替列印輸出的層級元素
主要代碼

public int[] Binary2ArrayS(BinaryTreeImpl root) {
    if (check(root)) {
        return new int[0];
    }
    List<Integer> list = new ArrayList<>();
    Stack<BinaryTreeImpl> stack1 = new Stack();
    Stack<BinaryTreeImpl> stack2 = new Stack();
    stack1.push(root);
    list.add(root.value);
    boolean rawflag = true;

    while (!stack1.empty() || !stack2.empty()) {
        while (!stack1.empty()) {
            BinaryTreeImpl node = stack1.pop();
            if (rawflag) {
                if (node.left != null) {
                    stack2.push(node.left);
                    list.add(node.left.value);
                }
                if (node.right != null) {
                    stack2.push(node.right);
                    list.add(node.right.value);
                }
            } else {
                if (node.right != null) {
                    stack2.push(node.right);
                    list.add(node.right.value);
                }
                if (node.left != null) {
                    stack2.push(node.left);
                    list.add(node.left.value);
                }
            }
        }
        rawflag = !rawflag;
        stack1 = stack2;
        stack2 = new Stack<>();
    }
    int[] binaryTrees = list.stream().mapToInt(Integer::intValue).toArray();
    return binaryTrees;
}

注意事項
- 標識位rawflag需要在每次層級關系結束的時候，反轉一次
- 層級關系結束的時候，雙堆疊需要交換一次

先序遍歷二叉樹輸出陣列

設計思路
- 先序遍歷的特點是，先跟節點，再左孩子，后右孩子
主要代碼

//先序遞回
public void PreOrder_recursion(BinaryTreeImpl root) {
    if (root == null) {
        return;
    }
    listPreOrder.add(root.value);
    if (root.left != null) {
        PreOrder_recursion(root.left);
    }
    if (root.right != null) {
        PreOrder_recursion(root.right);
    }
}

一直遍歷左孩子，再彈出右孩子

//先序非遞回
public void PreOrder_stack(BinaryTreeImpl root) {
    Stack<BinaryTreeImpl> stack = new Stack();
    while (root != null || !stack.empty()) {
        while (root != null) {
            stack.push(root);
            listPreOrder.add(root.value);
            root = root.left;
        }
        root = stack.pop().right;
    }
}

注意事項

中序遍歷二叉樹輸出陣列

設計思路
- 中序遍歷的特點是，先左孩子，再跟節點，最后右孩子
主要代碼

//中序遞回
private void InOrder_recursion(BinaryTreeImpl root) {
    if (root == null) {
        return;
    }
    InOrder_recursion(root.left);
    listInOrder.add(root.value);
    InOrder_recursion(root.right);
}

//中序非遞回
private void InOrder_stack(BinaryTreeImpl root) {
    Stack<BinaryTreeImpl> stack = new Stack<>();
    while (root != null || !stack.empty()) {
        while (root != null) {
            stack.push(root);
            root = root.left;
        }
        root = stack.pop();
        listInOrder.add(root.value);
        root = root.right;
    }
}

注意事項
- 中序非遞回中需要注意list加入節點的時機

后序遍歷二叉樹輸出陣列

設計思路
- 后序遍歷的特點是，先左孩子，再右孩子，最后跟節點
主要代碼

//后續遍歷 遞回
private void PostOrder_recursion(BinaryTreeImpl root) {
    if (check(root)) {
        return;
    }
    PostOrder_recursion(root.left);
    PostOrder_recursion(root.right);
    listPostOrder.add(root.value);
}

后續遍歷雙堆疊法在遍歷的時候，看似stack1是跟節點，左孩子，右孩子的順序入堆疊，實則在匯出至stack2的時候，是右孩子、左孩子、跟節點的順序，

//后續遍歷 雙堆疊法
private void PostOrder_stack2(BinaryTreeImpl root) {
    Stack<BinaryTreeImpl> stack1 = new Stack<>();
    Stack<BinaryTreeImpl> stack2 = new Stack<>();
    stack1.push(root);
    while (!stack1.empty()) {
        root = stack1.pop();
        stack2.push(root);
        if (root.left != null) {
            stack1.push(root.left);
        }
        if (root.right != null) {
            stack1.push(root.right);
        }
    }
    while (!stack2.empty()) {
        listPostOrder.add(stack2.pop().value);
    }
}

//后續遍歷 單堆疊法
public void PostOrder_stack1(BinaryTreeImpl h) {
    Stack<BinaryTreeImpl> stack = new Stack<>();
    stack.push(h);
    BinaryTreeImpl c = null;
    while (!stack.isEmpty()) {
        c = stack.peek();
        if (c.left != null && h != c.left && h != c.right) {
            stack.push(c.left);
        } else if (c.right != null && h != c.right) {
            stack.push(c.right);
        } else {
            listPostOrder.add(stack.pop().value);
            h = c;
        }
    }
}

注意事項
- 單堆疊法的h是上一個節點的位置，用于標記自身是否被重復入堆疊，

先序遍歷二叉樹輸出陣列(特殊符號)

設計思路
- 遞回
主要代碼

public int[] Binary2ArrayPreOrder_Symbol(BinaryTreeImpl root) {
        if (check(root)) {
            return new int[]{};
        }
        listPreOrder_Symbol = new ArrayList<>();
        PreOrder_Symbol(root);
        return listPreOrder_Symbol.stream().mapToInt(x -> x).toArray();
    }

    private void PreOrder_Symbol(BinaryTreeImpl root) {
        if (root == null) {
            listPreOrder_Symbol.add(Symbol);
            return;
        }
        listPreOrder_Symbol.add(root.value);
        PreOrder_Symbol(root.left);
        PreOrder_Symbol(root.right);
    }

中序遍歷二叉樹輸出陣列(特殊符號)

設計思路
- 遞回
主要代碼

public int[] Binary2ArrayInOrder_Symbol(BinaryTreeImpl root) {
    if(check(root)){
        return new int[]{};
    }
    listInOrder_Symbol = new ArrayList<>();
    InOrder_Symbol(root);
    return  listInOrder_Symbol.stream().mapToInt(Integer::intValue).toArray();
}

private void InOrder_Symbol(BinaryTreeImpl root){
    if(root == null){
        listInOrder_Symbol.add(Symbol);
        return;
    }
    InOrder_Symbol(root.left);
    listInOrder_Symbol.add(root.value);
    InOrder_Symbol(root.right);
}

后序遍歷二叉樹輸出陣列(特殊符號)

設計思路
- 遞回
主要代碼

public int[] Binary2ArrayPostOrder_Symbol(BinaryTreeImpl root) {
        if(check(root)){
            return new int[]{};
        }
        listPostOrder_Symbol = new ArrayList<>();
        PostOrder_Symbol(root);
        return listPostOrder_Symbol.stream().mapToInt(Integer::intValue).toArray();
    }

    private void PostOrder_Symbol(BinaryTreeImpl root){
        if(root==null){
            listPostOrder_Symbol.add(Symbol);
            return;
        }
        PostOrder_Symbol(root.left);
        PostOrder_Symbol(root.right);
        listPostOrder_Symbol.add(root.value);
    }

二叉樹的反序列化

將按層次遍歷的方式輸入的陣列構造成一個二叉樹

設計思路
- 通過佇列輔助，實作節點順序
主要代碼

//1、將按層次遍歷的方式輸入的陣列  構造成一個二叉樹(寫法一：非遞回，堆疊)
public BinaryTreeImpl createBinaryTreeLevel(int[] array) {
    if (!check(array)) {
        return null;
    }
    BinaryTreeImpl root = null;
    //借助佇列實作
    Queue<BinaryTreeImpl> queue = new LinkedList();
    int depth = 0;
    root = new BinaryTreeImpl(array[depth]);
    queue.offer(root);
    while (!queue.isEmpty()) {
        BinaryTreeImpl binaryTree = queue.poll();
        //left child exist
        if (++depth < array.length && array[depth] != -1) {
            binaryTree.left = new BinaryTreeImpl(array[depth]);
            queue.offer(binaryTree.left);
        }
        //right child exist
        if (++depth < array.length && array[depth] != -1) {
            binaryTree.right = new BinaryTreeImpl(array[depth]);
            queue.offer(binaryTree.right);
        }
    }
    return root;
}

使用遞回實作，但是需要注意，此處的count是必須是全域變數，

//1、將按層次遍歷的方式輸入的陣列  構造成一個二叉樹(寫法二:遞回)
private volatile int count;
public BinaryTreeImpl createBinaryTreeLevel(BinaryTreeImpl root, int[] tree_num, int i) {
    if (i < tree_num.length) {
        if (tree_num[i] == -1) {
            return null;
        } else {
            //new root's lchild and rchild
            BinaryTreeImpl lchild = new BinaryTreeImpl();
            BinaryTreeImpl rchild = new BinaryTreeImpl();
            //preOrder
            root.value = tree_num[i];
            root.left = createBinaryTreeLevel(lchild, tree_num, ++count);
            root.right = createBinaryTreeLevel(rchild, tree_num, ++count);
        }
    }
    return root;
}

注意事項
- count是必須是全域變數，

將按先序遍歷的方式輸入的陣列構造成一個二叉樹

設計思路
- 通過佇列記錄陣列順序
- 先序構造二叉樹
主要代碼

public BinaryTreeImpl createPreOrder(int[] array) {
    Queue<BinaryTreeImpl> queue = new LinkedList<>();
    if (!check(array)) {
        return null;
    }
    for (int value : array) {
        queue.add(new BinaryTreeImpl(value));
    }
    BinaryTreeImpl root = PreOrder(queue);
    return root;
}

private BinaryTreeImpl PreOrder(Queue<BinaryTreeImpl> queue) {
    if (queue == null) {
        return null;
    }
    BinaryTreeImpl root = queue.poll();
    if (root.value == Symbol) {
        return null;
    }
    root.left = PreOrder(queue);
    root.right = PreOrder(queue);
    return root;
}

注意事項

將按中序遍歷的方式輸入的陣列構造成一個二叉樹

注意事項
- 中序無法還原二叉樹，因為無法找到跟節點

將按后序遍歷的方式輸入的陣列構造成一個二叉樹

設計思路
- 通過佇列記錄陣列順序
- 因為佇列的最后一位是跟節點，繼續后續生成二叉樹，
- 注意佇列的入隊順序，因此先右孩子，再左孩子，
主要代碼

public BinaryTreeImpl createPostOrder(int[] array) {
    if (!check(array)) {
        return null;
    }
    Deque<BinaryTreeImpl> queue = new LinkedList<>();
    for (int value : array) {
        queue.add(new BinaryTreeImpl(value));
    }
    BinaryTreeImpl root = PostOrder(queue);
    return root;
}

private BinaryTreeImpl PostOrder(Deque<BinaryTreeImpl> queue) {
    if (queue == null) {
        return null;
    }
    BinaryTreeImpl root = queue.pollLast();
    if (root.value == Symbol) {
        return null;
    }
    root.right = PostOrder(queue);
    root.left = PostOrder(queue);
    return root;
}

注意事項

將按照完全二叉樹輸入的陣列構造成一個完全二叉樹

設計思路
- 第一步：判斷此陣列是否為完全二叉樹，即陣列長度是否為 2的n次方-1
- 第二步：回圈構建節點
- 第三部：構建節點關系f(i)=f(2*i+1)
主要代碼

public BinaryTreeImpl createfulltree(int[] array) {
    if (array == null || array.length == 0) {
        return null;
    }
    int length = array.length;
    int base = 2;
    //判斷一個數是否為 2的n次方-1
    int indexlength = String.valueOf(Math.log(length + 1) / Math.log(base)).length();
    //double型 整數 數字轉字串長度，長度為3
    if (indexlength > 3) {
        return null;
    }
    List<BinaryTreeImpl> btlist = new ArrayList<>();
    for (int i = 0; i < length; i++) {
        btlist.add(new BinaryTreeImpl(array[i]));
    }
    //注意此處的i < (length - 1) / 2，而不是i < (length + 1) / 2
    for (int i = 0; i < (length - 1) / 2; i++) {
        btlist.get(i).left = btlist.get(2 * i + 1);
        btlist.get(i).right = btlist.get(2 * i + 2);
    }
    return btlist.get(0);
}

注意事項

根據前序遍歷序列和中序遍歷序列，構建唯一一棵確定的二叉樹

設計思路
- 先序遍歷的第一個節點是中序遍歷的中間節點
- 通過回圈判斷中間節點，將中序分成兩部分，進行遞回
主要代碼

public BinaryTreeImpl createTreePre_InOrder(int[] PreOrderarray, int preStart, int preEnd, int[] InOrderarray, int inStart, int inEnd) {
    if (preStart <= preEnd) {
        //此處是PreOrderarray[preStart]，不是PreOrderarray[0]
        int value = PreOrderarray[preStart];
        BinaryTreeImpl node = new BinaryTreeImpl(value);
        int index = 0;
        //回圈不是從0 到 InOrderarray.length
        for (int i = inStart; i <= inEnd; i++) {
            if (value == InOrderarray[i]) {
                index = i;
                break;
            }
        }
        //此處length = index - inStart，而不是length = index - preStart
        int length = index - inStart;
        node.left = createTreePre_InOrder(PreOrderarray, preStart + 1, preStart + length,
                InOrderarray, inStart, index - 1);
        node.right = createTreePre_InOrder(PreOrderarray, preStart + length + 1, preEnd,
                InOrderarray, index + 1, inEnd);
        return node;
    }
    return null;
}

注意事項

根據后序遍歷序列和中序遍歷序列，構建唯一一棵確定的二叉樹

設計思路
- 后序遍歷的最后一個節點是中序遍歷的中間節點
- 通過回圈判斷中間節點，將中序分成兩部分，進行遞回
主要代碼

public BinaryTreeImpl createTreePost_InOrder(int[] PostOrderarray, int postStart, int postEnd, int[] InOrderarray, int inStart, int inEnd) {
        if (postStart <= postEnd) {
            //此處是PreOrderarray[preStart]，不是PreOrderarray[0]
            int value = PostOrderarray[postEnd];
            BinaryTreeImpl node = new BinaryTreeImpl(value);
            int index = 0;
            //回圈不是從0 到 InOrderarray.length
            for (int i = inStart; i <= inEnd; i++) {
                if (value == InOrderarray[i]) {
                    index = i;
                    break;
                }
            }
            //此處length = index - inStart，而不是length = index - preStart
            int length = index - inStart;
            node.left = createTreePost_InOrder(PostOrderarray, postStart, postStart + length - 1,
                    InOrderarray, inStart, index - 1);
            node.right = createTreePost_InOrder(PostOrderarray, postStart + length, postEnd - 1,
                    InOrderarray, index + 1, inEnd);
            return node;
        }
        return null;
    }

注意事項

二叉樹轉鏈表

右孩子轉左孩子的左孩子

設計思路
- 取出節點的左右孩子，右孩子置空
- 回圈左孩子（之前的）至葉子節點，
- 將右孩子（之前的）復制給該葉子節點的左孩子
主要代碼

//將右孩子并至左孩子葉子結點，形成鏈表
private BinaryTreeImpl BinaryTree2LinkedList_Left(BinaryTreeImpl binaryTree) {
    if (binaryTree == null) {
        return null;
    }
    /**
     * 取出節點的左右孩子，右孩子置空
     * 回圈左孩子（之前的）至葉子節點，
     * 將右孩子（之前的）復制給該葉子節點的左孩子
     */
    BinaryTree2LinkedList_Left(binaryTree.left);
    BinaryTree2LinkedList_Left(binaryTree.right);
    BinaryTreeImpl nodeleft = binaryTree.left;
    BinaryTreeImpl noderight = binaryTree.right;
    binaryTree.right = null;
    BinaryTreeImpl p = binaryTree;
    //注意此處的寫法是p.left 而不是p，因為存在判空問題
    while (p.left != null) {
        p = p.left;
    }
    p.left = noderight;
    return binaryTree;
}

注意事項

左孩子轉右孩子的右孩子

設計思路
- 取出節點的左右孩子，直接把左孩子復制給跟節點的右孩子，左孩子置空
- 回圈右孩子（之前的左孩子）至葉子節點，
- 將右孩子（之前的）復制給該葉子節點的右孩子
主要代碼

private BinaryTreeImpl BinaryTree2LinkedList_Right(BinaryTreeImpl binaryTree) {
    if (binaryTree == null) {
        return null;
    }
    /**
     * 取出節點的左右孩子，直接把左孩子復制給跟節點的右孩子，左孩子置空
     * 回圈右孩子（之前的左孩子）至葉子節點，
     * 將右孩子（之前的）復制給該葉子節點的右孩子
     */
    BinaryTree2LinkedList_Right(binaryTree.left);
    BinaryTree2LinkedList_Right(binaryTree.right);
    BinaryTreeImpl nodeleft = binaryTree.left;
    BinaryTreeImpl noderight = binaryTree.right;
    binaryTree.left = null;
    binaryTree.right = nodeleft;
    BinaryTreeImpl p = binaryTree;
    //注意此處的寫法是p.left 而不是p，因為存在判空問題
    while (p.right != null) {
        p = p.right;
    }
    p.right = noderight;
    return binaryTree;
}

注意事項

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/209504.html

標籤：其他

上一篇：利用遞回實作山脈效果，填充山脈以及山脈顏色漸變

下一篇：第九屆藍橋杯決賽真題：最大乘積

二叉樹序列化和反序列化的兩種方式

介紹

目錄

二叉樹的序列化

二叉樹的反序列化

二叉樹轉鏈表