数据结构学习笔记之二

数据结构学习笔记之二
注：参考阅读书籍为数据结构-严蔚敏编著 2011/11/29 下午

第六章：树和二叉树
一、树的定义和基本操作
1、树的特点
   树是一个结点n的有限集，在任意一颗树非空树中：1、有且只有一个根结点，2、当n>1时，其余结点分为m(m>0)个互不相交的有限集，其中每个集合本身又是一棵树，叫做根的子树。
   关键词组：有限集、唯一性、对称性、递归性。
   基本术语：结点、度、叶子、分支结点、孩子、双亲、兄弟、层次以及深度等。
   基本操作：构造初始化树、取得左子树或右子树、插入结点、删除结点、树的遍历等等。
2、线性结构VS树结构
   线性结构是一个“序列”，元素之间存在的是“一对一”的关系，而树是一个层次结构，元素之间存在的是“一对多”的关系。
二、二叉树的定义
1、二叉树的特点
   每个结点至多只有二棵子树（即二叉树中不存在度大于2的结点），并且二叉树的子树有左右之分，其次序不能颠倒。
   关键词组：对称、次序
2、二叉树的具体实例
   满二叉树、完全二叉树、平衡二叉树等，具体区别参考书籍教材详解。
3、二叉树的存储结构
   主要分为两种方式，一类是顺序结构（可使用一组地址连续的存储单元依次自上而下、自左至右存储完全二叉树上的结点元素），另外一类是链式存储结构，这两种存储方式各有利弊，具体要看实际操作的场合。
4、二叉树的遍历方式
   遍历方案有先序遍历、中序遍历、后序遍历，具体的算法实现有递归的算法和非递归的算法。二叉树线索化初步了解，待有需要再进一步编码实战。
三、树的应用实例
1、树和森林
   树的存储表示方式主要有三种：双亲表示法、孩子表示法以及孩子兄弟法。树和森林之间的相互转换也比较简单，不过多分析。
2、树的应用
   （1）树的等价问题：离散数学中引入的等价和等价类的概念
   （2）赫夫曼树及其应用（赫夫曼树又叫最优二叉树）
   （3）回溯法与树的遍历
   （4）树的计数
四、代码实战参考题目
   1、构造/初始化一颗二叉树
   2、递归/非递归中序遍历该二叉树
   3、二叉树和森林的相互转换模拟实现 //具体看存储的方式，比如孩子兄弟法
   4、对平衡二叉树进行增加、删除结点操作
   补充：参考学习资料：http://justsee.iteye.com/blog/1106693赫夫树、赫夫曼编码实现
  学习代码如下：

import java.util.Stack;
/**
 * @author Administrator
 * 
 * @description 二叉树类
 * @history
 */
public class BinaryTree {
	/**
	 * 根节点root
	 */
	private Node root;
	/**
	 *@description 获取根节点方法
	 *@return 返回根节点
	 */
	public Node getRoot() {
		return root;
	}
	/**
	 *@description 结点参数的构造方法
	 *@param node
	 */
	public BinaryTree(Node node){
		this.root = node;
	}
	/**
	 * @description 构造/初始化二叉树结点
	 * @return
	 */
	public static Node initTree() {
		// 初始化五个结点A-E
		Node aNode = new Node('A');
		Node bNode = new Node('B');
		Node cNode = new Node('C');
		Node dNode = new Node('D');
		Node eNode = new Node('E');
		// 设置左右子结点关系
		aNode.setLeft(bNode);
		aNode.setRight(cNode);
		bNode.setLeft(dNode);
		bNode.setRight(eNode);
		// 返回根节点aNode
		return aNode;
	}
	/**
	 * @description 递归算法中序遍历二叉树
	 * @param node
	 */
	public void diguiInOrder(Node root) {
		if (root != null) {
			// 递归左子树
			diguiInOrder(root.getLeft());
			// 打印出当前结点value
			System.out.print(root.getValue()+" ");
			// 递归右子树
			diguiInOrder(root.getRight());
		}
	}
	/**
	 * @description 采用栈实现中序遍历二叉树
	 * @param root
	 */
	public void stackInOrder(Node root) {
		if (root == null) return; // 返回不处理
		
		// 采用单个栈的实现方法，多栈实现有空再学习
		Stack<Node> stack = new Stack<Node>();
		Node node = root;
		
		// 根结点入栈、循环条件为stack不为空
		stack.push(node);
		while (!stack.empty()) {
			// 入栈操作、一直遍历到最左边那个结点
			while (node.getLeft() != null) {
				stack.push(node.getLeft());
				node = node.getLeft();
			}
			// 退栈操作、遍历退栈当前结点的右子树
			if (!stack.empty()) {
				node = stack.pop();
				System.out.print(node.getValue()+" ");
				
				// 如果当前退栈结点右子树不为null，入栈右结点
				if (node.getRight() != null) {
					stack.push(node.getRight());
					node = node.getRight(); // 设置node为右结点
				}
			}
		}
	}
	/**
	 * @description
	 * @param args
	 */
	public static void main(String[] args) {
		// 构造初始化二叉树、递归算法实现中序遍历
		Node root = initTree(); 
		BinaryTree bt = new BinaryTree(root); 
		bt.diguiInOrder(root);  // D B E A C
		
		// 非递归算法中序遍历
		bt.stackInOrder(root); 
		
	}
	/**
	 * @description 结点类、静态内部类
	 * @history
	 */
	private static class Node {
		private char value;
		private Node left;
		private Node right;
		/**
		 *@description value参数构造方法
		 */
		public Node(char value){
			this.value = value;
		}
		/**
		 *@description getter、setter方法实现
		 *@return
		 */
		public Node getLeft() {
			return left;
		}
		public char getValue() {
			return value;
		}
		public void setValue(char value) {
			this.value = value;
		}
		public void setLeft(Node left) {
			this.left = left;
		}
		public Node getRight() {
			return right;
		}
		public void setRight(Node right) {
			this.right = right;
		}
	}

}