二叉树排序 前序、中序、后序 （递归和非递归） 以及 层序

前序---->根左右

中序----->左根右

后序------>左右根

图片.png

前序遍历为： 124758369

中序遍历为： 742851693

后序遍历为： 748529631

层序遍历为：123456789

public class TreeNode{
  private String data;
  private TreeNode left;
  private TreeNote right;
  public TreeNode(String data, TreeNode left, TreeNode right) {
        this.data = data;
        this.left = left;
        this.right = right;
    }
//省略  get  set
}

• 使用递归方式进行排序

//前序
public void pre(TreeNode t){
  print(t.getData())；
  if(t.getLeft()!= null){
    pre(t.getLeft());
  }
  if(t.getRight()!= null){
    pre(t.getRight());
  }
}

//中序
public void mid(TreeNode t){
  if(t.getLeft()!= null){
    mid(t.getLeft());
  }
  print(t.getData())；
  if(t.getRight()!= null){
    mid(t.getRight());
  }
}
//后序
public void rear(TreeNode t){
  if(t.getLeft()!= null){
    rear(t.getLeft());
  }
  if(t.getRight()!= null){
    rear(t.getRight());
  }
  print(t.getData())；
}

• 非递归实现

//前序
public List<String> pre(TreeNode t){
  List<String> list = new ArrayList<>();
  Stack<TreeNode> stack = new Stack<>();
  if(t!= null){
    stack.push(t);
    while(!stack.isEmpty()){
      TreeNode pop = stack.pop();
      list.add(pop.getData());
      if(pop.getRight()!=null){
        stack.push(pop.getRight());
      }
      if(pop.getLeft()!=null){
        stack.push(pop.getLeft());
      }
    }
  }
  return list;
}

//中序
public void mid(TreeNode t){
  List<String> list = new ArrayList<>();
  Stack<TreeNode> stack = new Stack<>();
  TreeNode cur=t;
  if(cur!= null){
    while(!stack.isEmpty()||cur!= null){
      while(cur!= null){
        stack.push(cur);
        cur = cur.getLeft();
      }
      TreeNode pop = stack.pop();
      list.add(pop.getData());
      cur = pop.getRight();
    }
  }
  return list;
}
//后序
public List<String> rear(TreeNode t){
  List<String> list = new ArrayList<>();
  Stack<TreeNode> stack = new Stack<>();
  TreeNode cur=t;
  TreeNode re = null;
  if(cur!= null){
    while(!stack.isEmpty()||cur!=null){
      if(cur!= null){
        stack.push(cur);
        cur = cur.getLeft();
      }else{
        TreeNode pop = stack.peek();
        if(pop.getRight()!=null && pop.getRight != re){
          cur = pop.getRight();
          stack.push(cur);
          cur = cur.getLeft();
        }else{
          cur = stack.pop();
          list.add(cur.getData());
          re = cur;
          cur = null;
        }
      }
    }
  }
  return list;
}

• 层序遍历

public List<String> level(TreeNode t){
  Queue<TreeNode> queue = new LinkedList<>();
  if(t!= null){
    queue.add(t);
  }
  List<String> list = new ArrayList<>();
  while(!queue.isEmpty()){
    TreeNode poll = queue.poll();
    if(poll.getLeft()!= null){
      queue.add(poll.getLeft());
    }
    if(poll.getRight()!=null){
      queue.add(poll.getRight());
    }
  }
  return list;
}