Java数据结构与算法之树[整理].pdf

1 / 13

Java 数据结构与算法之树

为什么使用树：

树结合了两种数据结构的有点：一种是有序数组，树在查找数据项的速度和在有序数组中查找一样快；另一种是链表，树

在插入数据和删除数据项的速度和链表一样。既然这样，就要好好去学了 ....

(最主要讨论的是二叉树中的二叉搜索树，即一个节点的左子节点关键值小于这个节点，右子节点的关键值大于这个节点 )

设计前的思考：

树—— > 元素（节点）

class Node

public Node( int iData, float fData){}

public void displayNode(){}

}

2 / 13

class Tree

{

Node root ; // 树根

// 方法

public void insert(){}

public void displayTree(){}

public void find(){}

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 ;

21 return ;

22 }

23 }

24 else

25 {

3 / 13

26 current =current.right ;

27 if (current == null )

28 {

29 parent.right = newNode ;

30 return ;

31 }

32 }

33 }

34 }

遍历树：

1 // 中序遍历方法

2 public void inOrder(Node localRoot)

9 }

10 }

查找某个节点：

1 // 查找某个节点

2 public Node find( int iData)

3 {

4 Node current = root ;

5 while (current.iData != iData)

6 {

7 if (current.iData<iData)

14 return current ;

15 }