二叉树的三种遍历-er-cha-shu-de-san-zhong-bian-li.md

焦虑烧麦 148 2022-05-02
import java.util.LinkedList;
import java.util.List;



public class BinTreeTraverse {
	private int arr[]={1,2,3,4,5,6,7};
	private static List<Node> nodeList=null;
	private static class Node{
		Node leftchild;
		Node rightchild;
		int data;
		Node(int newdata){
			leftchild=null;
			rightchild=null;
			data=newdata;
		}
		
	}
	public void createBintree(){//新建一个二叉树
		nodeList=new LinkedList<Node>();
		for (int nodIndex = 0; nodIndex < arr.length; nodIndex++) {
			nodeList.add(new Node(arr[nodIndex]));
		}
		//以下定义主要依据上面讲解的第五条的特性实现
		for (int parentIndex = 0; parentIndex < arr.length/2-1; parentIndex++) {
			//左孩子
			nodeList.get(parentIndex).leftchild=nodeList.get(parentIndex*2+1);
			//右孩子
			nodeList.get(parentIndex).rightchild=nodeList.get(parentIndex*2+2);
		}
		//最后一个父节点,因为最后一个父节点可能没有右孩子,所以单独拿出来处理
		int lastParentIndex=arr.length/2-1;
		//左孩子
		nodeList.get(lastParentIndex).leftchild=nodeList.get(lastParentIndex*2+1);
		if (arr.length%2==1) {
			nodeList.get(lastParentIndex).rightchild=nodeList.get(lastParentIndex*2+2);
		}
	}
	 /** 
     * 先序遍历 
     *  
     * 这三种不同的遍历结构都是一样的,只是先后顺序不一样而已 
     *  
     * @param node 
     * 遍历的节点 
     */  
    public static void preOrderTraverse(Node node) {  
        if (node == null)  
            return;  
        System.out.print(node.data + " ");  
        preOrderTraverse(node.leftchild);  
        preOrderTraverse(node.rightchild);  
    }  
  
    /** 
     * 中序遍历 
     *  
     * 这三种不同的遍历结构都是一样的,只是先后顺序不一样而已 
     *  
     * @param node 
     *            遍历的节点 
     */  
    public static void inOrderTraverse(Node node) {  
        if (node == null)  
            return;  
        inOrderTraverse(node.leftchild);  
        System.out.print(node.data + " ");  
        inOrderTraverse(node.rightchild);  
    }  
  
    /** 
     * 后序遍历 
     *  
     * 这三种不同的遍历结构都是一样的,只是先后顺序不一样而已 
     *  
     * @param node 
     *            遍历的节点 
     */  
    public static void postOrderTraverse(Node node) {  
        if (node == null)  
            return;  
        postOrderTraverse(node.leftchild);  
        postOrderTraverse(node.rightchild);  
        System.out.print(node.data + " ");  
    }  
  
    public static void main(String[] args) {  
        BinTreeTraverse binTree = new BinTreeTraverse();  
        binTree.createBintree();  
        // nodeList中第0个索引处的值即为根节点  
        Node root = nodeList.get(0);  
  
        System.out.println("先序遍历:");  
        preOrderTraverse(root);  
        System.out.println();  
  
        System.out.println("中序遍历:");  
        inOrderTraverse(root);  
        System.out.println();  
  
        System.out.println("后序遍历:");  
        postOrderTraverse(root);  
    }  
	
}

运行结果:

先序遍历:
1 2 4 5 3 6 7 
中序遍历:
4 2 5 1 6 3 7 
后序遍历:
4 5 2 6 7 3 1