JAVA数据结构:二叉树

为什么使用树：

树结合了两种数据结构的有点：一种是有序数组，树在查找数据项的速度和在有序数组中查找一样快；另一种是链表，树在插入数据和删除数据项的速度和链表一样。既然这样，我就要好好去学了....

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

设计前的思考：

树——>元素（节点）

class Node
{
   public int iData ;
   public float fData ;
   public Node left ;
   public Node right ;

   //方法
   public Node(int iData,float fData){}
   public void displayNode(){} 
}

class Tree
{
   Node root ;//树根
 
   //方法
   public void insert(){}
   public void displayTree(){}
   public void find(){}
   public void delete(){}
}

插入数据：

View Code

 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<current.iData)
16                {
17                    current = current.left ;
18                    if(current == null)
19                    {
20                        parent.left = newNode ;
21                        return ;
22                     }
23                }
24                else
25                {
26                    current =current.right ;
27                    if(current == null)
28                    {
29                        parent.right = newNode ;
30                        return ;
31                     }
32                 }
33            }
34        }
35    }

遍历树：

View Code

 1  //中序遍历方法
 2    public void inOrder(Node localRoot)
 3    {
 4        if(localRoot != null)
 5        {
 6            inOrder(localRoot.left) ;//调用自身来遍历左子树
 7            localRoot.displayNode() ;//访问这个节点
 8            inOrder(localRoot.right) ;//调用自身来遍历右子树
 9        }
10    }

查找某个节点：

View Code

 1  //查找某个节点
 2    public Node find(int iData)
 3    {
 4        Node current = root ;
 5        while(current.iData != iData)
 6        {
 7            if(current.iData<iData)
 8               current = current.right ;
 9            else
10               current = current.left ;
11            if(current == null)
12                return null ;
13         }
14        return current ;
15     }

查找树中关键字的最大值和最小值：

最大值：不断地寻找右子节点

最小值：不断地寻找左子节点

View Code

 1 //查找关键字最小的节点
 2    public Node findMinNode()
 3    {
 4        Node current , last ;
 5        last = null ;
 6        current = root ;
 7        if(current.left == null)
 8           return current ;
 9        else
10        {
11             while(current != null)
12            {
13               last = current ;
14               current = current.left ;
15            }
16            return last ;
17        }
18    }

删除某个节点：

思考：

1).先找到要删除的节点：

 1  public boolean delete(int key)
 2    {
 3        //先找到需要删除的节点
 4        Node current = root ;
 5        Node parent = root ;
 6        boolean isLeftChild = false ;
 7        
 8        while(current.iData != key)//显然，当current.iData == key 时，current 就是要找的节点
 9        {
10            parent = current ;
11            if(key < current.iData)
12            {
13                isLeftChild = true ;
14                current = current.left ;
15            }
16            else
17            {
18                isLeftChild = false ;
19                current = current.right ;
20            }
21            if(current == null)//找不到key时返回false
22               return false ;
23        }
24 //continue ........
25 }

2).再考虑要删除的节点是怎样的节点，经分析，有三种情况：叶节点、有一个节点的节点、有两个节点的节点

A).如果删除的是一个叶子节点，直接删除即可

//接上................

 //分情况考虑删除的节点
       //删除的节点为叶节点时
       if(current.left == null && current.right == null)
       {
           if(current == root)
              root = null ;
           else
               if(isLeftChild)
                  parent.left = null ;
               else
                  parent.right = null ;
       }

//continue...........

B).如果删除的节点有一个节点时：分两种情况，删除的节点只有一个左子节点，或者只有一个右子节点

//接上.......
//删除的节点有一个子节点
       else
          if(current.right == null)//删除的节点只有一个左子节点时
          {
              if(current == root)//要删除的节点为根节点
                 root = current.left ;
              else
                  if(isLeftChild)//要删除的节点是一个左子节点
                     parent.left = current.left ;
                  else
                     parent.right = current.left ;//要删除的节点是一个右子节点
          }
          else
              if(current.left == null)//删除的节点只有一个右子节点时
              {
                  if(current == root)//要删除的节点为根节点
                     root = current.right ;
                  else
                      if(isLeftChild)//要删除的节点是一个左子节点
                         parent.left = current.right ;
                      else
                         parent.right = current.right ;//要删除的节点是一个右子节点
              }
//continue.......

c).如果删除的节点有两个节点时：

这种情况就比较复杂，需要去寻找一个节点去替代要删除的节点。这个节点应该是什么节点呢？

据书本介绍，最合适的节点是后继节点，即比要删除的节点的关键值次高的节点是它的后继节点。

说得简单一些，后继节点就是比要删除的节点的关键值要大的节点集合中的最小值。

以上面的为例，40的后继节点为74,10的后继节点是13,19的后继节点时26

以下是寻找后继节点的代码：

 1 //返回后继节点
 2    private Node getSuccessor(Node delNode)
 3    {
 4        Node successorParent = delNode ;//后继节点的父节点
 5        Node successor = delNode ;//后继节点
 6        Node current = delNode.right ;//移动到位置节点位置
 7        while(current != null)
 8        {
 9            successorParent = successor ;
10            successor = current ;
11            current = current.left ;
12        }
13        if(successor != delNode.right)
14        {
15           successorParent.left = successor.right ;
16           successor.right = delNode.right ;
17        }
18        return successor ;
19    }

找到了后继节点，接着就要讨论如何用后继节点替代药删除的节点

a)如果后继节点是刚好是要删除节点的右子节点（此时可以知道，这个右子节点没有左子点，如果有，就不该这个右子节点为后继节点）

//要删除的节点为左子节点时
parent.left = successor ;
successor.left = current.left ;

//要删除的节点是右子节点时
parent.right = successor ;
successor.left = current.left ;

b)如果后继节点为要删除节点的右子节点的左后代：

//假如要删除的节点为右子节点
successorParent.left = successor.right ;//第一步
successor.right = current.right ;//第二步
parent.right = successor ;
successor.left = current.left ;

//假设要删除的节点为左子节点
successorParent.left = successor.right ;
successor.right = current.right ;
parent.left = successor ;
successor.left = current.left ;

注意：第一步和第二步在getSuccessor()方法的最后的if语句中完成

以下是删除的节点有连个节点的代码：

 1 //接上 
 2 //删除的节点有两个子节点
 3               else
 4               {
 5                   Node successor = getSuccessor(current) ;//找到后继节点
 6                   if(current == root)
 7                      root = successor ;
 8                   else
 9                       if(isLeftChild)
10                          parent.left = successor ;
11                       else
12                          parent.right = successor ;
13                   successor.left = current.left ;
14               }
15 //continue....

综合上述，给出delete()方法的代码：

View Code

 1 //删除某个节点
 2    public boolean delete(int key)
 3    {
 4        //先找到需要删除的节点
 5        Node current = root ;
 6        Node parent = root ;
 7        boolean isLeftChild = false ;
 8        
 9        while(current.iData != key)//显然，当current.iData == key 时，current 就是要找的节点
10        {
11            parent = current ;
12            if(key < current.iData)
13            {
14                isLeftChild = true ;
15                current = current.left ;
16            }
17            else
18            {
19                isLeftChild = false ;
20                current = current.right ;
21            }
22            if(current == null)//找不到key时返回false
23               return false ;
24        }
25        
26        //分情况考虑删除的节点
27        //删除的节点为叶节点时
28        if(current.left == null && current.right == null)
29        {
30            if(current == root)
31               root = null ;
32            else
33                if(isLeftChild)
34                   parent.left = null ;
35                else
36                   parent.right = null ;
37        }
38        //删除的节点有一个子节点
39        else
40           if(current.right == null)//删除的节点只有一个左子节点时
41           {
42               if(current == root)//要删除的节点为根节点
43                  root = current.left ;
44               else
45                   if(isLeftChild)//要删除的节点是一个左子节点
46                      parent.left = current.left ;
47                   else
48                      parent.right = current.left ;//要删除的节点是一个右子节点
49           }
50           else
51               if(current.left == null)//删除的节点只有一个右子节点时
52               {
53                   if(current == root)//要删除的节点为根节点
54                      root = current.right ;
55                   else
56                       if(isLeftChild)//要删除的节点是一个左子节点
57                          parent.left = current.right ;
58                       else
59                          parent.right = current.right ;//要删除的节点是一个右子节点
60               }
61               //删除的节点有两个子节点
62               else
63               {
64                   Node successor = getSuccessor(current) ;//找到后继节点
65                   if(current == root)
66                      root = successor ;
67                   else
68                       if(isLeftChild)
69                          parent.left = successor ;
70                       else
71                          parent.right = successor ;
72                   successor.left = current.left ;
73               }
74        return true ;
75    }

进一步考虑：

删除那么复杂，那删除是必要的吗?我们可以给每个节点定义一个标志，该标志用于记录该节点是否已经删除了，

显示树时，先判断该节点是否已经删除，如果没有，则显示。

这样的结果是，节点其实是没有删除的，这样显然逃避责任了。当树中没有那么多的删除操作时，这也不失为一种好方法，例如：

已经离职的员工的档案要永久地保存在员工的记录中。

OVER.....( ^_^ )