二叉树的遍历与删除（递归实现）

1.引言

这一段时间都没看java数据结构，松懈了。今天记录下二叉树的遍历，建树，删除节点。下一章 会用非递归的方式实现一下。

2.正题

新建一个TreeNode类：

public class TreeNode {

    private String tag;
    private int number;
    private TreeNode leftNode;
    private TreeNode rightNode;
    //自己实现get、set
}

---

2.1 建立二叉树

递归参数：等待插入的节点A，父节点B（假如插入成功）
核心思想：假如A.number<B.number。表示在B的左边。然后在判断B.leftNode 是否为null；为null，就将A插进入，不为null，就进行递归。同理A.number>B.number一样。

实现代码：

   public TreeNode rootNode;
   public void buildTree(TreeNode treeNode,TreeNode binaryTree){
       if (rootNode==null){
          rootNode=treeNode;
          rootNode.setLeftNode(null);
          rootNode.setRightNode(null);
          return;
       }
       if (treeNode.getNumber()<binaryTree.getNumber()){
           if (binaryTree.getLeftNode()!=null){
               buildTree(treeNode,binaryTree.getLeftNode());
           }else {
               binaryTree.setLeftNode(treeNode);
           }
       }else {
           if (binaryTree.getRightNode()!=null){
               buildTree(treeNode,binaryTree.getRightNode());
           }else {
               binaryTree.setRightNode(treeNode);
           }
       }
   }

main函数：

BinaryTree binaryTree=new BinaryTree();
       List<TreeNode>treeNodes=new ArrayList<>();
       treeNodes.add(new TreeNode("A",6));
       treeNodes.add(new TreeNode("B",3));
       treeNodes.add(new TreeNode("C",7));
       treeNodes.add(new TreeNode("D",1));
       treeNodes.add(new TreeNode("E",4));
       treeNodes.add(new TreeNode("F",9));
       treeNodes.forEach(treeNode -> {binaryTree.buildTree(treeNode,binaryTree.rootNode);});

2.2前序遍历

递归参数：TreeNode
核心思想：先输出当前节点的tag，然后判断是否存在左节点。存在的话递归。然后在判断右节点是否存在，存在递归。

 /**
     *          A
     *      B         C
     *   D      E         F
     *
     * 前序遍历 ABDECF
     */
    public void preorderTraversal(TreeNode treeNode){
        if (treeNode==null)
            return;
        System.out.print(treeNode.getTag());
        if (treeNode.getLeftNode()!=null)
             preorderTraversal(treeNode.getLeftNode());
        if (treeNode.getRightNode()!=null)
            preorderTraversal(treeNode.getRightNode());

    }

2.3中序遍历

递归参数：TreeNode
核心思想：先判断是否存在左节点。存在的话递归。然后输出节点的tag，然后在判断是否存在右节点。存在递归，

 /**
     *          A
     *      B         C
     *   D      E         F
     *
     * 中序遍历 DBEACF
     */
    public void inorderTraversal(TreeNode treeNode){
        if (treeNode==null)
            return;
        if (treeNode.getLeftNode()!=null)
            inorderTraversal(treeNode.getLeftNode());
        System.out.print(treeNode.getTag());
        if (treeNode.getRightNode()!=null)
            inorderTraversal(treeNode.getRightNode());
    }

2.4后序遍历

递归参数：TreeNode
核心思想：先判断是否存在左节点。存在的话递归。然后在判断是否存在右节点。存在递归。然后输出节点的tag。

 /**
     *          A
     *      B         C
     *   D      E         F
     *
     * 后序遍历 DEBFCA
     */
    public void afterOrderTraversal(TreeNode treeNode){
        if (treeNode==null)
            return;
        if (treeNode.getLeftNode()!=null)
            afterOrderTraversal(treeNode.getLeftNode());
        if (treeNode.getRightNode()!=null)
            afterOrderTraversal(treeNode.getRightNode());
        System.out.print(treeNode.getTag());
    }

2.5删除节点：
节点的删除和节点的插入思想一样。实现代码

 /**
     * 删除节点
     * @param delete
     */
    public void deleteNode(TreeNode delete,TreeNode rootNode){
        if (delete==null)
            return;
        if (rootNode.getNumber()==delete.getNumber()){
            rootNode=null;
            return;
        }
        if (rootNode.getLeftNode()!=null){
            if (rootNode.getLeftNode().getNumber()==delete.getNumber()){
                rootNode.setLeftNode(null);
            }else {
                deleteNode(delete, rootNode.getLeftNode());
            }
        }
        if (rootNode.getRightNode()!=null){
            if (rootNode.getRightNode().getNumber()==delete.getNumber()){
                rootNode.setRightNode(null);
            }else {
                deleteNode(delete, rootNode.getRightNode());
            }
        }
    }

总体来说：二叉树的递归实现还是比较简单的,下一篇将二叉树的非递归算法。
完整代码：

import java.util.ArrayList;
import java.util.List;

/**
 * Created by wxy on 2017/6/4.
 */
public class BinaryTree {

    public TreeNode rootNode;
    public void buildTree(TreeNode treeNode,TreeNode binaryTree){
        if (rootNode==null){
           rootNode=treeNode;
           rootNode.setLeftNode(null);
           rootNode.setRightNode(null);
           return;
        }
        if (treeNode.getNumber()<binaryTree.getNumber()){
            if (binaryTree.getLeftNode()!=null){
                buildTree(treeNode,binaryTree.getLeftNode());
            }else {
                binaryTree.setLeftNode(treeNode);
            }
        }else {
            if (binaryTree.getRightNode()!=null){
                buildTree(treeNode,binaryTree.getRightNode());
            }else {
                binaryTree.setRightNode(treeNode);
            }
        }
    }


    /**
     *          A
     *      B         C
     *   D      E         F
     *
     * 前序遍历 ABDECF
     */
    public void preorderTraversal(TreeNode treeNode){
        if (treeNode==null)
            return;
        System.out.print(treeNode.getTag());
        if (treeNode.getLeftNode()!=null)
             preorderTraversal(treeNode.getLeftNode());
        if (treeNode.getRightNode()!=null)
            preorderTraversal(treeNode.getRightNode());

    }



    /**
     *          A
     *      B         C
     *   D      E         F
     *
     * 中序遍历 DBEACF
     */
    public void inorderTraversal(TreeNode treeNode){
        if (treeNode==null)
            return;
        if (treeNode.getLeftNode()!=null)
            inorderTraversal(treeNode.getLeftNode());
        System.out.print(treeNode.getTag());
        if (treeNode.getRightNode()!=null)
            inorderTraversal(treeNode.getRightNode());
    }

    /**
     *          A
     *      B         C
     *   D      E         F
     *
     * 后序遍历 DEBFCA
     */
    public void afterOrderTraversal(TreeNode treeNode){
        if (treeNode==null)
            return;
        if (treeNode.getLeftNode()!=null)
            afterOrderTraversal(treeNode.getLeftNode());
        if (treeNode.getRightNode()!=null)
            afterOrderTraversal(treeNode.getRightNode());
        System.out.print(treeNode.getTag());
    }


    /**
     * 删除节点
     * @param delete
     */
    public void deleteNode(TreeNode delete,TreeNode rootNode){
        if (delete==null)
            return;
        if (rootNode.getNumber()==delete.getNumber()){
            rootNode=null;
            return;
        }
        if (rootNode.getLeftNode()!=null){
            if (rootNode.getLeftNode().getNumber()==delete.getNumber()){
                rootNode.setLeftNode(null);
            }else {
                deleteNode(delete, rootNode.getLeftNode());
            }
        }
        if (rootNode.getRightNode()!=null){
            if (rootNode.getRightNode().getNumber()==delete.getNumber()){
                rootNode.setRightNode(null);
            }else {
                deleteNode(delete, rootNode.getRightNode());
            }
        }
    }


    public static void main(String args[]){
        BinaryTree binaryTree=new BinaryTree();
        List<TreeNode>treeNodes=new ArrayList<>();
        treeNodes.add(new TreeNode("A",6));
        treeNodes.add(new TreeNode("B",3));
        treeNodes.add(new TreeNode("C",7));
        treeNodes.add(new TreeNode("D",1));
        treeNodes.add(new TreeNode("E",4));
        treeNodes.add(new TreeNode("F",9));
        treeNodes.forEach(treeNode -> {binaryTree.buildTree(treeNode,binaryTree.rootNode);});
        System.out.print("前序遍历  ");
        binaryTree.preorderTraversal(binaryTree.rootNode);
        System.out.print("\n"+"中序遍历  ");
        binaryTree.inorderTraversal(binaryTree.rootNode);
        System.out.print("\n"+"后序遍历  ");
        binaryTree.afterOrderTraversal(binaryTree.rootNode);
        System.out.print("\n"+"删除节点B  ");
        binaryTree.deleteNode(treeNodes.get(4),binaryTree.rootNode);
        binaryTree.preorderTraversal(binaryTree.rootNode);
        binaryTree.inorderTraversal(binaryTree.rootNode);
        binaryTree.afterOrderTraversal(binaryTree.rootNode);
    }

}