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

作者: 过期的薯条 | 来源:发表于2017-06-05 00:09 被阅读39次

算法之二叉树
总结
数据结构之二叉树
二叉树的三种深度优先遍历算法与思路
二叉树的遍历实现递归与非递归
深入浅出二叉树遍历的非递归算法 2019-11-15（未经允许，
Java二叉树的遍历
二叉树，非递归法
python实现二叉树
Tree

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);
    }

}

算法之二叉树
二叉树之C++实现创建二叉树复制二叉树先序遍历递归实现非递归实现中序遍历递归实现非递归实现后序遍...
总结
1、二叉树广度遍历（非递归）广度遍历非递归实现需要依靠一个队列。 2、二叉树深度遍历（递归与非递归，前序，中序和...
数据结构之二叉树
数据结构之二叉树递归构造二叉树二叉树节点: 递归构造: 图示: 递归遍历递归实现先序遍历图示: 递归实现中...
二叉树的三种深度优先遍历算法与思路
看了一些关于二叉树遍历算法的文章，例如：二叉树三种遍历方式的递归和循环实现二叉树的递归与非递归遍历（前序、中序、后...
二叉树的遍历实现递归与非递归
本文实现了二叉树的深度遍历算法，分为递归与非递归递归的实现非常简单，基本上没啥难度非递归的实现需要根据遍历的顺...
深入浅出二叉树遍历的非递归算法 2019-11-15（未经允许，
1、二叉树遍历的递归算法递归实现二叉树的遍历非常直观，回顾一下递归的代码：前序遍历中序遍历后序遍历他们的...
Java二叉树的遍历
Java二叉树的遍历利用递归和非递归实现二叉树的先序,中序,后序遍历以及使用队列实现二叉树的层次遍历
二叉树，非递归法
递归法二叉树的递归，有前序遍历、中序遍历、后序遍历，一般采用递归法，比较简单非递归法二叉树非递归法，采用栈来实现
python实现二叉树
递归实现二叉树堆实现二叉树前序遍历
Tree
二叉树的深度优先遍历使用递归实现的时候又叫递归遍历，递归就是函数调用自己，同时需要明确递归的出口。递归遍历可以分为...