Java版数据结构与算法读书笔记（三）

树
树是n个节点的有限集，n=0时称为空树，在任意一棵非空树中，有且仅有一个根节点。每个节点最多只有一个父节点。

节点拥有的子树数称为节点的度，度为0的节点称为页子节点或者中断节点。树的度是树内各节点的度的最大值。

层次与深度
节点的层次从根开始定义，根为第一层，跟的孩子为第二层。树中节点的最大层次称为树的深度或高度。

树的存储结构，简单的顺序存储不能满足树的实现，需要结合顺序存储和链式存储来实现。

二叉树是由一个根节点和两棵互不相交的，分别称为根节点的左子树和右子树的二叉树组成。

满二叉树指的是在一棵二叉树中，所有分支节点都存在左子树和右子树，并且叶子节点都在同一层上。
完全二叉树，可以直接用顺序结构，比如数组存储。

二叉树的遍历
前序遍历
根，左，右

import java.util.Stack;


public class BinaryTree {
	
	private TreeNode root = null;
	
	
	public BinaryTree(){
		root = new TreeNode(1,"A");
	}
	
	/**
	 * 构建二叉树
	 *         A
	 *      B     C
	 *   D    E      F
	 */
	
	public void createBinaryTree(){
		TreeNode nodeB = new TreeNode(2,"B");
		TreeNode nodeC = new TreeNode(3,"C");
		TreeNode nodeD = new TreeNode(4,"D");
		TreeNode nodeE = new TreeNode(5,"E");
		TreeNode nodeF = new TreeNode(6,"F");
		
		root.leftChild = nodeB;
		root.rightChild = nodeC;
		nodeB.leftChild = nodeD;
		nodeB.rightChild = nodeE;
		nodeC.rightChild = nodeF;
	}
	
	
	/*
	 * 
	 * 求二叉树的高度
	 * 节点到页子节点的最大值
	 * 
	 */
	public int getHeight(){
		return getHeight(root);
	}
	
	private int getHeight(TreeNode node) {
		if(node == null){
			return 0;
		}else{
			int i = getHeight(node.leftChild);
			int j = getHeight(node.rightChild);
			return (i<j)?i+1:j+1;
		}
		
	}
	
	/**
	 * 
	 * 
	 * 获取二叉树的节点数
	 *
	 */
	public int getSize(){
		return getSize(root);
	}

	private int getSize(TreeNode node) {
		// TODO Auto-generated method stub
		if(node == null){
			return 0;
		}else{
			return 1 + getSize(node.leftChild) + getSize(node.rightChild);
		}
	}
	
	/**
	 * 
	 * 前序遍历
	 * 
	 *
	 */
	public void preOrder(TreeNode node){
		if(node == null){
			return;
		}else{
			System.out.println(node.data);
			preOrder(node.leftChild);
			preOrder(node.rightChild);
		}
	}
	
	/**
	 * 
	 * 前序非迭代
	 * 
	 */
	public  void nonPreOrder(TreeNode node){
		Stack<TreeNode> s = new Stack<TreeNode>();
		s.push(node);
		while(!s.isEmpty()){
			TreeNode temp = s.pop();
			System.out.println(temp.data);
			if(temp.rightChild!=null){
				s.push(temp.rightChild);
			}
			if(temp.leftChild!=null){
				s.push(temp.leftChild);
			}
		}
	}
	
	/**
	 * 
	 * 中序遍历
	 * 
	 *
	 */
	public void midOrder(TreeNode node){
		if(node == null){
			return;
		}else{
			midOrder(node.leftChild);
			System.out.println(node.data);
			midOrder(node.rightChild);
		}
	}
	
	/**
	 * 
	 * 中序非递归
	 * 核心思想，找到最左节点，一次压入栈中，然后遍历他的右子树
	 * 
	 */
	public void nonMidOrder(TreeNode node){
		Stack<TreeNode> s = new Stack<TreeNode>();
		TreeNode p = node;
		while(p!=null || !s.isEmpty()){
			while(p!=null){
				s.push(p);
				p = p.leftChild;
			}
			p = s.pop();
			System.out.println(p.data);
			if(p.rightChild!=null){
				p = p.rightChild;
			}else{
				p = null;
			}
		}
	}

	
	/**
	 * 
	 * 后序遍历
	 * 
	 *
	 */
	public void postOrder(TreeNode node){
		if(node == null){
			return;
		}else{
			postOrder(node.leftChild);
			postOrder(node.rightChild);
			System.out.println(node.data);
		}
	}
	
	/**
	 * 
	 * 后序遍历非递归
	 * 
	 *
	 */
	public void NonPostOrder(TreeNode node){
		Stack<TreeNode> s = new Stack<TreeNode>();
		TreeNode p = node;
		while(p!=null || !s.isEmpty()){
			while(p!=null){
				s.push(p);
				p = p.leftChild;
			}
			p = s.pop();
			System.out.println(p.data);
			if(!s.isEmpty()&& p == s.peek().leftChild){
				p = s.peek().rightChild;
			}else{
				p = null;
			}
		}
	}





	public class TreeNode{
		private int index;
		private String data;
		private TreeNode leftChild;
		private TreeNode rightChild;
		
		public TreeNode(int index,String data){
			this.index = index;
			this.data = data;
			this.leftChild = null;
			this.rightChild = null;
		}

		public int getIndex() {
			return index;
		}

		public void setIndex(int index) {
			this.index = index;
		}

		public String getData() {
			return data;
		}

		public void setData(String data) {
			this.data = data;
		}
		
		
	}
	
	public static void main(String[] args){
		BinaryTree bt = new BinaryTree();
		bt.createBinaryTree();
		bt.getHeight();
//		bt.preOrder(bt.root);
//		bt.nonRecOrder(bt.root);
//		bt.midOrder(bt.root);
//		bt.nonMidOrder(bt.root);
		bt.postOrder(bt.root);
		bt.NonPostOrder(bt.root);
	}

}