树的排序算法 前序 中序 后序
树节点 保存结点值,左子树,右子树
public class TreeNode {
private String value;
private TreeNode left;
private TreeNode right;
public String getValue() {
return value;
}
public void setValue(String value) {
this.value = value;
}
public TreeNode getLeft() {
return left;
}
public void setLeft(TreeNode left) {
this.left = left;
}
public TreeNode getRight() {
return right;
}
public void setRight(TreeNode right) {
this.right = right;
}
public TreeNode(String value, TreeNode left, TreeNode right) {
this.value = value;
this.left = left;
this.right = right;
}
@Override
public String toString() {
return "TreeNode{" +
"value='" + value + '\'' +
", left=" + left +
", right=" + right +
'}';
}
}
初始化一个树形状为
前序 中序 后序排序算法
public class Tree {
private TreeNode root;
private List<TreeNode> result=new ArrayList<TreeNode>();
public TreeNode getRoot() {
return root;
}
public void setRoot(TreeNode root) {
this.root = root;
}
public List<TreeNode> getResult() {
return result;
}
public void setResult(List<TreeNode> result) {
this.result = result;
}
public Tree(){
init();
}
private void init() {
TreeNode g=new TreeNode("G",null,null);
TreeNode x=new TreeNode("X",null,null);
TreeNode y=new TreeNode("Y",null,null);
TreeNode d=new TreeNode("D",x,y);
TreeNode b=new TreeNode("B",d,null);
TreeNode e=new TreeNode("E",g,null);
TreeNode f=new TreeNode("F",null,null);
TreeNode c=new TreeNode("C",e,f);
TreeNode a=new TreeNode("A",b,c);
root=a;
}
/**
* 计算深度
* @param node
* @return
*/
public int calDepth(TreeNode node){
if (node.getLeft()==null&&node.getRight()==null){
return 1;
}
int leftDepth=0;
int rightDepth=0;
if(node.getLeft()!=null){
leftDepth=calDepth(node.getLeft());
}
if(node.getRight()!=null){
rightDepth=calDepth(node.getRight());
}
System.out.println("左"+leftDepth+"右"+rightDepth);
int temp=leftDepth>rightDepth?leftDepth+1:rightDepth+1;
System.out.println("中间计算结果"+temp);
return temp;
}
//前序遍历 根左右
public void perOrder(TreeNode root){
if(root==null){
return;
}
result.add(root);
if(root.getLeft()!=null){
perOrder(root.getLeft());
}
if(root.getRight()!=null){
perOrder(root.getRight());
}
}
//中序遍历 左根右
public void InMiddleOrder(TreeNode root){
if(root==null){
return;
}
if(root.getLeft()!=null){
InMiddleOrder(root.getLeft());
}
result.add(root);
if(root.getRight()!=null){
InMiddleOrder(root.getRight());
}
}
//后序遍历 左右根
public void LastOrder(TreeNode root){
if(root==null){
return;
}
if(root.getLeft()!=null){
LastOrder(root.getLeft());
}
if(root.getRight()!=null){
LastOrder(root.getRight());
}
result.add(root);
}
}
测试程序
public class SearchTree {
public static void main(String[] args) {
Tree tree=new Tree();
System.out.println("根节点"+tree.getRoot().getValue());
//先序遍历
tree.perOrder(tree.getRoot());
System.out.println("树的深度是"+tree.calDepth(tree.getRoot()));
System.out.println("先序遍历结果是:");
for (TreeNode eNode :tree.getResult() ) {
System.out.print(eNode.getValue()+" ");
}
tree.getResult().clear();
tree.InMiddleOrder(tree.getRoot());
System.out.println("中序遍历结果是:");
for (TreeNode eNode :tree.getResult() ) {
System.out.print(eNode.getValue()+" ");
}
tree.getResult().clear();
tree.LastOrder(tree.getRoot());
System.out.println("后序遍历结果是:");
for (TreeNode eNode :tree.getResult() ) {
System.out.print(eNode.getValue()+" ");
}
}
}