一、概述
1.1、树的概念
树状图是一种数据结构，它是由n（n>=1）个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点：
每个节点有零个或多个子节点；没有父节点的节点称为根节点；每一个非根节点有且只有一个父节点；除了根节点外，每个子节点可以分为多个不相交的子树
1.2、树的定义
树（tree）是包含n（n>0）个结点的有穷集，其中：
（1）每个元素称为结点（node）；
（2）有一个特定的结点被称为根结点或树根（root）。
（3）除根结点之外的其余数据元素被分为m（m≥0）个互不相交的集合T1，T2，……Tm-1，其中每一个集合Ti（1<=i<=m）本身也是一棵树，被称作原树的子树（subtree）。
树也可以这样定义：树是由根结点和若干颗子树构成的。树是由一个集合以及在该集合上定义的一种关系构成的。集合中的元素称为树的结点，所定义的关系称为父子关系。父子关系在树的结点之间建立了一个层次结构。在这种层次结构中有一个结点具有特殊的地位，这个结点称为该树的根结点，或称为树根。
我们可以形式地给出树的递归定义如下:
单个结点是一棵树，树根就是该结点本身。
设T1,T2,…,Tk是树，它们的根结点分别为n1,n2,…,nk。用一个新结点n作为n1,n2,…,nk的父亲，则得到一棵新树，结点n就是新树的根。我们称n1,n2,…,nk为一组兄弟结点，它们都是结点n的子结点。我们还称T1,T2,…,Tk为结点n的子树。
空集合也是树，称为空树。空树中没有结点。
二、二叉树
2.1、概述
在计算机科学中，二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用于实现二叉查找树和二叉堆。
二叉树的每个结点至多只有二棵子树(不存在度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒。二叉树的第i层至多有2{i-1}个结点；深度为k的二叉树至多有2k-1个结点；对任何一棵二叉树T，如果其终端结点数为n_0，度为2的结点数为n_2，则n_0=n_2+1。
一棵深度为k，且有2^k-1个节点称之为满二叉树；深度为k，有n个节点的二叉树，当且仅当其每一个节点都与深度为k的满二叉树中，序号为1至n的节点对应时，称之为完全二叉树。
2.2、二叉树实现
看到上面的概念之后，下面将进行二叉树数据结构的实现
2.2.1、二叉树抽象类
BinaryTreeADT.java:
package sihai;import java.util.Iterator;/*** BinaryTreeADT是二叉树的抽象接口**/public interface BinaryTreeADT<T> {/** *返回根节点元素**/public T getRootElement();/** * 判断二叉树是否为空*/public boolean isEmpty();/** * 返回二叉树中元素的数量*/public int size();/** * 判断二叉树中是否存在特定的目标元素*/public boolean contains(T targetElement);/** * 查找目标元素** @param targetElement 在二叉树中查找的元素*/public T find(T targetElement);/** * */public String toString();/** * 返回这颗树的迭代器*/public Iterator<T> iterator();/** * 中序遍历*/public Iterator<T> iteratorInOrder();/** * 前序遍历 */public Iterator<T> iteratorPreOrder();/** * 后序遍历*/public Iterator<T> iteratorPostOrder();/** * 层次遍历 */public Iterator<T> iteratorLevelOrder();}
2.2.2、二叉树的节点类
package sihai;/*** 二叉树节点类，包括左节点和右节点，本身节点元素* */public class BinaryTreeNode<T>{protected T element;protected BinaryTreeNode<T> left, right;/*** 创建一个特定值得节点** @param obj 新的节点的元素*/public BinaryTreeNode(T obj) {element = obj;left = null;right = null;}/*** 创建一个特定值得节点** @param obj 新的节点的元素* @param left 节点的左子树* @param right 节点的右子树*/public BinaryTreeNode(T obj, LinkedBinaryTree<T> left, LinkedBinaryTree<T> right) {element = obj;if (left == null)this.left = null;elsethis.left = left.getRootNode();if (right == null)this.right = null;elsethis.right = right.getRootNode();}/*** 节点总数**/public int numChildren() {int children = 0;if (left != null)children = 1 + left.numChildren();if (right != null)children = children + 1 + right.numChildren();return children;}/*** 返回节点元素**/public T getElement() {return element;}/***返回节点的右节点*/public BinaryTreeNode<T> getRight() {return right;}/*** 设置节点的右节点*/public void setRight(BinaryTreeNode<T> node) {right = node;}/***返回节点的左节点*/public BinaryTreeNode<T> getLeft() {return left;}/*** 设置节点的左节点*/public void setLeft(BinaryTreeNode<T> node) {left = node;}}
通过上面的二叉树的抽象类和节点类，大概的二叉树的数据结构已经出来了，下面我们再讨论二叉树的另外一种实现，看看如何用链表来实现二叉树。
三、用链表实现二叉树
链表二叉树实现了BinaryTreeADT接口的LinkedBinaryTree类，需要跟踪位于树的根节点，一节树的元素数目。
package sihai;import java.util.*;import jsjf.exceptions.*;/*** 链表二叉树实现二叉树接口*/public class LinkedBinaryTree<T> implements BinaryTreeADT<T>, Iterable<T>{protected BinaryTreeNode<T> root; //二叉树根节点protected int modCount;/*** 创建空的链接二叉树*/public LinkedBinaryTree() {root = null;}/*** 创建一个带有特定元素的节点作为二叉树的根** @param 根节点的元素*/public LinkedBinaryTree(T element) {root = new BinaryTreeNode<T>(element);}/*** 创建一个带有特定元素的节点作为二叉树的根，并且设置其左子树和右子树** @param 根元素* @param 树的左子树* @param 树的右子树*/public LinkedBinaryTree(T element, LinkedBinaryTree<T> left, LinkedBinaryTree<T> right) {root = new BinaryTreeNode<T>(element);root.setLeft(left.root);root.setRight(right.root);}/*** 返回根节元素*/public T getRootElement() throws EmptyCollectionException{// TODO}/***返回根节点*/protected BinaryTreeNode<T> getRootNode() throws EmptyCollectionException{//TODO}/*** 返回树的根节点的左子树**/public LinkedBinaryTree<T> getLeft(){//TODO}/*** 返回树的根节点的右子树**/public LinkedBinaryTree<T> getRight(){//TODO}/*** 判断二叉树是否为空**/public boolean isEmpty() {return (root == null);}/*** 返回树的大小**/public int size() {// TODO}/*** 返回树的高度**/public int getHeight(){//TODO}/*** 返回特定节点的树的高度**/private int height(BinaryTreeNode<T> node) {//TODO}/*** 判断树是否包含目标元素*/public boolean contains(T targetElement) {// TODO}/*** 根据目标元素查找节点*/public T find(T targetElement) throws ElementNotFoundException{BinaryTreeNode<T> current = findNode(targetElement, root);if (current == null)throw new ElementNotFoundException("LinkedBinaryTree");return (current.getElement());}/***根据特定的元素查找目标节点*/private BinaryTreeNode<T> findNode(T targetElement, BinaryTreeNode<T> next){if (next == null)return null;if (next.getElement().equals(targetElement))return next;BinaryTreeNode<T> temp = findNode(targetElement, next.getLeft());if (temp == null)temp = findNode(targetElement, next.getRight());return temp;}public String toString() {// TODO}/*** 返回中序遍历迭代器**/public Iterator<T> iterator(){return iteratorInOrder();}public Iterator<T> iteratorInOrder(){ArrayUnorderedList<T> tempList = new ArrayUnorderedList<T>();inOrder(root, tempList);return new TreeIterator(tempList.iterator());}/*** 中序遍历*/protected void inOrder(BinaryTreeNode<T> node, ArrayUnorderedList<T> tempList) {if (node != null){inOrder(node.getLeft(), tempList);tempList.addToRear(node.getElement());inOrder(node.getRight(), tempList);}}/*** 前序遍历*/public Iterator<T> iteratorPreOrder() {//TODO}/*** 前序遍历*/protected void preOrder(BinaryTreeNode<T> node, ArrayUnorderedList<T> tempList) {// TODO}/*** 后序遍历*/public Iterator<T> iteratorPostOrder() {// TODO}/*** 后序遍历*/protected void postOrder(BinaryTreeNode<T> node, ArrayUnorderedList<T> tempList) {// TODO}/*** 层次遍历*/public Iterator<T> iteratorLevelOrder() {ArrayUnorderedList<BinaryTreeNode<T>> nodes = new ArrayUnorderedList<BinaryTreeNode<T>>();ArrayUnorderedList<T> tempList = new ArrayUnorderedList<T>();BinaryTreeNode<T> current;nodes.addToRear(root);while (!nodes.isEmpty()) {current = nodes.removeFirst();if (current != null){tempList.addToRear(current.getElement());if (current.getLeft() != null)nodes.addToRear(current.getLeft());if (current.getRight() != null)nodes.addToRear(current.getRight());}elsetempList.addToRear(null);}return new TreeIterator(tempList.iterator());}/*** 表示树的元素的迭代器的内部类*/private class TreeIterator implements Iterator<T>{private int expectedModCount;private Iterator<T> iter;public TreeIterator(Iterator<T> iter){this.iter = iter;expectedModCount = modCount;}public boolean hasNext() throws ConcurrentModificationException{if (!(modCount == expectedModCount))throw new ConcurrentModificationException();return (iter.hasNext());}public T next() throws NoSuchElementException{if (hasNext())return (iter.next());else throw new NoSuchElementException();}public void remove(){throw new UnsupportedOperationException();}}}
四、二叉树的应用
我们都知道用栈算法可以实现后缀表达式的计算，但是，其实用二叉树也是可以同样实现的，下面就创建一个ExpressionTree类来对这一算法进行实现。
在这之前，我们需要一个ExpressionTreeOp的操作辅助类，这个类可以跟踪记录该元素是一个数字还是一个操作符，以及该处存储的是哪个操作符或是什么值。
ExpressionTreeOp.java:
package sihai;/*** 表达式树的操作类*/public class ExpressionTreeOp {private int termType;private char operator;private int value;/*** 创建一个新的操作表达式树** @param type 元素类型* @param op 操作符* @param val 操作值*/public ExpressionTreeOp(int type, char op, int val) {termType = type;operator = op;value = val;}/*** 判断是否是运算符*/public boolean isOperator() {return (termType == 1);}/***返回运算符*/public char getOperator() {return operator;}/***返回值*/public int getValue() {return value;}public String toString(){if (termType == 1) return operator + "";elsereturn value + "";}}
下面就是表达式树的类
ExpressinTree.java：
package sihai;/*** 表示一个表达式树的操作数的操作值得*/public class ExpressionTree extends LinkedBinaryTree<ExpressionTreeOp>{public ExpressionTree() {super();}/*** 创建一个有左子树和右子树的表达式树*/public ExpressionTree(ExpressionTreeOp element,ExpressionTree leftSubtree, ExpressionTree rightSubtree) {root = new BinaryTreeNode<ExpressionTreeOp>(element, leftSubtree, rightSubtree);}/*** 评测表达式树*/public int evaluateTree() {return evaluateNode(root);}/*** 评测节点*/public int evaluateNode(BinaryTreeNode root) {int result, operand1, operand2;ExpressionTreeOp temp;if (root==null)result = 0;else{temp = (ExpressionTreeOp)root.getElement();if (temp.isOperator()){operand1 = evaluateNode(root.getLeft());operand2 = evaluateNode(root.getRight());result = computeTerm(temp.getOperator(), operand1, operand2);}elseresult = temp.getValue();}return result;}/*** 计算表达式的值*/private static int computeTerm(char operator, int operand1, int operand2){int result=0;if (operator == '+')result = operand1 + operand2;else if (operator == '-')result = operand1 - operand2;else if (operator == '*')result = operand1 * operand2;else result = operand1 / operand2;return result;}/*** 打印树*/public String printTree() {UnorderedListADT<BinaryTreeNode<ExpressionTreeOp>> nodes = new ArrayUnorderedList<BinaryTreeNode<ExpressionTreeOp>>();UnorderedListADT<Integer> levelList = new ArrayUnorderedList<Integer>();BinaryTreeNode<ExpressionTreeOp> current;String result = "";int printDepth = this.getHeight();int possibleNodes = (int)Math.pow(2, printDepth + 1);int countNodes = 0;nodes.addToRear(root);Integer currentLevel = 0;Integer previousLevel = -1;levelList.addToRear(currentLevel);while (countNodes < possibleNodes) {countNodes = countNodes + 1;current = nodes.removeFirst();currentLevel = levelList.removeFirst();if (currentLevel > previousLevel){result = result + "\n\n";previousLevel = currentLevel;for (int j = 0; j < ((Math.pow(2, (printDepth - currentLevel))) - 1); j++)result = result + " ";}else{for (int i = 0; i < ((Math.pow(2, (printDepth - currentLevel + 1)) - 1)) ; i++) {result = result + " ";}}if (current != null){result = result + (current.getElement()).toString();nodes.addToRear(current.getLeft());levelList.addToRear(currentLevel + 1);nodes.addToRear(current.getRight());levelList.addToRear(currentLevel + 1);}else {nodes.addToRear(null);levelList.addToRear(currentLevel + 1);nodes.addToRear(null);levelList.addToRear(currentLevel + 1);result = result + " ";}}return result;}}
