树在计算机领域中也有着广泛的应用，例如在编译程序中，用树来表示源程序的语法结构；在数据库系统中，可用树来组织信息；在分析算法的行为时，可用树来描述其执行过程。
本文主要对二叉树进行讨论。并分析二叉树的常用操作及算法，其常用操作有：查找、插入、删除、遍历等。树由一系列的节点有序的组成。下面看节点的定义：
|
package zieckey.datastructure.study.tree;
/**
*
* 树节点定义
* @author zieckey
*
*/
public class Node
{
int iData; // data used as key value
double fData; // other data
Node leftChild; // this node's left child
Node rightChild; // this node's right child
public Node( int data, double data2 )
{
iData = data;
fData = data2;
leftChild = null;
rightChild = null;
}
//拷贝构造函数
public Node( Node n)
{
this.fData = n.fData;
this.iData = n.iData;
this.leftChild = n.leftChild;
this.rightChild = n.rightChild;
}
/**
* 将节点n的值赋给当前节点
* @param n
*/
public void copy( Node n)
{
this.fData = n.fData;
this.iData = n.iData;
this.leftChild = n.leftChild;
this.rightChild = n.rightChild;
}
public String toString()
{
return "("+ iData + ","+fData+")";
}
public void displayNode()
{
System.out.print("("+ iData + ","+fData+") ");
}
}
|
树的Java代码实现：
注意程序中的注释。
|
package zieckey.datastructure.study.tree;
/**
*
* 树及树的常用操作
*
* @author zieckey
*
*/
public class Tree
{
private Node root; // the only data field in Tree
public Tree()
{
root = null;
}
public Node find( int key )
{
Node currentNode = root;
while( currentNode.iData != key )
{
if ( key<currentNode.iData ) //如果key小于当前的值，去左子树找
{
currentNode = currentNode.leftChild;
} else //如果key大于或等于当前的值，去右子树找
{
currentNode = currentNode.rightChild;
}
if ( null == currentNode ) //如果为空，表明没有找到
{
return null;//返回null
}
}
return currentNode; //当前的Node就是要找的对象
}
public void insert( int id, double dd )
{
Node newNode = new Node(id,dd);
if ( null == root )//如果树为空，待插入节点就做为根节点
{
root = newNode;
return;
}
Node currentNode = root;
Node parentNode = currentNode;//parentNode保存待插入节点的位子，即它将成为待插入节点的父节点
while( null != currentNode )
{
parentNode = currentNode;
if ( id<currentNode.iData ) //如果key小于当前的值，去左子树找
{
currentNode = currentNode.leftChild;
} else //如果key大于或等于当前的值，去右子树找
{
currentNode = currentNode.rightChild;
}
}
//while循环完后，parentNode就是待插入节点的父节点
if ( id<parentNode.iData )
{
parentNode.leftChild = newNode;
}else
{
parentNode.rightChild = newNode;
}
}
/**
* 中序遍历树
*
* 若二叉树非空，则依次执行如下操作：
* (1)遍历左子树；
* (2)访问根结点；
* (3)遍历右子树。
*
* @param localRoot
*/
public void inOrderTraveral( Node localRoot )
{
if ( null != localRoot )
{
inOrderTraveral( localRoot.leftChild );
localRoot.displayNode( );
inOrderTraveral( localRoot.rightChild );
}
}
/**
* 找最小节点
* @return 返回最小节点
*/
public Node minimum( )
{
Node currentNode = root, minimumNode = null;
while ( null != currentNode )
{
minimumNode = currentNode;
currentNode = currentNode.leftChild;
}
return minimumNode;
}
/**
* 找最大节点
* @return 返回最大节点
*/
public Node maximum( )
{
Node currentNode = root, maximumNode = null;
while ( null != currentNode )
{
maximumNode = currentNode;
currentNode = currentNode.rightChild;
}
return maximumNode;
}
/**
* 删除节点为key的节点
* @param key
* @return
*/
public boolean delete( int key )
{
Node currentNode = root;
Node parentNode = root;
boolean isLeftChild = true;//如果 currentNode 是 parentNode的左子节点为真，否则为假
while ( currentNode.iData!=key )
{
parentNode = currentNode;
if ( key < currentNode.iData )
{
isLeftChild = true;
currentNode = currentNode.leftChild;
}else
{
isLeftChild = false;
currentNode = currentNode.rightChild;
}
//没有找到待删除的节点
if ( null == currentNode )
{
return false;
}
}//end while
/**
* 已经找到要删除的节点，该节点为 currentNode，其父节点为 parentNode，关系有isLeftChild确定
* 下面分三种情况讨论，分别为currentNode节点有0个、1个、2个子节点
*/
/**
* 第一种情况：
* currentNode没有子节点，分两步处理：
* （1）如果 currentNode == root ，直接 currentNode = null即可
* （2）否则，根据isLeftChild来断开parentNode与currentNode的关系
*/
if ( null == currentNode.leftChild && null == currentNode.rightChild )
{
if ( root == currentNode )
{
root = null;
} else
{
if ( true == isLeftChild )
{
parentNode.leftChild = null;
currentNode = null;
}else
{
parentNode.rightChild = null;
currentNode = null;
}
}
}else if ( null != currentNode.leftChild && null == currentNode.rightChild )//第二种情况，只有一个字节点，且为左节点
{
if ( root == currentNode )
{
root = currentNode.leftChild;
currentNode = null;
} else
{
if ( true == isLeftChild )
{
parentNode.leftChild = currentNode.leftChild;
currentNode = null;
}else
{
parentNode.rightChild = currentNode.leftChild;
currentNode = null;
}
}
}else if ( null == currentNode.leftChild && null != currentNode.rightChild )//第二种情况，只有一个字节点，且为右节点
{
if ( root == currentNode )
{
root = currentNode.rightChild;
currentNode = null;
} else
{
if ( true == isLeftChild )
{
parentNode.leftChild = currentNode.rightChild;
currentNode = null;
}else
{
parentNode.rightChild = currentNode.rightChild;
currentNode = null;
}
}
}else//第三种情况，待删除节点有两个子节点。
{
/**
* 方法一：首先找到待删除节点的后继节点successor，然后根据两种不同的关系分别处理
*
* 后继节点successor与当前待删除节点currentNode有两种关系：
* 1、successor是currentNode的右子节点，即currentNode.rightChild == successor，
* 这个时候currentNode的右子节点没有左子树，这是最简单的情况，作两步处理
* a、successor.leftChild = currentNode.leftChild
* b、让successor代替currentNode成为parentNode的子节点
* 2、successor是currentNode的右子节点的左子树中的某个节点，
* 该情况下，在getSuccessor函数体内部建立了currentNode的子节点与successor的关系
* 所以在此处只需要建立currentNode的父节点与successor节点的关系
*/
/**
* 方法二：首先找到待删除节点的后继节点successor，将后继节点的值拷贝到待删除节点中，再删除掉后继节点。
* 这种方法是投机取巧型的，很实用，但是当节点结果改变时，该方法的代码也需要随之改变。
* 解决这中情况的出现，可以在节点里定义一个拷贝的方法，封装数据，这样就可以了。
*/
//此处用的是方法一，最原始的方法，也是最健壮的方法，
Node successor = getSuccessor( currentNode );//找到待删除节点的后继节点successor
if( root == currentNode )
{
root = successor;
}else if(isLeftChild)
{
parentNode.leftChild = successor;
}
else
{
parentNode.rightChild = successor;
}
successor.leftChild = currentNode.leftChild;
currentNode = null;
}
return true;
}
/**
* 找到delNode的后继节点
* @param delNode
* @return 返回delNode的后继节点
*
* 后继节点successor与当前待删除的delNode节点有两种关系：
* 1、successor是delNode的右子节点，即delNode.rightChild == successor
* 这个时候delNode的右子节点没有左子树，这是简单的情况
* 2、successor是delNode的右子节点的左子树中的某个节点
*/
private Node getSuccessor(Node delNode)
{
Node successor = delNode;//后继节点
Node successorParent = delNode;//后继节点的父节点
Node current = delNode.rightChild;
//找到后继节点
while ( null != current )
{
successorParent = successor;
successor = current;
current = current.leftChild;
}
//如果是第二种情况，顺便建立节点间关系，因为这样更方便
if ( successor != delNode.rightChild )
{
successorParent.leftChild = successor.rightChild;
successor.rightChild = delNode.rightChild;
successor.leftChild = delNode.leftChild;
}
return successor;
}
public Node getRoot()
{
return root;
}
public void setRoot( Node root )
{
this.root = root;
}
}
|
测试程序：
|
package zieckey.datastructure.study.tree;
/**
*
* 测试程序
*
* @author zieckey
*
*/
public class TreeApp
{
/**
* @param args
*/
public static void main( String[] args )
{
// TODO Auto-generated method stub
Tree t = new Tree();
t.insert( 50, 1.5 ); // insert 3 nodes
t.insert( 25, 1.7 );
t.insert( 75, 1.9 );
t.insert( 62, 1.9 );
t.insert( 87, 1.9 );
t.insert( 79, 1.9 );
t.insert( 93, 1.9 );
t.insert( 20, 1.9 );
t.insert( 30, 1.9 );
t.insert( 15, 1.9 );
t.inOrderTraveral( t.getRoot() );
t.delete( 50 );
System.out.println("");
System.out.println( t.getRoot().toString());
t.inOrderTraveral( t.getRoot() );
t.delete( 62 );
System.out.println("");
System.out.println( t.getRoot().toString());
t.inOrderTraveral( t.getRoot() );
// end main()
}
}
|
阅读(4062) | 评论(1) | 转发(0) |
