一、前言：

? 這是懷化學院的：Java數據結構中的一道難度偏難(偏難理解)的一道編程題(此方法為博主自己研究，問題基本解決，若有bug歡迎下方評論提出意見，我會第一時間改進代碼，謝謝！) 后面其他編程題只要我寫完，并成功實現，會陸續更新，記得三連哈哈! 所有答案供參考，不是標準答案，是博主自己研究的寫法。(這一個題書上也有現成類似的代碼，重要的是理解它的算法原理!)

二、題目要求如下：

(第 12 題) 鏈式二叉樹的創建及遍歷(難度系數100)

鏈式二叉樹的創建及遍歷
描述：
樹的遍歷有先序遍歷、中序遍歷和后序遍歷。先序遍歷的操作定義是先訪問根結點，然后訪問左子樹，最后訪問右子樹。中序遍歷的操作定義是先訪問左子樹，然后訪問根，最后訪問右子樹。后序遍歷的操作定義是先訪問左子樹，然后訪問右子樹，最后訪問根。對于采用鏈式存儲結構的二叉樹操作中，創建二叉樹通常采用先序次序方式輸入二叉樹中的結點的值，空格表示空樹。對于如下的二叉樹，我們可以通過如下輸入“AE-F--H--”得到（ ‘-’表示空子樹）。

試根據輸入創建對應的鏈式二叉樹，并輸入其先序、中序和后序遍歷結果。
輸入：
輸入第一行為一個自然數n，表示用例個數
接下來為n行字符串，每行用先序方式輸入的要求創建的二叉樹結點，’-’表示前一結點的子樹為空子樹。
輸出：
對每個測試用例，分別用三行依次輸出其先序、中序和后序遍歷結果。
樣例輸入：
1
abdh---e-i--cf-j--gk---
樣例輸出：
abdheicfjgk
hdbeiafjckg
hdiebjfkgca

三、代碼實現：?(代碼的做題原理全部在代碼注釋中，若還有疑問也可以翻書關于二叉樹的鏈式存儲結構以及二叉樹的遍歷以及遞歸實現的內容)?

<1>因為學校的提交測試的網站：不能有自己創建的包的聲明，不能有代碼注釋以及要把所有的操作放在同一個類中等等......,所以我首先放一個干凈的代碼實現：(此題提交成功！)

import java.util.Scanner;public class Main {private static class Node{char data;Node lChild;Node rChild;public Node(char data){this.data=data;}}private static int num=0;public static Node setNode(Node node,String point){if(num<point.length()){char c =point.charAt(num++);if (c != '-') {node= new Node(c);node.lChild= setNode(node.lChild,point);node.rChild= setNode(node.rChild,point);}else {node=null;}}return node;}private static Node root=null;public static void main(String[] args) {Scanner sc =new Scanner(System.in);int n = sc.nextInt();while (n>0){String point=sc.next();root = setNode(root,point);preOrder();inOrder();postOrder();num=0; n--;}}public static void preOrder(){preOrder(root);System.out.println();}public static void preOrder(Node node){if(node!=null){System.out.print(node.data);preOrder(node.lChild);preOrder(node.rChild);}}public static void inOrder(){inOrder(root);System.out.println();}public static void inOrder(Node node){if(node!=null){inOrder(node.lChild);System.out.print(node.data);inOrder(node.rChild);}}public static void postOrder(){postOrder(root);System.out.println();}public static void postOrder(Node node){if(node!=null){postOrder(node.lChild);postOrder(node.rChild);System.out.print(node.data);}}
}

(1)全部放在一個類中去實現題目的所有要求。(其中注意創建了一個結點內部類)?

import java.util.Scanner;public class Main04 {//靜態結點內部類(不這樣的話主方法里用不了)private static class Node{char data;    //當前結點的存放的數據Node lChild;  //左孩子結點Node rChild;  //右孩子結點public Node(char data){this.data=data;}}private static int num=0;//要設為靜態方法，不然主方法無法用//此方法是按照先序次序方式創建二叉樹public static Node setNode(Node node,String point){//從下標0開始依次添加結點if(num<point.length()){char c =point.charAt(num++);  //注意這里每賦值完一個會往后移if (c != '-') {node= new Node(c);  //這里給每個創建的新結點只要不是空結點就賦值//先左結點，再創建右結點node.lChild= setNode(node.lChild,point);node.rChild= setNode(node.rChild,point);}else {node=null;}}return node;}//創建應該初始的空根結點，也是要靜態的變量才行private static Node root=null;public static void main(String[] args) {Scanner sc =new Scanner(System.in);int n = sc.nextInt();while (n>0){String point=sc.next();root = setNode(root,point);preOrder();inOrder();postOrder();num=0;  //每次記得重置一下，因為這個我測試了好久才發現這個小錯誤n--;}}//實現先序遍歷("根"結點 -> 左孩子 -> 右孩子)public static void preOrder(){preOrder(root);System.out.println();   //遍歷完記得換行}public static void preOrder(Node node){//首先判斷傳進來的"根結點"是否為空if(node!=null){//只要不為空就先輸出當前"根結點"并繼續遍歷其左孩子，直到左孩子無左右孩子，再輸出當前"根結點"，再往前遞歸System.out.print(node.data);preOrder(node.lChild);preOrder(node.rChild);}}//實現中序遍歷(左孩子 -> "根"結點 ->右孩子)public static void inOrder(){inOrder(root);System.out.println();  //遍歷完記得換行}public static void inOrder(Node node){//首先判斷傳進來的"根結點"是否為空,然后先遍歷左孩子，直到左孩子的左孩子為空，那就輸出當前的"根結點"，再遍歷右孩子，再往前遞歸if(node!=null){inOrder(node.lChild);System.out.print(node.data);inOrder(node.rChild);}}//實現后序遍歷(左孩子 -> 右孩子 ->"根"結點 )public static void postOrder(){postOrder(root);System.out.println();  //遍歷完記得換行}public static void postOrder(Node node){//首先判斷傳進來的"根結點"是否為空,然后先遍歷左孩子，直到左孩子的左右孩子為空，那就輸出當前的"根結點"，再往前遞歸if(node!=null){postOrder(node.lChild);postOrder(node.rChild);System.out.print(node.data);}}
}

四、不同情況的代碼測試運行結果：

<1>首先是題目中的測試輸入樣例：(最好手打輸入測試，直接復制可能格式問題導致報錯！)

<2>其他：?