二叉树Java实现

 

      为了克服对树结构编程的畏惧感和神秘感，下定决心将二叉树的大部分操作实现一遍，并希望能够掌握二叉树编程的一些常用技术和技巧。关于编程实现中的心得和总结，敬请期待！~

      [1]  数据结构和表示： 二叉树的输入输出格式采用广义表表达式形式，内部表示采用左孩子右孩子的链式存储。

      [2]  已经实现的操作有：

             A. 根据二叉树的广义表表达式来创建二叉树(含表达式合法性检测)；

             B. 根据二叉树的前序和中序遍历列表来创建二叉树；

             C. 根据二叉树的中序和后序遍历列表来创建二叉树；

             D. 二叉树的“左孩子右孩子”链式存储转化为广义表表达式；

             E. 二叉树的前序、中序、后序的递归和非递归遍历；层序遍历；结点关联列表；

             F. 求解二叉树的高度、结点总数、叶子结点总数、所有的叶子结点列表；根结点到所有叶子结点的路径；最长路径；

             G. 二叉树复制，二叉树全等性比较，二叉树交换（将二叉树的所有结点的左右子树互换）

       [3]  尚待实现的操作：

             A. 求解二叉树中所有最长(短)路径

             E. 其它

 

       [4]  二叉树 Java 实现代码：

 

        /** * BinaryTree: 实现二叉树，可以根据给定的广义表表达式、前序及中序遍历列表、中序及后序遍历列表创建二叉树; * 二叉树的前序、中序、后序的递归和非递归遍历，层序遍历;求解二叉树的一些特性 * * @author shuqin1984 2011-3-19 * */package datastructure.tree;import java.util.ArrayList;import java.util.Iterator;import java.util.LinkedList;import java.util.List;import java.util.regex.Matcher;import java.util.regex.Pattern;public class BinaryTree {/**二叉树的广义表表示 */private String expression;/** 树的根结点 */private TreeNode root;/** * 用于检测二叉树广义表表达式合法性的编译了的正则表达式: * 合法的广义表表达式可以是： * [1] 基本表达式： A，A(,), A(B,), A(,B), A(B,C) * [2] 上述的 A，B，C 可以是 [1] 中的基本表达式 * [3] A,B,C 可允许的取值范围由应用决定，这里仅允许是 大小写字母，数字，+-/*% * [4] 表达式中不含任何空格符，因此，在检查表达式之前，必须确保表达式中不含空格符 * */private static String permittedChars = "[a-zA-Z0-9//+//-//*/////%]";private static String basicUnit = "[a-zA-Z0-9//+//-//*/////%//(//),]";private static Pattern basicPattern = Pattern.compile("" + "|" + permittedChars + "|" + permittedChars + "//(" + permittedChars + "?," + permittedChars + "?//)?");private static Pattern extendPattern = Pattern.compile(permittedChars + "//(" + basicUnit + "*," + basicUnit + "*//)");/** * 构造器 * @param root 树的根结点 */public BinaryTree(TreeNode root) {this.root = root;}/** * 构造器 * @param expression 二叉树的广义表表达式 */private BinaryTree(String expression) {this.expression = expression;}/** * 树结点实现 */private class TreeNode {private char ch;private TreeNode rchild;private TreeNode lchild;public TreeNode(char ch, TreeNode rchild, TreeNode lchild) {this.ch = ch;this.rchild = rchild;this.lchild = lchild;}public char getCh() {return ch;}public TreeNode getRchild() {return rchild;}public void setRchild(TreeNode rchild) {this.rchild = rchild;}public TreeNode getLchild() {return lchild;}public void setLchild(TreeNode lchild) {this.lchild = lchild;}public String toString(){return "" + getCh();}}/** * 结点关联类 */private class NodeLink {private TreeNode node1;private TreeNode node2;public NodeLink(TreeNode node1, TreeNode node2) {this.node1 = node1;this.node2 = node2;} public String toString() { return "(" + node1.getCh() + "," + node2.getCh() + ")"; }}/** * 【设置/获取】属性 */public TreeNode getRoot() {return root;}public void setRoot(TreeNode root) {this.root = root;} /** * getPreOrderList: 获得树的先序遍历列表 * @param flag 是否采用递归遍历的标记；若 flag = true， 采用递归遍历；否则，采用非递归遍历 * @return 二叉树的先序遍历列表 */public List<TreeNode> getPreOrderList(boolean flag) {List<TreeNode>nodelist = new ArrayList<TreeNode>();if (flag == true) { nodelist = preOrderTraverse(getRoot(), nodelist);}else { nodelist = preOrderTraverseIter(getRoot());}return nodelist;}/** * getInOrderList: 获得树的中序遍历列表 * @param flag 是否采用递归遍历的标记；若 flag = true， 采用递归遍历；否则，采用非递归遍历 * @return 获得树的中序遍历列表 */ public List<TreeNode> getInOrderList(boolean flag) { List<TreeNode>nodelist = new ArrayList<TreeNode>(); if (flag == true) { nodelist = inOrderTraverse(getRoot(), nodelist); } else { nodelist = inOrderTraverseIter(getRoot()); }return nodelist;} /** * getPostOrderList: 获得树的后序遍历列表 * @param flag 是否采用递归遍历的标记；若 flag = true， 采用递归遍历；否则，采用非递归遍历 * @return 获得树的后序遍历列表 */ public List<TreeNode> getPostOrderList(boolean flag) { List<TreeNode>nodelist = new ArrayList<TreeNode>(); if (flag == true) { nodelist = postOrderTraverse(getRoot(), nodelist); } else { nodelist = postOrderTraverseIter(getRoot()); }return nodelist;} /** * 获得树的层序遍历列表 * * @return 获得树的层序遍历列表 */ public List<TreeNode> getFloorOrderList() { List<TreeNode>nodelist = new ArrayList<TreeNode>();nodelist = floorOrderTraverse(getRoot());return nodelist;} /** * createBinaryTree: 根据树的广义表表示构造二叉树 * @throws Exception */ public static BinaryTree createBinaryTree(String expression) throws Exception { BinaryTree bt = new BinaryTree(trimSpace(expression)); bt.createBinaryTree(); return bt; } /** * createBinaryTree: 根据二叉树的广义表表达式来创建二叉树 * @exception 若二叉树的广义表表达式不合法，则抛出异常 */private void createBinaryTree() throws Exception {// 检查传入的二叉树广义表示法是否合法有效if (!checkValid(expression))throw new Exception("广义表表达式不合法，无法创建二叉树!");// 使用 LinkedList 来执行栈的功能LinkedList<TreeNode> stack = new LinkedList<TreeNode>();TreeNode newnode = null;int flag = 0; // flag = 0: 创建左子树 | flag = 1: 创建右子树for (char ch: expression.toCharArray()) {switch (ch) { // 遇到 "(" 时，表示该结点可能有孩子结点，将该父结点压入栈中 case '(': stack.push(newnode); flag = 0; break; // 遇到 ")" 时，表示已经扫描完父结点的右孩子结点的值，弹出该父结点 case ')': stack.pop(); break; // 遇到 "," 时， 表示将要扫描父结点的右孩子结点的值。 case ',': flag = 1; break; // 遇到结点的值，将其加入二叉树中 default: newnode = new TreeNode(ch, null, null);if (root == null) { root = newnode;}else { if (flag == 0) { TreeNode topnode = stack.peek(); topnode.setLchild(newnode); } else { TreeNode topnode = stack.peek(); topnode.setRchild(newnode); }} break; }}}/** * checkValid: 判断给定二叉树的广义表表示是否合法有效 * * @param expression 给定二叉树的广义表表示【字符串形式】 * @return 如果给定的二叉树广义表表示合法有效，返回true; 否则，返回 false * */private static boolean checkValid(String expression){ Matcher m = null;if (basicPattern.matcher(expression).matches())return true;else if ((m = extendPattern.matcher(expression)).matches()) {int index = separatorIndex(expression);if (index == -1) { // 不存在能够分割二叉树广义表达式的左右子树表达式的逗号return false;}String rightEx = "";String leftEx = ""; if (index > 2) {leftEx = expression.substring(2, index); // 左子树的广义表达式}if (index < expression.length()-2) { rightEx = expression.substring(index+1, expression.length()-1); // 右子树的广义表达式 }return checkValid(leftEx) && checkValid(rightEx);}else {return false;}}/** * getGeneralList: 获取该二叉树的广义表表示(字符串表示) */public String getGeneralListString(){StringBuilder sb = new StringBuilder("");if (expression == null) {createGeneralList(root, sb);return sb.toString();}return expression;}/** * getGeneralList: 根据给定二叉树生成其广义表表示(字符串形式) * @param root 树的根结点 * @return 树的广义表表示【字符串形式】 */private void createGeneralList(TreeNode root, StringBuilder sb) { if (root != null) {sb.append(root.getCh());if (root.getLchild() != null || root.getRchild() != null) {sb.append('(');if (root.getLchild() != null) {createGeneralList(root.getLchild(), sb);}sb.append(',');if (root.getRchild() != null) {createGeneralList(root.getRchild(), sb);}sb.append(')');}}}/** * size: 获取二叉树的结点总数 * * @param root 树的根结点 * @return 树的结点总数 * */public int size(TreeNode root) {if (root == null)return 0;else {return size(root.getLchild()) + size(root.getRchild()) + 1;}}/** * leafCounter: 获取二叉树的叶子结点数目 * * @param root 树的根结点 * @return 树的叶子结点数目 * */public int leafCounter(TreeNode root) {if (root == null)return 0;else {if (root.getLchild() == null && root.getRchild() == null)return 1;elsereturn leafCounter(root.getLchild()) + leafCounter(root.getRchild());}}/** * getLeafNodes : 获取该二叉树的所有叶子结点 */public List<TreeNode> getLeafNodes(){List<TreeNode> leaflist = new ArrayList<TreeNode>();getLeafNodes(getRoot(), leaflist);return leaflist;}/** * printLeafPaths : 打印该二叉树的所有叶子结点到根的路径 */public void printLeafPaths(){List<TreeNode> leafPath = new ArrayList<TreeNode>();buildLeafPaths(root, leafPath);}/** * buildLeafPaths : 递归求解给定二叉树的所有叶子结点到根的路径 * @param root 给定二叉树的根结点 * @param path 存放某个叶子结点到根的路径 */public void buildLeafPaths(TreeNode root, List<TreeNode> path){if (root != null) {path.add(root); // 将从根结点到叶子结点的路径上的结点保存起来if (root.getLchild() == null && root.getRchild() == null) { // 到达叶子结点，完成一条路径，并可对其处理processPath(path);}else {buildLeafPaths(root.getLchild(), path);if (root.getLchild() != null) { path.remove(path.size()-1); // 回溯，从左子树到右子树，删除前一条路径上的叶子结点}buildLeafPaths(root.getRchild(), path);if (root.getRchild() != null) { path.remove(path.size()-1);}}}}/** * processPath : 处理从某叶子结点到根结点的路径的操作 */private void processPath(List<TreeNode> path){System.out.println(listToString(path));}/** * getLeafNodes: 递归求解给定二叉树的所有叶子结点 * @param root 给定二叉树的根结点 * @param leaflist 给定二叉树的所有叶子结点 */private void getLeafNodes(TreeNode root, List<TreeNode> leaflist){if (root != null) {if (root.getLchild() == null && root.getRchild() == null) {leaflist.add(root);return ;}getLeafNodes(root.getLchild(), leaflist);getLeafNodes(root.getRchild(), leaflist);}}/** * height: 获取二叉树的高度 * * @param root 树的根结点 * @return 树的高度 * */public int height(TreeNode root){ if (root == null) return 0; else return 1 + Math.max(height(root.getLchild()), height(root.getRchild()));}/** * getNodelinkList: 获取该二叉树的结点关联列表 * @return 树的结点关联列表 */public List<NodeLink> getNodelinkList() {List<NodeLink> linklist = new ArrayList<NodeLink>();createNodelinkList(getRoot(), linklist);return linklist;}/** * createNodelinkList: 递归求解给定二叉树的结点关联列表表示 * @param root 给定二叉树的根结点 * @param linklist 存放给定二叉树的结点关联对象 */private void createNodelinkList(TreeNode root, List<NodeLink> linklist) {if (root != null) {if (root.getLchild() != null) {NodeLink nodelink = new NodeLink(root, root.getLchild());linklist.add(nodelink);createNodelinkList(root.getLchild(), linklist);}if (root.getRchild() != null) {NodeLink nodelink = new NodeLink(root, root.getRchild());linklist.add(nodelink);createNodelinkList(root.getRchild(), linklist);}}}/** * preOrderTraverse: 二叉树的递归先序遍历 * */private List<TreeNode> preOrderTraverse(TreeNode root, List<TreeNode> nodelist) {if (root != null) {nodelist.add(root);preOrderTraverse(root.getLchild(), nodelist);preOrderTraverse(root.getRchild(), nodelist);}return nodelist;}/** * preOrderTraverseIter: 二叉树的非递归先序遍历 */private List<TreeNode> preOrderTraverseIter(TreeNode root) {LinkedList<TreeNode> stack = new LinkedList<TreeNode>();List<TreeNode> nodelist = new ArrayList<TreeNode>();TreeNode pNode = root;for (;;) {while (pNode != null) {nodelist.add(pNode); // 访问根结点 stack.push(pNode); // 根结点入栈 pNode = pNode.getLchild(); // 访问左子树}pNode = stack.pop();pNode = pNode.getRchild(); // 访问右子树if (pNode == null && stack.isEmpty()) { break; }} return nodelist;}/** * inOrderTraverse: 二叉树的递归中序遍历 * */private List<TreeNode> inOrderTraverse(TreeNode root, List<TreeNode> nodelist) {if (root != null) {inOrderTraverse(root.getLchild(), nodelist);nodelist.add(root);inOrderTraverse(root.getRchild(), nodelist);}return nodelist;}/** * inOrderTraverseIter: 二叉树的非递归中序遍历 */private List<TreeNode> inOrderTraverseIter(TreeNode root) {LinkedList<TreeNode> stack = new LinkedList<TreeNode>();List<TreeNode> nodelist = new ArrayList<TreeNode>();TreeNode pNode = root;for (;;) {while (pNode != null) { // 访问左子树stack.push(pNode); pNode = pNode.getLchild();}pNode = stack.pop(); nodelist.add(pNode); // 访问根结点pNode = pNode.getRchild(); // 访问右子树if (pNode == null && stack.isEmpty()) { break; }}return nodelist;}/** * postOrderTraverse: 二叉树的递归后序遍历 */private List<TreeNode> postOrderTraverse(TreeNode root, List<TreeNode> nodelist) {if (root != null) {postOrderTraverse(root.getLchild(), nodelist);postOrderTraverse(root.getRchild(), nodelist);nodelist.add(root);}return nodelist;}/** * postOrderTraverseIter: 二叉树的非递归后序遍历 */private List<TreeNode> postOrderTraverseIter(TreeNode root) {LinkedList<TreeNode> stack = new LinkedList<TreeNode>();List<TreeNode> nodelist = new ArrayList<TreeNode>();int flag = 0; // 标识是否访问过右子树; flag = 0 表示没有访问； flag = 1 表示已经访问过TreeNode pNode = root;TreeNode tmpNode = null;loop1:for (;;) {while (pNode != null) { // 访问左子树stack.push(pNode); pNode = pNode.getLchild();flag = 0;}loop2:for (;;) {if (!stack.isEmpty()) {if (flag == 0) // 尚未访问根结点的右子树{ pNode = stack.peek(); // 取根结点的右子树，访问其右子树 pNode = pNode.getRchild(); flag = 1; continue loop1;}if (flag == 1) { // 已经访问过右子树pNode = stack.pop();nodelist.add(pNode); // 访问根结点，实际上是左右子树均为空的叶子结点 tmpNode = pNode; // 访问某个结点后，立即访问其父结点的右子树pNode = stack.peek(); // 取该结点的父结点if (pNode != null) { // 父结点不为空(没有回溯到整棵树的根结点)if (tmpNode == pNode.getRchild()) { // 如果刚刚访问的结点正是其父结点的右孩子，则直接回溯访问其父结点; continue loop2; }else { // 否则，访问其父结点的右子树 pNode = pNode.getRchild(); continue loop1;}} }}else // 栈空，递归调用结束，退出 {break loop1;}}}return nodelist;}/** * floorOrderTraverse: 二叉树的层序遍历 * * @param root 树的根结点 * @return 树的层序遍历列表 * */private List<TreeNode> floorOrderTraverse(TreeNode root) {// 使用 LinkedList 来执行队列的功能LinkedList<TreeNode> queue = new LinkedList<TreeNode>();List<TreeNode> nodelist = new ArrayList<TreeNode>();if (root != null) {nodelist.add(root);queue.addLast(root);while(queue.size() > 0) {TreeNode node = queue.removeFirst();if (node.getLchild() != null) {nodelist.add(node.getLchild());queue.addLast(node.getLchild());} if (node.getRchild() != null) {nodelist.add(node.getRchild());queue.addLast(node.getRchild());}}}return nodelist;}/** * copyBinaryTree: 复制二叉树 * @return 复制后的二叉树 */ public BinaryTree copyBinaryTree() { TreeNode anotherRoot = null; anotherRoot = copy(getRoot()); return new BinaryTree(anotherRoot); } /** * copy: 复制二叉树 * @param srcRoot 要复制的二叉树的根结点 * @param destRoot 目标二叉树的根结点 */ private TreeNode copy(TreeNode srcRoot) { if (srcRoot != null) { TreeNode newNode = new TreeNode(srcRoot.getCh(), null, null); newNode.setLchild(copy(srcRoot.getLchild())); newNode.setRchild(copy(srcRoot.getRchild())); return newNode; } return null; } /** * equalsTo: 比较该二叉树与给定二叉树 another 是否全等； * 若全等则返回 true, 否则返回 false. */ public boolean equalsTo(BinaryTree another) { return compareEqual(root, another.getRoot()); } /** * equalsTo : 比较给定的两个二叉树是否全等 * 两个二叉树全等当且仅当 * A. 两个二叉树均为空; 或者 * B. 两个二叉树均非空，且所有对应位置的结点都相同，对应结点之间的关联也完全相同. */ private boolean compareEqual(TreeNode root, TreeNode anotherRoot) { return (root == null && anotherRoot == null) || ((root != null && anotherRoot != null) && (root.getCh() == anotherRoot.getCh()) && (compareEqual(root.getLchild(), anotherRoot.getLchild())) && (compareEqual(root.getRchild(), anotherRoot.getRchild()))); } /** * swapTree : 将该二叉树的所有结点的左右孩子互换 */ public void swapTree() { StringBuilder sb = new StringBuilder(""); swapTree(root); createGeneralList(root, sb); expression = sb.toString(); } /** * swapTree : 将给定的二叉树的所有结点的左右孩子互换 * @param root 给定二叉树的根结点 */ private void swapTree(TreeNode root) { if (root != null) { TreeNode tmp = root.getLchild(); root.setLchild(root.getRchild()); root.setRchild(tmp); swapTree(root.getLchild()); swapTree(root.getRchild()); } } /** * longestPath: 获取该二叉树中的一条最长路径 * @return 二叉树中的一条最长路径 */ public List<TreeNode> longestPath() { List<TreeNode> longestPath = new ArrayList<TreeNode>(); longestPath(root, longestPath); return longestPath; } /** * longestPath: 递归求解给定二叉树的一条最长路径 * @param root 给定二叉树的根结点 * @param longestPath 存放二叉树的最长路径上的结点 */ private void longestPath(TreeNode root, List<TreeNode> longestPath) { if (root != null) { longestPath.add(root); if (root.getLchild() == null && root.getRchild() == null) { // 左右子树均空 return ; } if (root.getLchild() != null && root.getRchild() == null) { // 左子树非空，右子树为空，则最长路径的结点必在左子树路径上 longestPath(root.getLchild(), longestPath); } if (root.getLchild() == null && root.getRchild() != null) { // 左子树非空，右子树为空，则最长路径的结点必在右子树路径上 longestPath(root.getRchild(), longestPath); } if (root.getLchild() != null && root.getRchild() != null) { // 左右子树均非空;分别求解左右子树的最长路径，取最大者 List<TreeNode> leftLongestPath = new ArrayList<TreeNode>(); List<TreeNode> rightLongestPath = new ArrayList<TreeNode>(); longestPath(root.getLchild(), leftLongestPath); longestPath(root.getRchild(), rightLongestPath); if (leftLongestPath.size() >= rightLongestPath.size()) { longestPath.addAll(leftLongestPath); } else if (leftLongestPath.size() < rightLongestPath.size()) { longestPath.addAll(rightLongestPath); } } } } /** * listToString: 返回二叉树的结点列表的字符串表示 * * @param nodelist 树的结点列表 * @return 二叉树的结点列表的字符串表示 * */public String listToString(List<TreeNode> nodelist) {if (nodelist == null || nodelist.size() == 0) {return "[ 空树 ]";}StringBuilder str = new StringBuilder("[");Iterator<TreeNode> iter = nodelist.iterator();while (iter.hasNext()) {TreeNode node = iter.next();str.append(node.getCh()+" ");}str.deleteCharAt(str.length()-1);str.append(']');return str.toString();}/** * createBinaryTree: 根据前序和中序遍历列表生成二叉树 * * @param preOrderList 前序列表字符串 * @param inOrderList 中序列表字符串 * @throws Exception * */public static BinaryTree createBinaryTree(String preOrderList, String inOrderList) throws Exception {BinaryTree bt = new BinaryTree(getGeneralList(preOrderList, inOrderList));bt.createBinaryTree();return bt;}/** * getGeneralist: 根据前序和中序遍历列表生成二叉树的广义表表示【字符串形式】 * * @param preOrderList 前序列表字符串 * @param inOrderList 中序列表字符串 * @return generalList 广义表表示 * */private static String getGeneralList(String preOrderList, String inOrderList) {String s = "";if (preOrderList.length() > 0 || inOrderList.length() > 0) {// 如果只含一个结点值，就直接返回if (preOrderList.length() == 1)return preOrderList;// 根据前序遍历， 第一个是根结点的值char ch = preOrderList.charAt(0); // 根据中序遍历及根结点，将前序列表分为左右子树列表。int index = inOrderList.indexOf(ch);String inOrderLeft = inOrderList.substring(0, index); // 左子树的中序遍历列表String inOrderRight = inOrderList.substring(index+1); // 右子树的中序遍历列表String preOrderLeft = preOrderList.substring(1, inOrderLeft.length()+1); // 左子树的前序遍历列表String preOrderRight = preOrderList.substring(inOrderLeft.length()+1); // 右子树的前序遍历列表s += ch;s += "(" + getGeneralList(preOrderLeft,inOrderLeft) + "," + getGeneralList(preOrderRight,inOrderRight) + ")"; }return s;}/** * createBinaryTree: 根据中序和后序遍历列表生成二叉树 * * @param inOrderList 中序列表 * @param postOrderList 后序列表 * @param flag 标记 * * @throws Exception */public static BinaryTree createBinaryTree(String inOrderList, String postOrderList, boolean flag) throws Exception {BinaryTree bt = new BinaryTree(getGeneralList(inOrderList, postOrderList, flag));bt.createBinaryTree();return bt;}/** * getGeneralList: 根据中序和后序遍历生成二叉树的广义表表示【字符串形式】 * * @param inOrderList 中序列表 * @param postOrderList 后序列表 * @param flag 标记 * @return generalList 广义表表示 * */private static String getGeneralList(String inOrderList, String postOrderList, boolean flag) {String s = "";if (inOrderList.length() > 0 || postOrderList.length() >0) {// 如果只含一个结点值，就直接返回if (inOrderList.length() == 1) return inOrderList;// 根据后序遍历规则，最后一个是根结点的值char ch = postOrderList.charAt(postOrderList.length()-1); // 根据中序遍历及根结点，将前序列表分为左右子树列表。int index = inOrderList.indexOf(ch);String inOrderLeft = inOrderList.substring(0, index); // 左子树的中序遍历列表String inOrderRight = inOrderList.substring(index+1); // 右子树的中序遍历列表String postOrderLeft = postOrderList.substring(0, inOrderLeft.length()); // 左子树的前序遍历列表String postOrderRight = postOrderList.substring(inOrderLeft.length(), inOrderLeft.length()+inOrderRight.length()); // 右子树的前序遍历列表s += ch;s += "(" + getGeneralList(inOrderLeft,postOrderLeft,true) + "," + getGeneralList(inOrderRight,postOrderRight,true) + ")"; }return s;}/** * trimSpace: 将广义表表达式字符串中的空格符去掉 */private static String trimSpace(String s){StringBuilder sb = new StringBuilder("");for (int i=0; i < s.length(); i++) {char ch = s.charAt(i);if (!(new Character(ch).toString().matches("//s"))) { sb.append(ch);}}return sb.toString();}/** * separatorIndex : 求解广义表表达式中分割左右子树的分隔符的位置 * 由于这里使用逗号分割左右子树，则当且仅当其位置应当满足： * 在该分割符之前，左括号的数目恰好比右括号的数目多1. * @return 若存在满足条件的分隔符，则返回其位置；否则返回 -1 */private static int separatorIndex(String expression){int leftBracketCounter=0, rightBacketCounter=0;int index = 0;for (; index < expression.length(); index++) {char ch = expression.charAt(index);if (ch == '(') {leftBracketCounter++;}else if (ch == ')') {rightBacketCounter++;}else if (ch == ',') {if (leftBracketCounter == rightBacketCounter+1) break;}}if (index < expression.length()) {return index;}return -1;}}

 

 

 

     [5]  该二叉树程序的用法示例代码：

 

 

      package datastructure.tree;public class BinaryTreeTester {public static void testInvalid(String generalList) {try {BinaryTree.createBinaryTree(generalList);}catch (Exception e) {System.out.println(e.getMessage());}}public static void testTreeInfo(BinaryTree bt) {System.out.println("二叉树的广义表表示：" + bt.getGeneralListString());System.out.println("二叉树高度: " + bt.height(bt.getRoot())); System.out.println("二叉树总结点数： " + bt.size(bt.getRoot())); System.out.println("二叉树总叶子结点数： " + bt.leafCounter(bt.getRoot())); System.out.println("二叉树的所有叶子结点: " + bt.listToString(bt.getLeafNodes())); System.out.println("二叉树的所有叶子结点到根的路径: "); bt.printLeafPaths(); System.out.println("二叉树中的一条最长路径: " + bt.listToString(bt.longestPath()));}public static void testTraverse(BinaryTree bt) {System.out.println("二叉树的结点关联表示："); System.out.println(bt.getNodelinkList());System.out.println("二叉树的先序遍历："); System.out.println("递归: " + bt.listToString(bt.getPreOrderList(true))); System.out.println("非递归: " + bt.listToString(bt.getPreOrderList(false))); System.out.println("二叉树的中序遍历："); System.out.println("递归:" + bt.listToString(bt.getInOrderList(true))); System.out.println("非递归:" + bt.listToString(bt.getInOrderList(false))); System.out.println("二叉树的后序遍历："); System.out.println("递归: " + bt.listToString(bt.getPostOrderList(true))); System.out.println("非递归:" + bt.listToString(bt.getPostOrderList(false))); System.out.println("二叉树的层序遍历："); System.out.println(bt.listToString(bt.getFloorOrderList()));}public static void testAll(BinaryTree bt) {testTreeInfo(bt);testTraverse(bt);}public static void main(String[] args) {String expression = "-( +(a, *(b, -(c,d))), /(e,f)/t)";// String expression = "b( , %)";BinaryTree bt = null;try { bt = BinaryTree.createBinaryTree(expression); testAll(bt); System.out.println(); System.out.println(" ----------- 根据前序及中序遍历列表构造二叉树 ------------ "); bt = BinaryTree.createBinaryTree("ABCDEFG", "CBEDAFG"); testAll(bt); System.out.println(); System.out.println(" ----------- 根据中序及后序遍历列表构造二叉树 ------------ "); bt = BinaryTree.createBinaryTree("CBEDAFG", "CEDBGFA", true); testAll(bt); System.out.println(); System.out.println("复制二叉树: ********************* "); BinaryTree copy = bt.copyBinaryTree(); testAll(copy); System.out.println("************* 二叉树比较： bt VS copy : ****************** "); System.out.println("bt: " + bt.getGeneralListString()); System.out.println("copy: " + copy.getGeneralListString()); System.out.println("比较广义表表示是否相等? " + bt.getGeneralListString().equals(copy.getGeneralListString())); System.out.println("比较给定二叉树是否全等? " + (bt.equalsTo(copy) ? "是": "否")); testInvalid("A(B(C,D)"); testInvalid("A(B,), C(D)"); testInvalid("A(B(C, D),E),F),)"); testInvalid("A(B)"); testInvalid("AB(C,D)"); bt = BinaryTree.createBinaryTree("A(B(D, ), C(E,F))"); testAll(bt); bt.swapTree(); testAll(bt);}catch (Exception e) {System.out.println(e.getMessage());e.printStackTrace();} }} 

 

         [6]  先歇会吧！