首先，我们来看一下二叉树结构。
二叉树
二叉树有三种遍历方式：
前序遍历：根左右 ABDCEF
中序遍历：左根右 DBAECF
后序遍历：左右根 DBEFCA
加上逐层遍历：ABCDEF
因此，按照这样的顺序，就有四种不同的代码，具体如下。
class TreeNode
{
public T data;
public TreeNodeleft;
public TreeNoderight;
public TreeNode(T data, TreeNode left, TreeNode right)
{
this.data = data;
this.left = left;
this.right = right;
}
}
public class BinaryTree {
public static void main(String[] args) {
TreeNode D =new TreeNode<>("D",null,null);
TreeNode E =new TreeNode<>("E",null,null);
TreeNode F =new TreeNode<>("F",null,null);
TreeNode B =new TreeNode<>("B",D,null);
TreeNode C =new TreeNode<>("C",E,F);
TreeNode root =new TreeNode<>("A",B,C);
pre(root);
System.out.println();
mid(root);
System.out.println();
bac(root);
System.out.println();
}
//递归后序
private static void bac(TreeNode root) {
if(root !=null){
bac(root.left);
bac(root.right);
System.out.print(root.data+" ");
}
}
//递归中序
private static void mid(TreeNode root) {
if(root !=null){
mid(root.left);
System.out.print(root.data+" ");
mid(root.right);
}
}
//递归前序
private static void pre(TreeNode root) {
if(root !=null){
System.out.print(root.data+" ");
pre(root.left);
pre(root.right);
}
}
//非递归后序
private static void baccir(TreeNode root) {
class NodeFlag{
TreeNodenode;
char tag;
public NodeFlag(TreeNode node, char tag) {
super();
this.node = node;
this.tag = tag;
}
}
Stack>> stack=new Stack>>();
TreeNode p=root;
NodeFlag> bt;
//栈不空或者p不空时循环
while(p!=null || !stack.isEmpty())
{
//遍历左子树
while(p!=null)
{
bt=new NodeFlag(p, 'L');
stack.push(bt);
p=p.left;
}
//左右子树访问完毕访问根节点
while(!stack.isEmpty() && stack.peek().tag=='R')
{
bt=stack.pop();
System.out.print(bt.node.data+" ");
}
//遍历右子树
if (!stack.isEmpty())
{
bt=stack.peek();
bt.tag='R';
p=bt.node;
p=p.right;
}
}
}
//非递归中序
private static void midcir(TreeNode root) {
TreeNode p = root;
Stack> stack =new Stack<>();
while(p!=null||!stack.isEmpty()){
if(p!=null){
stack.push(p);
p = p.left;
}else {
p = stack.pop();
System.out.print(p.data+" ");
p = p.right;
}
}
}
//非递归前序
private static void precir(TreeNode root) {
TreeNode p = root;
Stack> stack =new Stack<>();
while(p!=null||!stack.isEmpty()){
if(p!=null){
stack.push(p);
System.out.print(p.data+" ");
p = p.left;
}else {
p = stack.pop();
p = p.right;
}
}
}
//逐层遍历
private static void printNode(TreeNode root) {
LinkedList> queue =new LinkedList>();
if(root!=null){
queue.add(root);
}
while(!queue.isEmpty()){
root = queue.getFirst();
System.out.print(root.data+" ");
queue.removeFirst();
if(root.left!=null){
queue.add(root.left);
}
if(root.right!=null){
queue.add(root.right);
}
}
}
}
个人公号：【排骨肉段】，可以关注一下。
网友评论