Wenn wir eine
Vorbestellungs-Durchlaufsequenz haben: 1,3,7,9,5,11
In-Reihenfolge-Durchlaufsequenz: 9,7,3,1, 5, 11
Wir können den entsprechenden Binärbaum leicht mit einem Stift schreiben. Aber wie implementiert man es mithilfe von Code?
Lassen Sie uns kurz über die Grundideen sprechen.
Zuerst basiert die Reihenfolge der Vorbestellungsdurchquerung auf der Reihenfolge Wurzel-linkes Kind-rechtes Kind, dann können wir als Erstes bestätigen ist die Durchlaufsequenz vor der Bestellung. Die erste Zahl ist der Wurzelknoten, und dann wird der Durchlauf in der Reihenfolge in der Reihenfolge linkes Kind-Wurzel-rechtes Kind durchlaufen. Wir haben den Wurzelknoten durch die Durchquerung vor der Bestellung bestätigt, dann müssen wir nur noch die Position des Wurzelknotens bei der Durchquerung in der Reihenfolge finden, und dann können wir leicht die Knoten unterscheiden, die zum linken Teilbaum gehören, und diejenigen, die dazu gehören rechter Teilbaum. Wie unten gezeigt:
Wir bestimmen die Nummer 1 als Wurzelknoten und bestimmen sie dann gemäß der Durchlaufreihenfolge der Durchlaufreihenfolge in der Reihenfolge Nummer 1 sind linke Teilbaumknoten und alle rechten Teilbäume sind rechte Teilbäume. Aus der Anzahl der Knoten des linken Teilbaums kann geschlossen werden, dass die drei aufeinanderfolgenden Zahlen vom Wurzelknoten in der Durchlaufsequenz vor der Bestellung zum linken Teilbaum gehören und die verbleibenden Zahlen zum rechten Teilbaum gehören. Auf diese Weise werden die obigen Schritte in der Reihenfolge des linken und rechten Teilbaums wiederholt, bis schließlich keine Kindknoten mehr gefunden werden.
Der Implementierungscode lautet wie folgt:
1 package com.tree.traverse; 2 3 import java.util.ArrayList; 4 import java.util.List; 5 6 /** 7 * @author Caijh 8 * 9 * 2017年6月2日 下午7:21:10 10 */ 11 12 public class BuildTreePreOrderInOrder { 13 14 /** 15 * 1
16 * / \ 17 * 3 5
18 * / \ 19 * 7 11 20 * /
21 * 9
22 */ 23 public static int treeNode = 0;//记录先序遍历节点的个数 24 private List<Node> nodeList = new ArrayList<>();//层次遍历节点的队列 25 public static void main(String[] args) { 26 BuildTreePreOrderInOrder build = new BuildTreePreOrderInOrder(); 27 int[] preOrder = { 1, 3, 7, 9, 5, 11}; 28 int[] inOrder = { 9, 7, 3, 1, 5, 11}; 29 30 treeNode = preOrder.length;//初始化二叉树的节点数 31 Node root = build.buildTreePreOrderInOrder(preOrder, 0, preOrder.length - 1, inOrder, 0, preOrder.length - 1); 32 System.out.print("先序遍历："); 33 build.preOrder(root); 34 System.out.print("\n中序遍历："); 35 build.inOrder(root); 36 System.out.print("\n原二叉树：\n"); 37 build.prototypeTree(root); 38 } 39 40 /** 41 * 分治法 42 * 通过先序遍历结果和中序遍历结果还原二叉树 43 * @param preOrder 先序遍历结果序列 44 * @param preOrderBegin 先序遍历起始位置下标 45 * @param preOrderEnd 先序遍历末尾位置下标 46 * @param inOrder 中序遍历结果序列 47 * @param inOrderBegin 中序遍历起始位置下标 48 * @param inOrderEnd 中序遍历末尾位置下标 49 * @return 50 */ 51 public Node buildTreePreOrderInOrder(int[] preOrder, int preOrderBegin, int preOrderEnd, int[] inOrder, int inOrderBegin, int inOrderEnd) { 52 if (preOrderBegin > preOrderEnd || inOrderBegin > inOrderEnd) { 53 return null; 54 } 55 int rootData = preOrder[preOrderBegin];//先序遍历的第一个字符为当前序列根节点 56 Node head = new Node(rootData); 57 int divider = findIndexInArray(inOrder, rootData, inOrderBegin, inOrderEnd);//找打中序遍历结果集中根节点的位置 58 int offSet = divider - inOrderBegin - 1;//计算左子树共有几个节点，节点数减一，为数组偏移量 59 Node left = buildTreePreOrderInOrder(preOrder, preOrderBegin + 1, preOrderBegin + 1 + offSet, inOrder, inOrderBegin,inOrderBegin + offSet); 60 Node right = buildTreePreOrderInOrder(preOrder, preOrderBegin + offSet + 2, preOrderEnd, inOrder, divider + 1, inOrderEnd); 61 head.left = left; 62 head.right = right; 63 return head; 64 } 65 /** 66 * 通过先序遍历找到的rootData根节点，在中序遍历结果中区分出：中左子树和右子树 67 * @param inOrder 中序遍历的结果数组 68 * @param rootData 根节点位置 69 * @param begin 中序遍历结果数组起始位置下标 70 * @param end 中序遍历结果数组末尾位置下标 71 * @return return中序遍历结果数组中根节点的位置 72 */ 73 public int findIndexInArray(int[] inOrder, int rootData, int begin, int end) { 74 for (int i = begin; i <= end; i++) { 75 if (inOrder[i] == rootData) 76 return i; 77 } 78 return -1; 79 } 80 /** 81 * 二叉树先序遍历结果 82 * @param n 83 */ 84 public void preOrder(Node n) { 85 if (n != null) { 86 System.out.print(n.val + ","); 87 preOrder(n.left); 88 preOrder(n.right); 89 } 90 } 91 /** 92 * 二叉树中序遍历结果 93 * @param n 94 */ 95 public void inOrder(Node n) { 96 if (n != null) { 97 inOrder(n.left); 98 System.out.print(n.val + ","); 99 inOrder(n.right);100 }101 }102 /**103 * 还原后的二叉树104 * 二叉数层次遍历105 * 基本思想：106 * 1.因为推导出来的二叉树是保存在Node类对象的子对象里面的，（类似于c语言的结构体）如果通过递归实现层次遍历的话，不容易实现107 * 2.这里采用List队列逐层保存Node对象节点的方式实现对二叉树的层次遍历输出108 * 3.如果父节点的位置为i,那么子节点的位置为，2i 和 2i+1;依据这个规律逐层遍历，通过保存的父节点，找到子节点。并保存，不断向下遍历保存。109 * @param tree110 */111 public void prototypeTree(Node tree){112 //用list存储层次遍历的节点113 if(tree !=null){114 if(tree!=null)115 nodeList.add(tree);116 nodeList.add(tree.left);117 nodeList.add(tree.right);118 int count=3;119 //从第三层开始120 for(int i=3;count<treeNode;i++){121 //第i层第一个子节点的父节点的位置下标122 int index = (int) Math.pow(2, i-1-1)-1;123 /**124 * 二叉树的每一层节点数遍历125 * 因为第i层的最大节点数为2的i-1次方个，126 */127 for(int j=1;j<=Math.pow(2, i-1);){128 //计算有效的节点的个数，和遍历序列的总数做比较，作为判断循环结束的标志129 if(nodeList.get(index).left!=null)130 count++;131 if(nodeList.get(index).right!=null)132 count++;133 nodeList.add(nodeList.get(index).left);134 nodeList.add(nodeList.get(index).right);135 index++;136 if(count>=treeNode)//当所有有效节点都遍历到了就结束遍历137 break;138 j+=2;//每次存储两个子节点，所以每次加2139 }140 }141 int flag=0,floor=1;142 for(Node node:nodeList){143 if(node!=null)144 System.out.print(node.val+" ");145 else146 System.out.print("# ");//#号表示空节点147 flag++;148 /**149 * 逐层遍历输出二叉树150 *
151 */152 if(flag>=Math.pow(2, floor-1)){153 flag=0;154 floor++;155 System.out.println();156 }157 }158 }159 }160 /**161 * 内部类162 * 1.每个Node类对象为一个节点，163 * 2.每个节点包含根节点，左子节点和右子节点164 */165 class Node {166 Node left;167 Node right;168 int val;169 public Node(int val) {170 this.val = val;171 }172 }173 }
Laufergebnis:
Abschließend die Grundidee der schichtweisen Ausgabe des Binärbaums:
* 1. Weil der abgeleitete Binärbaum im Unterobjekt des Node-Klassenobjekts gespeichert ist , (ähnlich der Struktur der C-Sprache) wenn Es ist nicht einfach, hierarchische Durchquerung durch Rekursion zu implementieren
* 2. Hier wird die Listenwarteschlange verwendet, um Knotenobjektknoten Schicht für Schicht zu speichern und die hierarchische Durchquerungsausgabe zu realisieren der Binärbaum
* 3. Wenn die Position des übergeordneten Knotens i ist, dann sind die Positionen der untergeordneten Knoten 2i und 2i+1. Durchlaufen Sie Schicht für Schicht und finden Sie die untergeordneten Knoten durch die gespeicherten übergeordneter Knoten. Und zum Speichern gehen Sie weiter nach unten, um zu speichern.
Das obige ist der detaillierte Inhalt vonStellen Sie den Binärbaum durch die Sequenz nach der Durchquerung vor der Bestellung und der Durchquerung in der Reihenfolge wieder her. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!
![[Web-Frontend] Node.js-Schnellstart](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
