文档介绍：Java数据结构与算法之树—动力节点
Java数据结构不算法之树 为什么使用树:
树结合了两种数据结构的有点:一种是有序数组,树在查找数据项的速度和在有序数组中查找一样快;另一种是链表,树
在插入数据和删除数据项的速度和链表一样。既然这样,就要好好去学了.... (最主要讨论的是二叉树中的二叉搜索树,即一个节点的左子节点关键值小于这个节点,右子节点的关键值大于这个节点)
设计前的思考:
树——>元素，节点，
class Node
{
public int iData ;
public float fData ;
public Node left ;
public Node right ;
//方法
public Node(int iData,float fData){}
public void displayNode(){} }
1 / 13
class Tree
{
Node root ;//树根
//方法
public void insert(){}
public void displayTree(){}
public void find(){}
public void delete(){}
}
插入数据:
1 //插入子节点
2 public void insert(int iData ,float fData)
3 {
4 Node newNode = new Node(iData,fData) ;
5
6 if(root == null)
7 root = newNode ;
8 else
9 {
10 Node current = root ; 11 Node parent ; 12 while(true)//寻找插入的位置
13 {
14 parent = current ; 15 if(iData<) 16 {
17 current = ;
18 if(current == null)
19 {
20 = newNode ;
21 return ;
22 }
23 }
24 else
25 {
2 / 13
26 current = ;
27 if(current == null)
28 {
29 = newNode ;
30 return ;
31 }
32 }
33 }
34 }
35 }
遍历树:
1 //中序遍历方法
2 public void inOrder(Node localRoot)
3 {
4 if(localRoot != null)
5 {
6 inOrder() ;//调用自身来遍历左子树
7 () ;//访问这个节点
8 inOrder() ;//调用自身来遍历右子树
9 }
10 }
查找某个节点:
1 //查找某个节点
2 public Node find(int iData)
3 {
4 Node current = root ;
5 while( != iData)
6 {
7 if(<iData)
8 current = ;
9 else
10 current = ;
11 if(current == null)
12 return null ;
13 }
14 return current ;
15 }
3 / 13
查找树中关键字的最大值和最小值:
最大值:不断地寻找右子节点
最小值:不断地寻找左子节点
1 //查找关键字最小的节点
2 public Node findMinNode()
3 {
4 Node current , last ;
5 last = null ;
6 current = root ;
7 if( == null)
8 return current ;
9 else
10 {
11 while(current != null)
12 {
13 last = curre