经典题集之树一

1. 先序遍历
2. 中序遍历
3. 后续遍历
4. 层次遍历
5. 找出二叉树中的最大元素
6. 寻找二叉树中的某个元素
7. 在二叉树中插入元素,插入位置只要满足二叉树要求即可。

package com.dong.Tree;

import java.util.ArrayDeque;
import java.util.Queue;
import java.util.Stack;

import com.dong.Tree.isBalanceTree.Node;

public class ArticleResource {
	static class Node{
		int data;
		Node leftchild;
		Node rightchild;
	}
	//先序遍历递归版
	public void Preorder_Recursive_traversal(Node root) {
		System.out.println(root.data);
		Preorder_Recursive_traversal(root.leftchild);
		Preorder_Recursive_traversal(root.rightchild);
	}
	//先序遍历非递归版
	public void Preorder_No_Recursive_traversal(Node root) {
		Stack<Node> stack = new Stack<Node>();
		Node temp=null;
		stack.push(root);
		while(stack.isEmpty()) {
			temp = (Node) stack.pop();
			if(temp != null) {
				System.out.println(temp.data);
					stack.push(temp.rightchild);
					stack.push(temp.leftchild);
			}
		}
	}
	//中序遍历递归版
	public void In_order_Recursive_traversal (Node root) {
		In_order_Recursive_traversal(root.leftchild);
		System.out.println(root.data);
		In_order_Recursive_traversal(root.rightchild);
	}
	//中序遍历非递归版本
	public void IN_order_NO_Recursive_traversal(Node root) {
		Stack<Node> stack = new Stack<Node>();
		Node p  = root;
		while(!stack.isEmpty()) {
			for(;p!=null;) {
				stack.push(p);
				p = p.leftchild;
			}
			p = stack.pop();
			System.out.println(p.data);
			if(p.rightchild != null)
				p = p.rightchild;
			else
				p = null;
		}
	}
	//后续遍历递归版本
	public void Subsequent_Recursive_traversal(Node root) {
		Subsequent_Recursive_traversal(root.leftchild);
		Subsequent_Recursive_traversal(root.rightchild);
		System.out.println(root.data);
	}
	//后续遍历非递归版本
	public void Subsequent_No_Recursive_traversal(Node root) {
		 Stack<Node> stack = new Stack<Node>();
		 Node p = root;
		 stack.push(p);
		 while(!stack.isEmpty() ||  p!= null) {
			while( p!= null) {
				stack.push(p);
				p = p.leftchild;	
			}
			p = stack.pop();
			System.out.println(p.data);
			if(!stack.empty() && p == stack.peek().leftchild) {
				p = stack.peek().rightchild;
			}else
				p =null;
		    }
	}
	//层次遍历
	public void Hierarchical_traversal(Node root) {
		Queue<Node> q  = new ArrayDeque<Node>();
		q.add(root);
		Node temp ;
		while(!q.isEmpty()) {
			temp = q.poll();
			System.out.println(temp.data);
			if(temp.leftchild != null)
				q.add(temp.leftchild);
			if(temp.rightchild != null) {
				q.add(temp.rightchild);
			}
		}
	}
	//找出二叉树中的最大元素
	public int findMaxElementRecursive(Node root) {
		int root_val,left,right,max =Integer.MIN_VALUE;
		if(root != null) {
			root_val = root.data;
			left = findMaxElementRecursive(root.leftchild);
			right = findMaxElementRecursive(root.rightchild);
			if(left > right)
				max = left;
			else
				max = right;
			if(root_val > max)
				max = root_val;
		}
		return max;
	}
	public int findMaxElementNoRecursive(Node root) {
		Queue<Node> q = new ArrayDeque<Node>();
		int max = Integer.MIN_VALUE;
		Node temp ;
		while(!q.isEmpty()) {
			temp = q.poll();
			if(max < temp.data)
				max = temp.data;
			if(temp.leftchild != null)
				q.add(temp.leftchild);
			if(temp.rightchild != null)
				q.add(temp.rightchild);
		}
		return max;
	}
	//寻找二叉树中的某个元素
	public int findElementRecursive(Node root,int target) {
		if(root == null)
			return 0;
		else {
			if(target == root.data)
				return 1;
			else {			
				int temp = findElementRecursive(root.leftchild, target);
				if(temp == 1 )
					return 1;
				else
					return findElementRecursive(root.rightchild, target);
			}}
		}
	public int findElementNoRecursive(Node root,int target) {
		if(root == null) return 0;
		Queue<Node> q =new  ArrayDeque<Node> ();
		q.add(root);
		Node temp;
		while(!q.isEmpty()) {
			temp = q.poll();
			if(temp.data == target)
				return 1;
			if(temp.leftchild != null)
				q.add(temp.leftchild);
			if(temp.rightchild != null)
				q.add(temp.rightchild);
		}
		return 0;
	}
	//在二叉树中插入元素,插入位置只要满足二叉树要求即可。
	public void insertElement(Node root,int value) {
	
		Queue<Node> q = new ArrayDeque<Node> ();
		Node temp ,newNode;
		newNode = new Node();
		newNode.leftchild = newNode.rightchild = null;
		newNode.data = value;
		if(root == null) {
			root = newNode;
			return;
		}
		q.add(root);
		while(!q.isEmpty()) {
			temp = q.poll();
			if(temp.leftchild != null)
				q.add(temp.leftchild);
			else {
				temp.leftchild = newNode;
				return ;
			}
			if(temp.rightchild != null)
				q.add(temp.rightchild);
			else {
				temp.rightchild = newNode;
				return ;
			}
		}
	}

代码参考《程序员面试手册》