二叉树遍历与删除

时间：2022-01-03 11:23:36

      前面写过二叉树的节点插入与查找关键数据项以及最值的数据项。二叉树的删除与遍历是另外一项重要的操作。特别是二叉树的人删除比较复杂，分为无子节点的节点删除，只有一个子节点的节点删除和有两个子节点的节点删除三种情况。

1. 删除没有子节点的节点

      这种情况是三种节点删除中最简单的。因为没有子节点的节点删除时只需要将该节点的左或者右节点的引用置为null即可。其他的基本不用变。可以下图表示：

二叉树遍历与删除

原始二叉树，删除数据项82后如下图所示：

二叉树遍历与删除

以下是删除无子节点的节点代码：

        Node current=root;
        Node parent=current;
boolean isLeftChild=true;
//删除没有子节点的节点
while(current.dData!=key)
        {
            parent=current;
if(key<current.iData)
            {
                isLeftChild=true;
                current=current.leftNode;
            }else
            {
                isLeftChild=false;
                current=current.rightNode;
            }
if(current==null)
            {
return false;
            }
        }
if(current.leftNode==null && current.rightNode==null)
        {
if(current == root)//删除整个树
                root=null;
        }else if(isLeftChild)
        {
            parent.leftNode=null;
        }else
            parent.rightNode=null;

2 删除有一个子节点的节点

      这种情况不算复杂，该节点仅有一个子节点表示该节点有两个连接：连向该节点的父节点和连向该节点的子节点。此时删除该节点相当于剪断该引用，直接将该节点的子节点替换为该节点。下图表示这个删除过程：

二叉树遍历与删除
二叉树遍历与删除

删除一个字节点的代码：

//接着以上删除无子节点代码片段
//如果无右子节点，则直接用该节点的父节点的左节点引用该节点的子节点
else if(current.rightChild==null)
if(current == root)
         root = current.leftChild;
else if(isLeftChild)
         parent.leftChild = current.leftChild;
else
         parent.rightChild = current.leftChild;

//如果无左节点，则直接用该节点的父节点右节点引用该节点的子节点
else if(current.leftChild==null)
if(current == root)
         root = current.rightChild;
else if(isLeftChild)
         parent.leftChild = current.rightChild;
else
         parent.rightChild = current.rightChild;

3 删除有两个子节点的节点

      这种删除情况较为复杂，由于二叉树特性，不能直接用下面的子树直接代替该删除的节点，又要考虑树节点特有的顺序。

      这种情况最重要的是找到该删除节点的后继节点。删除有两个子节点的节点，用该节点的中序后继来代替该节点。最主要的是保证树的结构和数据存放顺序。

二叉树遍历与删除

      删除数据项为88的节点，此时应该首先寻找后继节点，很明显此时不能将95开始的父节点子树替代88节点，这样那样就不符合二叉树的规则了。这里数据项90是节点88的后继节点。将90所处的节点代替88所在的节点，90的右子节点引用连接95节点引用即可。

二叉树遍历与删除

       以上表示过程其实是寻找后继节点比较简单的一种，因为当删除的节点所处的树层次较低时（靠近树的顶部位置），此时找到后继节点后构建引用时会非常复杂，因为可能要反转半棵子树。此时已经不是找一个后继节点的事情那么简单了。当后继节点出现了无左子节点时，这情况可以减小删除的复杂度。以上为例，下面以右子树为后继节点，不改变二叉树的结构以及保证树种节点数据的有序。

       原始树的结构。

二叉树遍历与删除

      树节点删除过程。

二叉树遍历与删除

      删除后的树结构：

二叉树遍历与删除

以上关于删除的几种代码如下：

else  
      {
//后继节点有两个子节点的情况
      Node successor = getSuccessor(current);
if(current == root)
         root = successor;
else if(isLeftChild)
         parent.leftChild = successor;
else
         parent.rightChild = successor;
      successor.leftChild = current.leftChild;
      }  

return true;                                
   } 
//获取后继节点
private Node getSuccessor(Node delNode)
   {
   Node successorParent = delNode;
   Node successor = delNode;
   Node current = delNode.rightChild;   // 寻找右节点
while(current != null)               
      {                                 
      successorParent = successor;
      successor = current;
      current = current.leftChild;      // 寻找左节点
      }                               
if(successor != delNode.rightChild)  
      {                                
      successorParent.leftChild = successor.rightChild;
      successor.rightChild = delNode.rightChild;
      }
return successor;
   }

       关于二叉树的删除是一项比较复杂的操作,删除有时候需要考虑其必要性。

关于二叉树删除节点的说明

      很明显二叉树删除节点是一个很复杂的步骤，以上还没有完全列出二叉树删除node的情况，特别是需要反转半棵子树的时候，那就更麻烦了。通常的做法是：先找到需要删除的节点，不做删除动作但是只需要在这个节点处做上删除标志。这样在下一次遍历或者查找的中可以根据删除标志来判断是否显示。用这个办法可以避免删除二叉树节点的复杂操作。

二叉树的遍历

      二叉树的遍历分三种情况，中序遍历，前序遍历以及后序遍历。中序遍历是一种常见的遍历方式。下面给出二叉树的三种方式遍历过程。遍历过程采用递归实现，递归的终止条件是判断节点是否为null，分别对左子节点和右子节点进行遍历。

　前向遍历： 

//前序遍历
//采用递归思想
//对左子节点进行遍历
//对右子节点进行遍历
//递归基值是localRoo是否是null
private void preOrder(Node localRoot)
    {
if(localRoot==null)
        {
return;
        }
else
        {
            System.out.print(localRoot.iData+" ");//输出数据节点信息
            preOrder(localRoot.leftNode);
            preOrder(localRoot.rightNode);
        }
    }

      很明显这种方式遍历首先从root节点开始遍历。

中序遍历

//中序排序
private void inOrder(Node localRoot)
    {
if(localRoot==null)
        {
return;
        }
else
        {
            inOrder(localRoot.leftNode);
            System.out.print(localRoot.iData+" ");
            inOrder(localRoot.rightNode);
        }
    }

后序遍历

 //后序排序
private void postOrder(Node localRoot)
    {
if(localRoot==null)
        {
return;
        }
else
        {
            postOrder(localRoot.leftNode);
            postOrder(localRoot.rightNode);
            System.out.print(localRoot.iData+" ");
        }
    }

      这三种遍历方式的不同仅仅在于输出节点信息的语句位置不同。最主要的就是采用递归对二叉树进行遍历。下面是测试方法：

  public void showTree()
    {
        System.out.println("前序排序");
        preOrder(root);
        System.out.println(" ");
        System.out.println("中序排序");
        inOrder(root);
        System.out.println(" ");
        System.out.println("后序排序");
        postOrder(root);
    }

遍历输出：

前序排序
3 1 2 4 5 6  
中序排序
1 2 3 4 5 6  
后序排序
2 1 6 5 4 3

关于二叉树的效率

      当二叉树是满树时，将近一半的节点在底层，查找与插入删除节点操作大约有一半时间都需要找最底层的节点。二叉搜索操作时间复杂度大致是N以2为底的对数，O（logN），树对所有常用的数据存储操作都有很高的效率。
标签：

相关文章