- 二叉树是一个比较难搞的问题,但是通过递归实现就代码就比较简单(但是递归需要自己理解,可以通过画图来帮助自己理解)。
- 二叉树的遍历比存储简单,下面的代码也会手动建立一个二叉树,并且创建求他结点个数和二叉树深度的方法,都用到了递归。
- 二叉树里面包括前中后序的遍历,用到递归,方法里面内容相近,主要是输出语句的位置不同。
具体看代码:
package pt; import java.util.Arrays; public class BinaryCharTree { char value; BinaryCharTree leftChild; BinaryCharTree rightChild; public BinaryCharTree(char paraName) { value = paraName; leftChild = null; rightChild = null; }// of the constructor public static BinaryCharTree manualConstructorTree() { // Step 1. Construct a tree with only one node. BinaryCharTree resultTree = new BinaryCharTree('a'); // Step 2. Construct all nodes. The first node is the root. // BinaryCharTreeNode tempTreeA=resultTree.root. BinaryCharTree tempTreeB = new BinaryCharTree('b'); BinaryCharTree tempTreeC = new BinaryCharTree('c'); BinaryCharTree tempTreeD = new BinaryCharTree('d'); BinaryCharTree tempTreeE = new BinaryCharTree('e'); BinaryCharTree tempTreeF = new BinaryCharTree('f'); BinaryCharTree tempTreeG = new BinaryCharTree('g'); // step 3.link all nodes. resultTree.leftChild = tempTreeB; resultTree.rightChild = tempTreeC; tempTreeB.rightChild = tempTreeD; tempTreeC.leftChild = tempTreeE; tempTreeD.leftChild = tempTreeF; tempTreeD.rightChild = tempTreeG; return resultTree; } public void preOrderVisit() { System.out.println("" + value + " "); if (leftChild != null) { leftChild.preOrderVisit(); } // of if if (rightChild != null) { rightChild.preOrderVisit(); } // of if }// of preOrderVisit public void inOrderVisit() { if (leftChild != null) { leftChild.inOrderVisit(); } // of if System.out.println("" + value + " "); if (rightChild != null) { rightChild.postOrderVisit(); } // of if }// of inOrderVisit public void postOrderVisit() { if (leftChild != null) { leftChild.postOrderVisit(); } // of if if (rightChild != null) { rightChild.postOrderVisit(); } // of if System.out.println("" + value + " "); } public int getDepth() { // It is a leaf. if ((leftChild == null) && (rightChild == null)) { return 1; } // of if // The depth of the left child. int tempLeftDepth = 0; if (leftChild != null) { tempLeftDepth = leftChild.getDepth(); } // of if // The depth of the right child. int tempRightDepth = 0; if (rightChild != null) { tempRightDepth = rightChild.getDepth(); } // of if // The depth should increment by 1. if (tempLeftDepth >= tempRightDepth) { return tempLeftDepth + 1; } else { return tempRightDepth + 1; } // of if }// of getDepth public int getNumNodes() { // It is a leaf. if ((leftChild == null) && (rightChild == null)) { return 1; } // of if // The number of nodes of the left child. int tempLeftNodes = 0; if (leftChild != null) { tempLeftNodes = leftChild.getNumNodes(); } // of if // The number of nodes of the right child. int tempRightNodes = 0; if (rightChild != null) { tempRightNodes = rightChild.getNumNodes(); } // of if // The total number of nodes. return tempLeftNodes + tempRightNodes + 1; }// of gerNumbders public static void main(String args[]) { BinaryCharTree tempTree = manualConstructorTree(); System.out.println("rnPreorder visit:"); tempTree.preOrderVisit(); System.out.println("rnIn-order visit:"); tempTree.inOrderVisit(); System.out.println("rnPost-order visit:"); tempTree.postOrderVisit(); System.out.println("rnrnThe depth is: " + tempTree.getDepth()); System.out.println("The number of nodes is: " + tempTree.getNumNodes()); }// of main }// of BinaryCharTree
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)