数据结构学习笔记之二
数据结构学习笔记之二
注：参考阅读书籍为数据结构-严蔚敏编著 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-ENode 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);// 返回根节点aNodereturn aNode;}/** * @description 递归算法中序遍历二叉树 * @param node */public void diguiInOrder(Node root) {if (root != null) {// 递归左子树diguiInOrder(root.getLeft());// 打印出当前结点valueSystem.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;}}}