漫话二叉树之递归遍历算法(两种不同的思路)

· 结点的度：一个结点的子树的个数记为该结点的度． 

· 树的度：所有节点中度数最大的结节的度数，叶子节点的度为零。 

· 树的高度：一棵树的最大层次数记为树的高度(或深度)。 

· 有序(无序)树：若将树中结点的各子树看成是从左到右具有次序的，即不能交换，则称该树为有序树。否则称为无序树。 

· 二叉树第i层（i≥1）上至多有2^(i-1)个节点。 

· 深度为k的二叉树至多有2^k-1个节点（k≥1）。 

· 对任何一棵二叉，若叶子节点数为n0，度为2的节点数为n2，则n0=n2+1。 

· 具有n个节点的完全二叉树的深度为 (㏒2^n)(向下取整)+1。 

· 对一棵有n个节点的完全二叉树的节点按层次从上到下，自左至右进行编号，则对任一节点i(1≤i≤n)有：若 i=1，则节点i是二叉树的根，无双亲；若 i>1，则其双亲为 i/2(向下取整)。若2i>n，则节点i没有孩子节点，否则其左孩子为2i。若2i+1>n，则节点i没有右孩子，否则其右孩子为2i+1。 

· 若深度为k的二叉树有2^k-1个节点，则称其为满二叉树。满二叉树是一棵完全二叉树。 

· 对于完全二叉树中，度为1的节点个数只可能为1个或0个。 

· 对于二叉树，如果叶子节点数为n0，度为1的节点数为n1，度为2的节点数为n2，则节点总数n = n0 + n1 + n2。 

· 对于任意树，总节点数 = 每个节点度数和 + 1 

· 二叉树的高度等于根与最远叶节点（具有最多祖先的节点）之间分支数目。空树的高度是-1。只有单个元素的二叉树，其高度为0。

3.说完性质谈遍历

今天讨论的重点就在于此，在二叉树的一些应用中，常常要求在树中查找具有某种特征的结点或者对树中全部结点逐一进行某种处理。这就提出了一个遍历二叉树的问题，即如何按某条搜索路径巡访树中每个结点使得每个结点均被访问一次而且仅被访问一次。遍历对线性结构来说，是一个容易解决的问题而对二叉树则不然，由于二又树是一种非线性结构，每个结点都可能有两棵子树，因而需要寻找一种规律，以便使二又树上的结点能排列在一个线性队列上，从而便于访问。

First：谈一下二叉树的遍历方式~

二叉树的遍历分为前序遍历，中序遍历和后序遍历。

⑴ 前序遍历（ DLR）二叉树的操作定义为：
若二叉树为空，则空操作；否则
① 访问根结点；
② 先序遍历左子树；
③ 先序遍历右子树。
⑵ 中序遍历（ LDR）二叉树的操作定义为：
若二叉树为空，则空操作；否则
① 中序遍历左子树；
② 访问根结点；
③ 中序遍历右子树。
⑶ 后序遍历（ LRD）二叉树的操作定义为：
若二叉树为空，则空操作；否则
① 后序遍历左子树；
② 后序遍历右子树；
③ 访问根结点。
下面先以一棵二叉树表示一个算术表达式，然后对其进行遍历。以二叉树表示表达式的递归定义如下：若表达式为数或简单变量，则相应二叉树中仅有一个根结点；若表达式=（第一操作数）（运算符）（第二操作数），则相应二叉树用左子树表示第一操作数，用右子树表示第二操作数，根结点存放运算符。例如图 6-6（ a）所示的二叉树表示下述表达式
a＋ (b－ c)×d－ e／ f
如果对该二叉树进行三种遍历，分别得到的遍历序列如下
先序遍历：－ ＋ a × － b c d ／ e f
中序遍历： a ＋ b － c × d － e ／ f
后序遍历： a b c － d × ＋ e f ／ －
从表达式上看，以上三个序列正好是表达式的前缀表示（波兰式）、中缀表示和后缀表示（逆波兰式）。在计算机中，使用后缀表达式易于求值。后缀表达式的代码请参考我的数据结构与算法(二)，同时也有前缀表达式与后缀表达式的转换代码~~
给大家看一张图将会更方便理解：

上述遍历的过程显然是一个递归的过程~

二叉树的递归其实很容易实现，但是为了显示我的认真负责任的态度，我将给大家两个不同思路的代码，不同点在于构造树和遍历方式的不同。next~~

代码1：

import java.util.Stack;

public class TreeApp {
	protected node root;
	
	/** 构造一棵树 **/
	public static node init() {
		node a = new node('A', null, null);
		node b = new node('B', null, a);
		node c = new node('C', null, null);
		node d = new node('D', b, c);
		node e = new node('E', null, null);
		node f = new node('F', e, null);
		node g = new node('G', null, f);
		node h = new node('H', d, g);
		return h;// root
	}

	// 访问结点
	public static void visitKey(node p) {
		System.out.println(p.getKey() + "    ");
	}

	// 递归实现前序遍历 (根左右) prefix(前缀) 
	public static void prefixOrder(node p) {
		if (p != null) {
			visitKey(p);
			prefixOrder(p.getLeft());
			prefixOrder(p.getRight());
		}
	}
	
	// 递归实现中序遍历(左根右) infix(中缀)  
	protected static void infixOrder(node p) {
		if (p != null) {
			infixOrder(p.getLeft());
			visitKey(p);
			infixOrder(p.getRight());
		}
	}
	
	// 递归实现后序遍历(左右根) postfix(后缀) 
	protected static void postfixOrder(node p) {
		if (p != null) {
			postfixOrder(p.getLeft());
			postfixOrder(p.getRight());
			visitKey(p);
		}
	}
	
	public static void main(String[] args) {  
		System.out.println("递归实现二叉树遍历");
		postfixOrder(init());
	}
}

class node {
	private char key;
	private node left, right;

	public node(char key, node left, node right) {
		this.key = key;
		this.left = left;
		this.right = right;
	}

	public char getKey() {
		return key;
	}

	public void setKey(char key) {
		this.key = key;
	}

	public node getLeft() {
		return left;
	}

	public void setLeft(node left) {
		this.left = left;
	}

	public node getRight() {
		return right;
	}

	public void setRight(node right) {
		this.right = right;
	}
}

代码的含义很清晰，不做解释，下面是代码2

public class Node {
    public Node left; // 左子结点
    public Node right; // 右子结点
    public int value; // 结点值

    public Node(int value) {
        this.value = value;
    }

    public Node() {
    }
    
    // 前序遍历
    public static void preTraversal(Node node) {
        if (node != null) {
            System.out.print(node.value+" "); //输出当前结点值
        }
        if (node.left != null) {
            preTraversal(node.left); //读左结点
        }
        if (node.right != null) {
            preTraversal(node.right); // 读右结点
        }
    }
    
    // 中序遍历
    public static void midTraversal(Node node){
        if(node.left != null){
            midTraversal(node.left);
        }
        if(node != null){
            System.out.print(node.value+" ");
        }
        if(node.right != null){
            midTraversal(node.right);
        }
    }
    
    // 后序遍历
    public static void behTraversal(Node node){
        if(node.left != null){
            behTraversal(node.left);
        }
        if(node != null){
            System.out.print(node.value+" ");
        }
        if(node.right != null){
            behTraversal(node.right);
        }
    }
    public static void main(String[] args) {
        // 初始化5个结点,值分别为: 1,2,3,4,5
        Node n1 = new Node(1);
        Node n2 = new Node(2);
        Node n3 = new Node(3);
        Node n4 = new Node(4);
        Node n5 = new Node(5);
        Node n6 = new Node(); // 值默认为0
        Node n7 = null;
        
        System.out.println("n6 = "+n6); 
        System.out.println("n7 = "+n7); // null
        
        // 构建二叉树, 以n1为根结点
        n1.left = n2;
        n1.right = n5;
        n2.left = n3;
        n2.right = n4;
        n5.left = n6;
        n5.right = n7;
        
        System.out.print("前序遍历结果为: ");
        preTraversal(n1); 
        System.out.println();
        System.out.print("中序遍历结果为: ");
        midTraversal(n1);
        System.out.println();
        System.out.print("后序遍历结果为: ");
        behTraversal(n1);
    }
}

5.At Last... 二叉树是一种很重要的操作，而递归遍历不过是很简单的一部分，非递归遍历、查找结点、插入结点、删除结点的实现要比表的一些操作实现起来复杂的多，但后面将会对以上几点进行完成~