树是一些节点的集合。这些集合可以是空集，如果不是空集，那么树则由称作根的节点r以及0个或多个非空的树T1、T2.....Tk组成。
如图没有儿子的节点称为树叶；具有相同父亲的节点称为兄弟；
深度：对于任意的节点ni,从根到ni的唯一路径的长。
高：从ni到一片树叶的最长路径的长。
遍历
先序遍历：若树为空则返回空，否则先访问根节点，然后先序遍历左子树，然后先序遍历又子树。上图先序遍历的结果：A->B->D->E->C->F
后序遍历：若二叉树为空，则返回空，否则按照从左到右先叶子结点后节点，最后根节点的方式的方式访问。上图后序遍历的结果：D->E->B->F->C->A。
中序遍历：若二叉树为空，则返回空。否则从根节点开始（注意不是先访问根节点），中序遍历根节点的左子树，然后根节点然后中序遍历根节点的右子树。上图中序遍历的结果：D->B->E->A->F->C。
从上可知除去父节点，子节点的访问三种遍历方式都是从左到右。
二叉树
二叉树是一棵树，其中每个节点都不能有多余两个的儿子。
二叉查找树：二叉查找树又称为二叉排序树或者二叉搜索树。它具有以下的性质：
- 若左子树不为空，则其左子树上的值都下小于或者等于根节点的值；
- 若右子树不为空，则右子树上的所有值均大于或者等于根节点的值；
- 左右子树也分别为儿二叉排序树。
二叉查找树的实现：
package structures;
/**
* 二叉查找树
*/
public class BinarySearchTree<E extends Comparable<? super E>>{
private BinaryNode<E> root;
public BinarySearchTree() {
this.root = null;
}
public BinarySearchTree(BinaryNode<E> root) {
this.root = root;
}
public void makeEmpty(){
this.root = null;
}
public boolean isEmpty(){
return this.root == null;
}
public boolean contains(E ele){
return contains(ele, root);
}
public E findMax() throws Exception {
if(isEmpty()){
throw new Exception();
}
return findMax(root).element;
}
public E findMin() throws Exception {
if(isEmpty()){
throw new Exception();
}
return findMin(root).element;
}
public void insert(E ele){
root = insert(ele,root);
}
public void remove(E e){
root = remove(e, root);
}
public void printTree(){
if(isEmpty()){
System.out.println("empty tree");
}else{
printTree(root);
}
}
private void printTree(BinaryNode<E> root) {
if(null!=root){
//使用的中序遍历
printTree(root.left);
System.out.println(root.element);
printTree(root.right);
}
}
private BinaryNode<E> remove(E e, BinaryNode<E> root) {
if(null == root){
return root;
}
int compareResult = e.compareTo(root.element);
if(compareResult<0){
root.left = remove(e, root.left);
}else if(compareResult>0){
root.right = remove(e, root.right);
}else if(null!=root.left && null!=root.right){
root.element = findMin(root.right).element;
root.right = remove(root.element, root.right);
}else{
root = (null!=root.left)?root.left:root.right;
}
return root;
}
private BinaryNode<E> insert(E ele, BinaryNode<E> root) {
if(null == root){
return new BinaryNode<E>(ele);
}
int compareResult = ele.compareTo(root.element);
if(compareResult<0){
root.left = insert(ele, root.left);
}else if(compareResult>0){
root.right = insert(ele, root.right);
}else{
//ele==root.element do nothing;
}
return root;
}
private BinaryNode<E> findMin(BinaryNode<E> root) {
if(null!=root){
while(null!=root.left){
root = root.left;
}
}
return root;
}
private BinaryNode<E> findMax(BinaryNode<E> root) {
if(root != null){
while (null!=root.right){
root = root.right;
}
}
return root;
}
private boolean contains(E ele, BinaryNode<E> root) {
if(null == root){
return false;
}
int compareResult = ele.compareTo(root.element);
if(compareResult<0){
return contains(ele, root.left);
}else if(compareResult>0){
return contains(ele, root.right);
}else{
return true;
}
}
/**
* 内部类
* @param <E>
*/
private static class BinaryNode<E>{
public BinaryNode(E element) {
//this.element = element;
this(element, null, null);
}
public BinaryNode(E element, BinaryNode<E> left, BinaryNode<E> right) {
this.element = element;
this.left = left;
this.right = right;
}
E element;
BinaryNode<E> left;
BinaryNode<E> right;
}
}
第一部分树的简介及二插树先写到这里，后面再写二叉平衡树和伸展树等。