树形结构
相关术语
结点(Node)：表示树中的数据元素，由数据项和数据元素之间的关系组成。在图中，共有10个结点
结点的度(Degree of Node)：结点所拥有的子树的个数，在图中，结点A的度为3
树的度(Degree of Tree)：树中各结点度的最大值。在图中，树的度为3
叶子结点(Leaf Node)：度为0的结点，也叫终端结点。在图中，结点E、F、G、H、I、J都是叶子结点
分支结点(Branch Node)：度不为0的结点，也叫非终端结点或内部结点。在图中，结点A、B、C、D是分支结点
孩子(Child)：结点子树的根。在图中，结点B、C、D是结点A的孩子
双亲(Parent)：结点的上层结点叫该结点的双亲。在图中，结点B、C、D的双亲是结点A
祖先(Ancestor)：从根到该结点所经分支上的所有结点。在图中，结点E的祖先是A和B
子孙(Descendant)：以某结点为根的子树中的任一结点。在图中，除A之外的所有结点都是A的子孙
兄弟(Brother)：同一双亲的孩子。在图5.1中，结点B、C、D互为兄弟
结点的层次(Level of Node)：从根结点到树中某结点所经路径上的分支数称为该结点的层次。根结点的层次规定为1，其余结点的层次等于其双亲结点的层次加1。
堂兄弟(Sibling)：同一层的双亲不同的结点。在图中，G和H互为堂兄弟
树的深度(Depth of Tree)：树中结点的最大层次数。在图5.1中，树的深度为3。
无序树(Unordered Tree)：树中任意一个结点的各孩子结点之间的次序构成无关紧要的树。通常树指无序树。
有序树(Ordered Tree)：树中任意一个结点的各孩子结点有严格排列次序的树。二叉树是有序树，因为二叉树中每个孩子结点都确切定义为是该结点的左孩子结点还是右孩子结点。
森林(Forest)：m(m≥0)棵树的集合。自然界中的树和森林的概念差别很大，但在数据结构中树和森林的概念差别很小。从定义可知，一棵树有根结点和m个子树构成，若把树的根结点删除，则树变成了包含m棵树的森林。当然，根据定义，一棵树也可以称为森林。
二叉树
二叉树是最简单的树形结构，其特点为：
每个节点度可为0、1或者2
子节点分为左子树和右子树，有顺序要区分开来
所以，有如下几个特性：
在二叉树的第i层上最多有2i-1 个节点
二叉树中如果深度为k,那么最多有2k-1个节点
n0=n2+1 n0表示度数为0的节点数，n2表示度数为2的节点数
满二叉树，表示所有的节点都同时拥有左右子树，叶子节点在同一层中，比如：
满二叉树
完全二叉树，表示按从上至下，从左至右的顺序排序，不会出现空位，比如：
图2 完全二叉树
二叉树的存储顺序，是从上到下，从左到右，空置的节点也会耗费空间，比如上面的二叉树都是按照从A到G的顺序存储的
二叉树的java实现
在这里介绍一些java中二叉树的实现的关键点。
定树节点部分：
public class TreeNode
{
private String data = null;// 数据部分，多用两个参数的键值对表示，此处简化为单个值
private TreeNode left;// 左节点的引用
private TreeNode right;// 右节点的引用
//……sth.
}
二叉树的遍历
二叉树的遍历方试有前中后序，对应代码：
/**
* 前序遍历
*
* @param node
*/
public void preOrder(TreeNode node)
{
if (node != null)
{
System.out.println(node.getData());
preOrder(node.getLeft());
preOrder(node.getRight());
}
}
/**
* 中序遍历
*
* @param node
*/
public void inOrder(TreeNode node)
{
if (node != null)
{
inOrder(node.getLeft());
System.out.println(node.getData());
inOrder(node.getRight());
}
}
/**
* 后续遍历
*
* @param node
*/
public void postOrder(TreeNode node)
{
if (node != null)
{
postOrder(node.getLeft());
postOrder(node.getRight());
System.out.println(node.getData());
}
}
我们按照上图中完全二叉树的顺序推演就是前序遍历ABDECF，中序遍历DBEAFC，后序遍历DEBFCA。
还有层次遍历(提供两种类似的实现，请注意考虑空子树的情况)：
public void order(TreeNode node){
Queue<TreeNode> queue= new ArrayBlockingQueue<TreeNode>(20);
queue.add(node);
while(!queue.isEmpty()){
node=queue.poll();
System.out.println(node.getData());
if(node.getLeft()!=null){
queue.add(node.getLeft());
}
if(node.getRight()!=null){
queue.add(node.getRight())
}
}
}
private ArrayList<Integer> list=new ArrayList<Integer>();
public void orderTree2(TreeNode node,int p){
for(int i=0;i<size;i++){
list.add(-1);
}
list.set(p,node.getData());
if(node.getLeft()!=null){
readTree(node.getLeft(),p*2);
}
if(node.getRight()!=null){
readTree(node.getRight(),p*2+1);
}
}
//后者的list就是层次树结构，空位为-1
二叉查找树
当我们开始代入树中的数据时，便诞生了二叉查找树，这是二叉树的基本应用，二叉查找树是满足如下几点条件的二叉树：
若左子树不空，则左子树上所有结点的值均小于它的根结点的值
若右子树不空，则右子树上所有结点的值均大于它的根结点的值
左、右子树也分别为二叉排序树
没有键值相等的节点
例如：
使用时，遍历二叉树，若值大于节点，则遍历右子树，反之左子树，直到查到值或无结果。简单谈一下代码实现：
查找节点：
public Node find(int key) {
Node currentNode = root; //root为定值 记录根节点
while (currentNode != null && currentNode.key != key) {
if (key < currentNode.key) {
currentNode = currentNode.leftChild;
} else {
currentNode = currentNode.rightChild;
}
}
return currentNode;
}
插入节点：
public void insert(int key, int value) {
if (root == null) {
root = new Node(key, value);
return;
}
Node currentNode = root;
Node parentNode = root;
boolean isLeftChild = true;
while (currentNode != null) { //遍历过程 这里需要已经确定key值不在树中
parentNode = currentNode;
if (key < currentNode.key) {
currentNode = currentNode.leftChild;
isLeftChild = true;
} else {
currentNode = currentNode.rightChild;
isLeftChild = false;
}
}
Node newNode = new Node(key, value); //currentNode为空，需插入
if (isLeftChild) {
parentNode.leftChild = newNode;
} else {
parentNode.rightChild = newNode;
}
}
删除节点：
删除节点的操作非常复杂，分为两部分。
public boolean delete(int key) {
Node currentNode = root;//用来保存待删除节点
Node parentNode = root;//用来保存待删除节点的父亲节点
boolean isLeftChild = true;//用来确定待删除节点是父亲节点的左孩子还是右孩子
while (currentNode != null && currentNode.key != key) {
parentNode = currentNode;
if (key < currentNode.key) {
currentNode = currentNode.leftChild;
isLeftChild = true;
} else {
currentNode = currentNode.rightChild;
isLeftChild = false;
}
}
if (currentNode == null) {
return false;
}
if (currentNode.leftChild == null && currentNode.rightChild == null) {//要删除的节点为叶子节点
if (currentNode == root)
root = null;
else if (isLeftChild)
parentNode.leftChild = null;
else
parentNode.rightChild = null;
}else if (currentNode.rightChild == null) {//要删除的节点只有左子树
if (currentNode == root)
root = currentNode.leftChild;
else if (isLeftChild)
parentNode.leftChild = currentNode.leftChild;
else
parentNode.rightChild = currentNode.leftChild;
}else if (currentNode.leftChild == null) {//要删除的节点只有右子树
if (currentNode == root)
root = currentNode.rightChild;
else if (isLeftChild)
parentNode.leftChild = currentNode.rightChild;
else
parentNode.rightChild = currentNode.rightChild;
}else {
//要删除的节点既有左子树又有右子树
}
return true;
}
当要删除的节点含有左右子树时：
//要删除的节点既有左子树又有右子树
//思路：用待删除节点右子树中的key值最小节点的值来替代要删除的节点的值,然后删除右子树中key值最小的节点
//右子树key最小的节点一定不含左子树,所以删除这个key最小的节点一定是属于叶子节点或者只有右子树的节点
Node directPostNode = getDirectPostNode(currentNode);
currentNode.key = directPostNode.key;
currentNode.value = directPostNode.value;
……
private Node getDirectPostNode(Node delNode) {
//方法作用为得到待删除节点的直接后继节点
Node parentNode = delNode;//用来保存待删除节点的直接后继节点的父亲节点
Node direcrPostNode = delNode;//用来保存待删除节点的直接后继节点
Node currentNode = delNode.rightChild;
while (currentNode != null) {
parentNode = direcrPostNode;
direcrPostNode = currentNode;
currentNode = currentNode.leftChild;
}
if (direcrPostNode != delNode.rightChild) {//从树中删除此直接后继节点
parentNode.leftChild = direcrPostNode.rightChild;
direcrPostNode.rightChild = null;
}
return direcrPostNode;//返回此直接后继节点
}
B Tree