1、树的基本概念
1.1树是什么？
递归：一棵树是N个节点和N-1条边的集合。
1.2树的基本概念
1.2.1节点的定义
每一棵树的根节点叫做根r的儿子，而r是每一棵子树的父亲。
没有儿子的节点称为树叶（leaf）
具有相同父节点的节点称为兄弟
1.2.2树的特点
从节点n1到nk的路径定义为一个序列，使得对于1<=i<=k节点ni是ni+1的父亲，这条路径的长是为该路径上的边的条数，即k-1，从一棵树中从根到每个节点恰好存在一条路径。
对于任意节点ni,ni的深度为从根到ni的唯一的路径长，根的深度为0
ni的高是ni到一片树叶的成长路径的长，所有树叶的高为0，一颗树的高度等于根的高
1.3树的遍历
1.3.1先序遍历：对节点的处理是在节点的诸儿子节点被处理之前进行的（节点，左子树，右子树）
1.3.1后序遍历：对节点的处理是在节点的诸儿子节点被计算后进行的（左子树,右子树，节点）
1.3.1中序遍历：节点按左，节点，右 的顺序打印
2、二叉树
2.1二叉树是什么？
二叉树是一棵树，其中每个节点都不能有多于2个的儿子
2.2二叉树的性质
一棵平均的二叉树的深度要比节点个数N小的多，平均深度为o(/n),深度的平均值是O(logN)
2.2二叉树的实现
public class BinaryNode {
BinaryNode left;//left child
BinaryNode right;//right chid
Object element; //The data in node
}
3、二叉查找树（ADT）
3.1二叉查找树是什么
对于树中的每个节点X，它的左子树中的值小于X中的项，而右子树中所有的项的值大于X中的项，该树所有的元素可以用某一种一致的方式排序。
3.2二叉查找树的性质
二叉树的平均深度是O(logN)
需要一个CompareTo接口
查询复杂度 O(NlogN)
package com.example.springbootdemo;
import java.nio.BufferUnderflowException;
/**
* void insert( x ) --> Insert x
* void remove( x ) --> Remove x
* boolean contains( x ) --> Return true if x is present
* Comparable findMin( ) --> Return smallest item
* Comparable findMax( ) --> Return largest item
* boolean isEmpty( ) --> Return true if empty; else false
* void makeEmpty( ) --> Remove all items
* void printTree( ) --> Print tree in sorted order
*
* @author jingyangTan
* @version lola_4.0
* @since 7月 13, 2020 14:37
*/
public class BinarySearchTree<AnyType extends Comparable<? super AnyType>> {
private BinaryNode<AnyType> root;
AnyType element;
BinaryNode<AnyType> leftNode;
BinaryNode<AnyType> right;
public BinarySearchTree() {
root = null;
}
public boolean isEmpty() {
return root == null;
}
public void insert(AnyType x) {
root = insert(x, root);
}
private static class BinaryNode<AnyType> {
BinaryNode(AnyType element) {
this(element, null, null);
}
AnyType element;
BinaryNode<AnyType> leftNode;
BinaryNode<AnyType> rightNode;
public BinaryNode(AnyType element, BinaryNode<AnyType> leftNode, BinaryNode<AnyType> rightNode) {
this.element = element;
this.leftNode = leftNode;
this.rightNode = rightNode;
}
}
//增
public BinaryNode<AnyType> insert(AnyType x, BinaryNode<AnyType> t) {
if (t == null) {
return new BinaryNode<>(x, null, null);
}
int compareResult = x.compareTo(t.element);
if (compareResult < 0) {
t.leftNode = insert(x, t.leftNode);
} else if (compareResult > 0) {
t.rightNode = insert(x, t.rightNode);
} else {
}
return t;
}
public void remove(AnyType x) {
root = remove(x, root);
}
//删
public BinaryNode<AnyType> remove(AnyType x, BinaryNode<AnyType> t) {
if (t == null) {
return t;
}
int compareResult = x.compareTo(t.element);
if (compareResult < 0) {
t.leftNode = remove(x, t.leftNode);
} else if (compareResult > 0) {
t.rightNode = remove(x, t.rightNode);
} else if (t.leftNode != null && t.rightNode != null) {
t.element = findMin(t.rightNode).element;
t.rightNode = remove(t.element, t.rightNode);
} else {
t = (t.leftNode != null) ? t.leftNode : t.rightNode;
}
return t;
}
//遍历
public void printTree() {
if (isEmpty()) {
System.out.println("Empty Tree");
} else {
printTree(root);
}
}
//是否包含
public boolean contains(AnyType x) {
return contains(x, root);
}
public boolean contains(AnyType x, BinaryNode<AnyType> t) {
if (t == null) {
return false;
}
int compareResult = x.compareTo(x);
if (compareResult < 0) {
return contains(x, t.leftNode);
} else if (compareResult > 0) {
return contains(x, t.rightNode);
} else {
return true;
}
}
public AnyType findMin() {
if (isEmpty()) {
throw new BufferUnderflowException();
}
return findMin(root).element;
}
public BinaryNode<AnyType> findMin(BinaryNode<AnyType> t) {
if (t == null) {
return null;
} else if (t.leftNode == null) {
return t;
} else {
return findMin(t.leftNode);
}
}
public AnyType findMax() {
if (isEmpty()) {
throw new BufferUnderflowException();
}
return findMax(root).element;
}
//查找最大
public BinaryNode<AnyType> findMax(BinaryNode<AnyType> t) {
if (t == null) {
return null;
} else if (t.rightNode == null) {
return t;
} else {
return findMax(t.rightNode);
}
}
private void printTree(BinaryNode<AnyType> t) {
if (t != null) {
printTree(t.leftNode);
System.out.println(t.element);
printTree(t.rightNode);
}
}
private int height(BinaryNode<AnyType> t) {
if (t == null) {
return -1;
} else {
return 1 + Math.max(height(t.leftNode), height(t.rightNode));
}
}
public static void main(String[] args) {
BinarySearchTree<Integer> t = new BinarySearchTree<>();
final int NUMS = 4000;
final int GAP = 37;
System.out.println("Checking... (no more output means success)");
for (int i = GAP; i != 0; i = (i + GAP) % NUMS) {
t.insert(i);
}
for (int i = 1; i < NUMS; i += 2) {
t.remove(i);
}
if (NUMS < 40) {
t.printTree();
}
if (t.findMin() != 2 || t.findMax() != NUMS - 2) {
System.out.println("FindMin or FindMax error!");
}
for (int i = 2; i < NUMS; i += 2) {
if (!t.contains(i)) {
System.out.println("Find error1!");
}
}
for (int i = 1; i < NUMS; i += 2) {
if (t.contains(i)) {
System.out.println("Find error2!");
}
}
}
}
网友评论