3.8二叉树中结点最大的距离重建二叉树顺序遍历二叉树

1. 前言

本文的一些图片, 资料 截取自编程之美

2. 问题描述

3. 问题分析

对于树的相关问题, 递归是非常常见的

对于第一个问题 : 可以通过先递归获取每一个结点的最大左子树的深度, 以及最大右子树的深度, 然后在递归一次获取(node.maxLeft &＃43; node.maxRight)的最大值即为所求

对于第二个问题, 因为我们现在有一个先序, 中序的遍历序列, 所以我们可以确定root结点即为先序遍历的第一个结点, 然后根据中序序列来确定root结点的左右子树, 然后在递归建树即可

对于第三个问题 , 通常是使用一个队列来维护需要遍历的结点队列, 遍历一个结点之后, 就将其左右孩子结点添加到队列中, 遍历啊遍历, 直到队列为空

对于上面的描述, 可能比较抽象, 下面是几幅图, 希望可以帮助理解

问题一 :
1 给定的树

2 递归获取树的最大左右子树深度

3 递归获取树的结点最大距离

问题二 :
1 前序和中序
firstOrder :
infixOrder :

2 判断根节点, 左右子树
根据firstOrder判断根节点 :
根据中序判断左右子树 :
在根据左右子树的节点数, 分解前序中的左右子树 :

确定左右子树的前序, 中序遍历序列之后, 即可递归建树了

问题三 :
1 给定的树

2 将当前结点的左右结点添加到队列, 进队的顺序

进队的顺序就保证了层次关系, 因而层次遍历二叉树得以实现

4. 代码

备注 : 先序构建树, “#“结点表示空节点, 上面的问题三的图形对应的数的表示为 : a b # d # # c f # # e # #
代码清单 :
1 先序建树
2 先序 &＃43; 中序, 中序 &＃43; 后序, 重建二叉树 [一种思路是上面的思路, 另一种思路是先补全其先序序列[加上空结点], 然后在利用先序建树(1)[注意 : 中序 &＃43; 后序重建树, 需要先构建右子树, 然后在构建左子树 ], 不过原理和第一种基本上一致 ]
3 判断给定的先序 &＃43; 中序, 是否能够构建一颗二叉树
4 获取指定层级的结点
5 层次遍历, 层次自底向上遍历二叉树

/*** file name : Test09FindMaxDisInBinaryTree.java* created at : 8:56:46 AM May 29, 2015* created by 970655147*/package com.hx.test04;public class Test09FindMaxDisInBinaryTree {// 1. 获取一颗二叉树的两个节点的最大距离// 2. 重建二叉树// 3. 判断给定的(前序, 中序)[(中序, 后序) ] 是否能够成一个合法的二叉树// 4. 获取二叉树的某一层的元素// 5. 顺序遍历二叉树 层次遍历二叉树public static void main(String []args) {// BinTree bt &＃61; BinTree.createABinTree();
// Log.log(bt);// -----------获取一颗二叉树的两个节点的最大距离--------------- String data &＃61; "58 34 12 # # 42 # # 78 68 69 # # # 99 # #";BinTree bt &＃61; BinTree.createABinTree(data);Log.log(bt);List deepth &＃61; new ArrayList();bt.headTraverseForMaxDepth(bt.root, 0, deepth);Log.log(deepth );// 相信能获取到这个 数据的话应该知道 该怎么获取最大深度了吧,,int maxDis &＃61; bt.getMaxDis(bt.root);Log.log("maxDistance : " &＃43; maxDis);// -----------重建二叉树--------------- String data02 &＃61; "a b # d # # c f # # e # #";String firstOrder &＃61; "a b d c e f";String infixOrder &＃61; "d b a e c f";String epilogue &＃61; "d b e f c a";// BinTree bt02 &＃61; BinTree.rebuildForFirstOrderAndInfixOrder(firstOrder, infixOrder);
// BinTree bt02 &＃61; BinTree.rebuildForFirstOrderAndInfixOrder02(firstOrder, infixOrder);
// BinTree bt02 &＃61; BinTree.rebuildForInfixOrderAndEpilogue(infixOrder, epilogue);BinTree bt02 &＃61; BinTree.rebuildForInfixOrderAndEpilogue02(epilogue, infixOrder);Log.log(bt02);// -----------判断给定的(前序, 中序)[(中序, 后序) ] 是否能够成一个合法的二叉树--------------- String[] first &＃61; firstOrder.split("\\s&＃43;");String[] infix &＃61; infixOrder.split("\\s&＃43;");Log.log(BinTree.canCompleteForFirstOrderAndInfixOrder(first, infix, 0, 0, first.length) );// -----------获取二叉树的某一层的元素---------------BinTree.getSpecifiedLayerElements(bt.root, 2);Log.enter();// -----------顺序遍历二叉树 层次遍历二叉树---------------BinTree.traverseInOrder(bt.root);BinTree.traverseInOrder02(bt.root);BinTree.traverseInOrderInversely(bt.root);BinTree.traverseInOrderInversely02(bt.root);// -----------splits---------------}// 一颗二叉树public static class BinTree {// 根节点Node root;// 初始化public BinTree() {root &＃61; new Node();}public BinTree(Node root) {this.root &＃61; root;}// 获取root节点public Node root() {return root;}// 判断结点的左结点是否为空[#也算为空]public static boolean isNodeNull(Node node) {return (node &＃61;&＃61; null) || (Node.NULL.equals(node.getData()) );}// 根据用户的输入创建一颗二叉树public static BinTree createABinTree() {BinTree bt &＃61; new BinTree();createNode(bt.root, "root");return bt;}// 根据指定格式的字符串创建一颗二叉树public static BinTree createABinTree(String data) {return createABinTreeReversely(data);}// 根据指定格式的字符串创建一颗二叉树 先建立左子树 在建立右子树public static BinTree createABinTreeReversely(String data) {BinTree bt &＃61; new BinTree();String[] splits &＃61; data.split("\\s&＃43;");idx &＃61; 0;createNodeReversely(bt.root, splits);return bt;}// 根据指定格式的字符串创建一颗二叉树 先建立右子树 在建立左子树public static BinTree epilogueOrderCreateABinTreeInversely(String data) {BinTree bt &＃61; new BinTree();String[] splits &＃61; data.split("\\s&＃43;");idx &＃61; 0;epilogueOrderCreateNodeInversely(bt.root, splits);return bt;}// assistMethod 根据用户的输入建树private static void createNode(Node node, String notice) {Scanner scan &＃61; Tools.getScanner();Log.logWithoutLn("please input " &＃43; notice &＃43; " : ");node.data &＃61; scan.next();if(!Node.NULL.equals(node.data) ) {node.left &＃61; new Node();node.right &＃61; new Node();createNode(node.left, notice &＃43; "&＃39;s leftChild");createNode(node.right, notice &＃43; "&＃39;s rightChild");}}// assistMethod 根据指定格式的字符串建树static int idx;// 先建立左子树 在建立右子树private static void createNodeReversely(Node node, String[] data) {node.data &＃61; data[idx &＃43;&＃43;];if(!Node.NULL.equals(node.data) ) {node.left &＃61; new Node();node.right &＃61; new Node();createNodeReversely(node.left, data);createNodeReversely(node.right, data);}}// 先建立右子树 在建立左子树private static void epilogueOrderCreateNodeInversely(Node node, String[] data) {node.data &＃61; data[idx &＃43;&＃43;];if(!Node.NULL.equals(node.data) ) {node.left &＃61; new Node();node.right &＃61; new Node();epilogueOrderCreateNodeInversely(node.right, data);epilogueOrderCreateNodeInversely(node.left, data);}}// 根据先序, 中序 重新建树// 思路 : 先补全树的字符串表示, 在建树[左 -> 右]public static BinTree rebuildForFirstOrderAndInfixOrder(String firstOrder, String infixOrder) {String[] first &＃61; firstOrder.split("\\s&＃43;");String[] infix &＃61; infixOrder.split("\\s&＃43;");StringBuilder sb &＃61; new StringBuilder();completeForFirstOrderAndInfixOrder(first, infix, 0, 0, first.length, sb);return createABinTree(sb.toString());}// 根据先序, 中序 重新建树 递归建树public static BinTree rebuildForFirstOrderAndInfixOrder02(String firstOrder, String infixOrder) {String[] first &＃61; firstOrder.split("\\s&＃43;");String[] infix &＃61; infixOrder.split("\\s&＃43;");Node root &＃61; rebuildForFirstOrderAndInfixOrder020(first, infix, 0, 0, first.length);return new BinTree(root);}// 根据中序, 后序 重新建树// 思路 : 先补全树的逆序字符串表示, 在逆序建树[右 -> 左]public static BinTree rebuildForInfixOrderAndEpilogue(String infixOrder, String epilogueOrder) {String[] epilogue &＃61; epilogueOrder.split("\\s&＃43;");String[] infix &＃61; infixOrder.split("\\s&＃43;");StringBuilder sb &＃61; new StringBuilder();completeForInfixOrderAndEpilogue(epilogue, infix, 0, 0, epilogue.length, sb);return epilogueOrderCreateABinTreeInversely(sb.toString());}// 根据先序, 中序 重新建树 递归建树public static BinTree rebuildForInfixOrderAndEpilogue02(String epilogueOrder, String infixOrder) {String[] epilogue &＃61; epilogueOrder.split("\\s&＃43;");String[] infix &＃61; infixOrder.split("\\s&＃43;");Node root &＃61; rebuildForInfixOrderAndEpilogueOrder020(epilogue, infix, 0, 0, infix.length);return new BinTree(root);}// 根据先序和中序 补全 "#"子节点private static void completeForFirstOrderAndInfixOrder(String[] first, String[] infix, int start01, int start02, int len, StringBuilder sb) {sb.append(first[start01] &＃43; " ");int idx &＃61; getIdxForStr(first[start01], infix, start02, len);int leftNumMinus1 &＃61; idx - start02, rightNumMinus1 &＃61; start02 &＃43; len - idx - 1;if(leftNumMinus1 &＃61;&＃61; 0) {sb.append("# ");} else {completeForFirstOrderAndInfixOrder(first, infix, start01&＃43;1, start02, leftNumMinus1, sb);}if(rightNumMinus1 &＃61;&＃61; 0) {sb.append("# ");} else {completeForFirstOrderAndInfixOrder(first, infix, start01&＃43;leftNumMinus1&＃43;1, idx&＃43;1, rightNumMinus1, sb);}}// 根据先序和中序, 递归构造左右子树private static Node rebuildForFirstOrderAndInfixOrder020(String[] first, String[] infix, int start01, int start02, int length) {Node node &＃61; new Node(first[start01]);int idx &＃61; getIdxForStr(first[start01], infix, start02, length);int leftNumMinus1 &＃61; idx - start02, rightNumMinus1 &＃61; start02 &＃43; length - idx - 1;if(leftNumMinus1 > 0) {node.left &＃61; rebuildForFirstOrderAndInfixOrder020(first, infix, start01&＃43;1, start02, leftNumMinus1);} else {node.left &＃61; new Node(Node.NULL);}if(rightNumMinus1 > 0) {node.right &＃61; rebuildForFirstOrderAndInfixOrder020(first, infix, start01&＃43;1&＃43;leftNumMinus1, idx&＃43;1, rightNumMinus1);} else {node.right &＃61; new Node(Node.NULL);}return node;}// 根据先序和中序 补全 "#"子节点private static void completeForInfixOrderAndEpilogue(String[] epilogue, String[] infix, int start01, int start02, int len, StringBuilder sb) {int endIdx &＃61; start01 &＃43; len - 1;sb.append(epilogue[endIdx] &＃43; " ");int idx &＃61; getIdxForStr(epilogue[endIdx], infix, start02, len);int leftNumMinus1 &＃61; idx - start02, rightNumMinus1 &＃61; start02 &＃43; len - idx - 1;if(rightNumMinus1 &＃61;&＃61; 0) {sb.append("# ");} else {completeForInfixOrderAndEpilogue(epilogue, infix, endIdx-rightNumMinus1, idx&＃43;1, rightNumMinus1, sb);}if(leftNumMinus1 &＃61;&＃61; 0) {sb.append("# ");} else {completeForInfixOrderAndEpilogue(epilogue, infix, start01, start02, leftNumMinus1, sb);}}// 根据中序和后序, 递归构造左右子树private static Node rebuildForInfixOrderAndEpilogueOrder020(String[] epilogue, String[] infix, int start01, int start02, int length) {int endIdx &＃61; start01 &＃43; length - 1;Node node &＃61; new Node(epilogue[endIdx]);int idx &＃61; getIdxForStr(epilogue[endIdx], infix, start02, length);int leftNumMinus1 &＃61; idx - start02, rightNumMinus1 &＃61; start02 &＃43; length - idx - 1;if(rightNumMinus1 > 0) {node.right &＃61; rebuildForInfixOrderAndEpilogueOrder020(epilogue, infix, start01&＃43;leftNumMinus1, idx&＃43;1, rightNumMinus1);} else {node.right &＃61; new Node(Node.NULL);}if(leftNumMinus1 > 0) {node.left &＃61; rebuildForInfixOrderAndEpilogueOrder020(epilogue, infix, start01, start02, leftNumMinus1);} else {node.left &＃61; new Node(Node.NULL);}return node;}// 判断给定的前序和中序 是否合理 是否能构成一颗合法的二叉树public static boolean canCompleteForFirstOrderAndInfixOrder(String[] first, String[] infix, int start01, int start02, int len) {int idx &＃61; getIdxForStr(first[start01], infix, start02, len);int leftNumMinus1 &＃61; idx - start02, rightNumMinus1 &＃61; start02 &＃43; len - idx - 1;boolean isLeftOk &＃61; false, isRightOk &＃61; false;if(leftNumMinus1 &＃61;&＃61; 0) {isLeftOk &＃61; true;} else {isLeftOk &＃61; canCompleteForFirstOrderAndInfixOrder(first, infix, start01&＃43;1, start02, leftNumMinus1);}if(rightNumMinus1 &＃61;&＃61; 0) {isRightOk &＃61; true;} else {isRightOk &＃61; canCompleteForFirstOrderAndInfixOrder(first, infix, start01&＃43;leftNumMinus1&＃43;1, idx&＃43;1, rightNumMinus1);}return isLeftOk && isRightOk;}// 获取level层的元素 递归实现public static void getSpecifiedLayerElements(Node node, int level) {if(Node.NULL.equals(node.data) ) {return ;}if(level &＃61;&＃61; 0) {Log.logWithoutLn(node.data &＃43; " ");}getSpecifiedLayerElements(node.left, level-1);getSpecifiedLayerElements(node.right, level-1);}// 顺序遍历二叉树 方向从左至右public static void traverseInOrder(Node node) {Deque que &＃61; new LinkedList();que.addLast(node);while(que.size() > 0) {Node tmp &＃61; que.pollFirst();Log.logWithoutLn(tmp.data &＃43; " ");if(!Node.NULL.equals(tmp.left.data) ) {que.addLast(tmp.left);}if(!Node.NULL.equals(tmp.right.data) ) {que.addLast(tmp.right);}}Log.enter();}// 顺序遍历二叉树 方向从右至左public static void traverseInOrder02(Node node) {Deque que &＃61; new LinkedList();que.addLast(node);while(que.size() > 0) {Node tmp &＃61; que.pollFirst();Log.logWithoutLn(tmp.data &＃43; " ");if(!Node.NULL.equals(tmp.right.data) ) {que.addLast(tmp.right);}if(!Node.NULL.equals(tmp.left.data) ) {que.addLast(tmp.left);}}Log.enter();}// 顺序自底向上遍历二叉树 方向从左至右public static void traverseInOrderInversely(Node node) {Deque que &＃61; new LinkedList();Deque inv &＃61; new LinkedList();que.addLast(node);while(que.size() > 0) {Node tmp &＃61; que.pollFirst();inv.push(tmp);if(!Node.NULL.equals(tmp.right.data) ) {que.addLast(tmp.right);}if(!Node.NULL.equals(tmp.left.data) ) {que.addLast(tmp.left);}}while(inv.size() > 0) {Node tmp &＃61; inv.pop();Log.logWithoutLn(tmp.data &＃43; " ");}Log.enter();}// 顺序自底向上遍历二叉树 方向从右至左public static void traverseInOrderInversely02(Node node) {Deque que &＃61; new LinkedList();Deque inv &＃61; new LinkedList();que.addLast(node);while(que.size() > 0) {Node tmp &＃61; que.pollFirst();inv.push(tmp);if(!Node.NULL.equals(tmp.left.data) ) {que.addLast(tmp.left);}if(!Node.NULL.equals(tmp.right.data) ) {que.addLast(tmp.right);}}while(inv.size() > 0) {Node tmp &＃61; inv.pop();Log.logWithoutLn(tmp.data &＃43; " ");}Log.enter();}// 获取arr中与str相同的字符串的索引private static int getIdxForStr(String str, String[] arr, int start, int len) {int idx &＃61; -1, end &＃61; start &＃43; len;for(int i&＃61;start; iif(str.equals(arr[i]) ) {idx &＃61; i;return idx;}}return idx;}// 先序遍历public void headTraverse(Node node) {if(node !&＃61; null) {Log.logWithoutLn(node.data &＃43; " ");headTraverse(node.left);headTraverse(node.right);}}// assistMethod toString时使用 先序遍历二叉树 获取当前二叉树的字符串表示public void headTraverseForString(Node node, StringBuilder sb) {if(node !&＃61; null) {sb.append(node.data &＃43; " ");
// sb.append(node.maxLeft &＃43; " - " &＃43; node.maxRight &＃43; "; ");headTraverseForString(node.left, sb);headTraverseForString(node.right, sb);}}// 先序遍历二叉树获取各个叶子节点的深度public void headTraverseForMaxDepth(Node node, int cnt, List deepth) {if(! node.data.equals(Node.NULL) ) {headTraverseForMaxDepth(node.left, cnt&＃43;1, deepth);headTraverseForMaxDepth(node.right, cnt&＃43;1, deepth);} else {deepth.add(cnt);return ;}}// 先序遍历二叉树 获取每一个节点的最深左子树的深度, 和最深右子树的深度private void headTraverseForDepth(Node node, int cnt) {if(!node.data.equals(Node.NULL) ) {headTraverseForDepth(node.left, cnt&＃43;1);headTraverseForDepth(node.right, cnt&＃43;1);node.maxLeft &＃61; getMax(node.left.maxLeft &＃43; 1, node.left.maxRight &＃43; 1);node.maxRight &＃61; getMax(node.right.maxLeft &＃43; 1, node.right.maxRight &＃43; 1);} else {node.maxLeft &＃61; -1;node.maxRight &＃61; -1;return ;}}// 获取node子树的可能的最大距离 // 先递归获取每一个结点的最大左子树的深度, 以及最大右子树的深度, 然后在递归一次获取(node.maxLeft &＃43; node.maxRight)的最大值即为所求public int getMaxDis(Node node ) {headTraverseForDepth(node, 0);return getMaxDis0(node);}// 获取node子树的可能的最大距离 sum表示(maxLeft &＃43; maxRight)// 如果node.sum大于node.left.sum, node.right.sum 则结果去node.sum// 否则 去较大的子树结点 递归private int getMaxDis0(Node node ) {int nodeSum &＃61; node.maxLeft &＃43; node.maxRight;int nodeLeftSum &＃61; node.left.maxLeft &＃43; node.right.maxRight;int nodeRightSum &＃61; node.right.maxLeft &＃43; node.right.maxRight;int max &＃61; getMax(nodeSum, nodeLeftSum);max &＃61; getMax(max, nodeRightSum);if(max &＃61;&＃61; nodeSum) {return nodeSum;} else if(max &＃61;&＃61; nodeLeftSum) {return getMaxDis(node.left);} else if(max &＃61;&＃61; nodeRightSum) {return getMaxDis(node.right);}return -1;}// 获取x, y的较大值private int getMax(int x, int y) {return x > y ? x : y;}// Debugpublic String toString() {StringBuilder sb &＃61; new StringBuilder();headTraverseForString(root, sb);return sb.toString();}}// 树的结点public static class Node {// 空节点 表示叶子节点final static String NULL &＃61; "#";// data 存放该节点的数据, left, right 存放左/ 右子树的索引// maxLeft, maxRight 表示左/ 右子树的最深深度String data;Node left;Node right;int maxLeft;int maxRight;// 初始化public Node() {} public Node(String data) {this.data &＃61; data;}// getter & setter public String getData() {return data;} public Node getLeft() {return left;}public Node getRight() {return right;}public void setLeft(Node left) {this.left &＃61; left;}public void setRight(Node right) {this.right &＃61; right;}// Debugpublic String toString() {return data;}}}


5. 运行结果

6. 总结

树是一种递归的结构&＃xff0c; 所以涉及的算法很多都涉及递归, 通过这几个算法, 相信我们对于二叉树的了解又会深一层