算法——二叉树基础遍历与排序

1.二叉树，一种递归的数据结构，一棵非空的二叉树由根节点以及左右子树组成。

且看图：

 

在任一给定结点上，可以按某种次序执行三个操作：

 

   1）访问结点本身（N）

   2）遍历该结点的左子树（L）

   3）遍历该结点的右子树（R）

因此根据这三种操作的先后次序，可分为：

  a）NLR 前序遍历  (PreorderTraversal亦称（先序遍历））——访问根结点的操作发生在遍历其左右子树之前。

  b）LNR 中序遍历  (InorderTraversal）——访问根结点的操作发生在遍历其左右子树之中。

  c）LRN 后序遍历  (PostorderTraversal）——访问根结点的操作发生在遍历其左右子树之后。

什么先根，中根，后根是同一东西。注意，无论哪种次序，每个节点只被访问一次。

以下是示例，基于下图实验：

1.TreeNode.java

package tree;

public class TreeNode {

	public int key;
	public TreeNode leftNode;
	public TreeNode rightNode;
	
	public TreeNode(int key, TreeNode leftNode, TreeNode rightNode) {
		this.key = key;
		this.leftNode= leftNode;
		this.rightNode = rightNode;
	}
}

2.BrinaryTree.java  —— 构造上图的二叉树

        TreeNode leftLeaf1 = new TreeNode(4, null, null);
	TreeNode rightLeaf1 = new TreeNode(5, null, null);
	TreeNode rightLeaf2 = new TreeNode(6, null, null);
		
	TreeNode leftTree = new TreeNode(2, leftLeaf1, rightLeaf1);
	TreeNode rightTree = new TreeNode(3, null, rightLeaf2);
	TreeNode root = new TreeNode(1, leftTree, rightTree);

 

前序算法实现（递归）

/**
	 * 递归前序排列
	 */
	public void recursePostOrder(TreeNode root) {
		if(root == null) return;
		
		root.accessMe();
		if(root.leftNode != null) {
			recursePostOrder(root.leftNode);
		}
		if(root.rightNode != null) {
			recursePostOrder(root.rightNode);
		}
		
	}

 前序算法实现（非递归）

/**
	 * 非递归的前序遍历 
	 */
	public void stackPreOrder(TreeNode root) {
		if(root == null) return;
		
		Stack<TreeNode> stack = new Stack<TreeNode>();
		stack.push(root);
		root.accessMe();
		
		TreeNode tmp = root.leftNode;
		while(tmp != null) {
			stack.push(tmp);
			tmp.accessMe();
			tmp = tmp.leftNode;
		}
		
		tmp = stack.pop();
		while(tmp != null) {
			tmp = tmp.rightNode;
			while(tmp != null) {
				stack.push(tmp);
				tmp.accessMe();
				tmp = tmp.leftNode;
			}
			if(stack.isEmpty()) {
				break;
			}
			tmp = stack.pop();
		}
	}

  

前序结果：1 2 4 5 3 6

中序算法实现（递归）

public void recurseInOrder(TreeNode root) {
		if(root == null) return;
		
		if(root.leftNode != null) {
			recurseInOrder(root.leftNode);
		}
		root.accessMe();
		
		if(root.rightNode != null) {
			recurseInOrder(root.rightNode);
		}
	}

 

中序算法实现（非递归）

/**
	 * 非递归的中序遍历 
	 */
	public void stackInOrder(TreeNode root) {
		if(root == null) return;
		
		Stack<TreeNode> stack = new Stack<TreeNode>();
		stack.push(root);
		
		TreeNode tmp = root.leftNode;
		while(tmp != null) {
			stack.push(tmp);
			tmp = tmp.leftNode;
		}
		
		tmp = stack.pop();
		while(tmp != null) {
			tmp.accessMe();
			tmp = tmp.rightNode;
			while(tmp != null) {
				stack.push(tmp);
				tmp = tmp.leftNode;
			}
			if(stack.isEmpty()) {
				break;
			}
			tmp = stack.pop();
		}
	}

 中序结果：4 2 5 1 3 6

后序算法实现（递归）

/**
	 * 递归后序排列
	 */
	public void recursePostOrder(TreeNode root) {
		if(root == null) return;
		
		if(root.leftNode != null) {
			recursePostOrder(root.leftNode);
		}
		if(root.rightNode != null) {
			recursePostOrder(root.rightNode);
		}
		root.accessMe();
	}

 

后序算法实现（非递归）

/**
	 * 非递归的后序遍历 
	 */
	public void stackPostOrder(TreeNode root) {
		if(root == null) return;
		
		Stack<TreeNode> stack = new Stack<TreeNode>();
		
		TreeNode tmp = root;
		
		while(root!=null){
			
			while(root.leftNode != null) {
				stack.push(root);
				root = root.leftNode;
			}
			
			while(root != null && (root.rightNode == null || root.rightNode == tmp )) {
				root.accessMe();
				tmp = root;
				if(stack.isEmpty()) return;
				root = stack.pop();
				
			}
			
			 stack.push(root);  
	                 root = root.rightNode;  
		}
	}

 后序结果：4 5 2 6 3 1

 

2.排序

   指定的元素插入二叉排序树中

/**
	 * 指定的元素插入二叉排序树中
	 */
	public void insertTree(TreeNode root, int key){
		
		if(root != null) {
			
			int value = root.key;
			
			if(key < value) {
				if(root.leftNode == null) {
					TreeNode node = new TreeNode(key, null, null);
					root.leftNode = node;
				}else {
					insertTree(root.leftNode, key);
				}
			}else if(key > value) {
				if(root.rightNode == null) {
					TreeNode node = new TreeNode(key, null, null);
					node.rightNode = node;
				}else {
					insertTree(root.rightNode, key);
				}
			}
		}else {
			root = new TreeNode(key, null, null);
		}
	}

 

根据key查找某一元素

/**
	 * 根据key查找 
	 */
	public TreeNode searchTree(TreeNode root, int key) {
		if(root == null) {
			return null;
		}else {
			if(key == root.key) {
				return root;
			}else if(key < root.key) {
				return searchTree(root.leftNode, key);
			}else {
				return searchTree(root.rightNode, key);
			}
		}
	}