zcq
    创建二叉树以及实现前中后序遍历查找删除。

    1. package com.atguigu.tree;
    3. public class BinaryTreeDemo {
    5.     public static void main(String[] args) {
    6.         //先需要创建一颗二叉树
    7.         BinaryTree binaryTree = new BinaryTree();
    8.         //创建需要的结点
    9.         HeroNode root = new HeroNode(1, "宋江");
    10.         HeroNode node2 = new HeroNode(2, "吴用");
    11.         HeroNode node3 = new HeroNode(3, "卢俊义");
    12.         HeroNode node4 = new HeroNode(4, "林冲");
    13.         HeroNode node5 = new HeroNode(5, "关胜");
    15.         //说明，我们先手动创建该二叉树，后面我们学习递归的方式创建二叉树
    16.         root.setLeft(node2);
    17.         root.setRight(node3);
    18.         node3.setRight(node4);
    19.         node3.setLeft(node5);
    20.         binaryTree.setRoot(root);
    22.         //测试
    23. //        System.out.println("前序遍历"); // 1,2,3,5,4
    24. //        binaryTree.preOrder();
    26.         //测试 
    27. //        System.out.println("中序遍历");
    28. //        binaryTree.infixOrder(); // 2,1,5,3,4
    29. //        
    30. //        System.out.println("后序遍历");
    31. //        binaryTree.postOrder(); // 2,5,4,3,1
    33.         //前序遍历
    34.         //前序遍历的次数 ：4 
    35. //        System.out.println("前序遍历方式~~~");
    36. //        HeroNode resNode = binaryTree.preOrderSearch(5);
    37. //        if (resNode != null) {
    38. //            System.out.printf("找到了，信息为 no=%d name=%s", resNode.getNo(), resNode.getName());
    39. //        } else {
    40. //            System.out.printf("没有找到 no = %d 的英雄", 5);
    41. //        }
    43.         //中序遍历查找
    44.         //中序遍历3次
    45. //        System.out.println("中序遍历方式~~~");
    46. //        HeroNode resNode = binaryTree.infixOrderSearch(5);
    47. //        if (resNode != null) {
    48. //            System.out.printf("找到了，信息为 no=%d name=%s", resNode.getNo(), resNode.getName());
    49. //        } else {
    50. //            System.out.printf("没有找到 no = %d 的英雄", 5);
    51. //        }
    53.         //后序遍历查找
    54.         //后序遍历查找的次数  2次
    55. //        System.out.println("后序遍历方式~~~");
    56. //        HeroNode resNode = binaryTree.postOrderSearch(5);
    57. //        if (resNode != null) {
    58. //            System.out.printf("找到了，信息为 no=%d name=%s", resNode.getNo(), resNode.getName());
    59. //        } else {
    60. //            System.out.printf("没有找到 no = %d 的英雄", 5);
    61. //        }
    63.         //测试一把删除结点
    65.         System.out.println("删除前,前序遍历");
    66.         binaryTree.preOrder(); //  1,2,3,5,4
    67.         binaryTree.delNode(5);
    68.         //binaryTree.delNode(3);
    69.         System.out.println("删除后，前序遍历");
    70.         binaryTree.preOrder(); // 1,2,3,4
    74.     }
    76. }
    78. //定义BinaryTree 二叉树
    79. class BinaryTree {
    80.     private HeroNode root;
    82.     public void setRoot(HeroNode root) {
    83.         this.root = root;
    84.     }
    86.     //删除结点
    87.     public void delNode(int no) {
    88.         if(root != null) {
    89.             //如果只有一个root结点, 这里立即判断root是不是就是要删除结点
    90.             if(root.getNo() == no) {
    91.                 root = null;
    92.             } else {
    93.                 //递归删除
    94.                 root.delNode(no);
    95.             }
    96.         }else{
    97.             System.out.println("空树，不能删除~");
    98.         }
    99.     }
    100.     //前序遍历
    101.     public void preOrder() {
    102.         if(this.root != null) {
    103.             this.root.preOrder();
    104.         }else {
    105.             System.out.println("二叉树为空，无法遍历");
    106.         }
    107.     }
    109.     //中序遍历
    110.     public void infixOrder() {
    111.         if(this.root != null) {
    112.             this.root.infixOrder();
    113.         }else {
    114.             System.out.println("二叉树为空，无法遍历");
    115.         }
    116.     }
    117.     //后序遍历
    118.     public void postOrder() {
    119.         if(this.root != null) {
    120.             this.root.postOrder();
    121.         }else {
    122.             System.out.println("二叉树为空，无法遍历");
    123.         }
    124.     }
    126.     //前序遍历
    127.     public HeroNode preOrderSearch(int no) {
    128.         if(root != null) {
    129.             return root.preOrderSearch(no);
    130.         } else {
    131.             return null;
    132.         }
    133.     }
    134.     //中序遍历
    135.     public HeroNode infixOrderSearch(int no) {
    136.         if(root != null) {
    137.             return root.infixOrderSearch(no);
    138.         }else {
    139.             return null;
    140.         }
    141.     }
    142.     //后序遍历
    143.     public HeroNode postOrderSearch(int no) {
    144.         if(root != null) {
    145.             return this.root.postOrderSearch(no);
    146.         }else {
    147.             return null;
    148.         }
    149.     }
    150. }
    152. //先创建HeroNode 结点
    153. class HeroNode {
    154.     private int no;
    155.     private String name;
    156.     private HeroNode left; //默认null
    157.     private HeroNode right; //默认null
    158.     public HeroNode(int no, String name) {
    159.         this.no = no;
    160.         this.name = name;
    161.     }
    162.     public int getNo() {
    163.         return no;
    164.     }
    165.     public void setNo(int no) {
    166.         this.no = no;
    167.     }
    168.     public String getName() {
    169.         return name;
    170.     }
    171.     public void setName(String name) {
    172.         this.name = name;
    173.     }
    174.     public HeroNode getLeft() {
    175.         return left;
    176.     }
    177.     public void setLeft(HeroNode left) {
    178.         this.left = left;
    179.     }
    180.     public HeroNode getRight() {
    181.         return right;
    182.     }
    183.     public void setRight(HeroNode right) {
    184.         this.right = right;
    185.     }
    186.     @Override
    187.     public String toString() {
    188.         return "HeroNode [no=" + no + ", name=" + name + "]";
    189.     }
    191.     //递归删除结点
    192.     //1.如果删除的节点是叶子节点，则删除该节点
    193.     //2.如果删除的节点是非叶子节点，则删除该子树
    194.     public void delNode(int no) {
    196.         //思路
    197.         /*
    198.          *     1. 因为我们的二叉树是单向的，所以我们是判断当前结点的子结点是否需要删除结点，而不能去判断当前这个结点是不是需要删除结点.
    199.             2. 如果当前结点的左子结点不为空，并且左子结点 就是要删除结点，就将this.left = null; 并且就返回(结束递归删除)
    200.             3. 如果当前结点的右子结点不为空，并且右子结点 就是要删除结点，就将this.right= null ;并且就返回(结束递归删除)
    201.             4. 如果第2和第3步没有删除结点，那么我们就需要向左子树进行递归删除
    202.             5.  如果第4步也没有删除结点，则应当向右子树进行递归删除.
    204.          */
    205.         //2. 如果当前结点的左子结点不为空，并且左子结点 就是要删除结点，就将this.left = null; 并且就返回(结束递归删除)
    206.         if(this.left != null && this.left.no == no) {
    207.             this.left = null;
    208.             return;
    209.         }
    210.         //3.如果当前结点的右子结点不为空，并且右子结点 就是要删除结点，就将this.right= null ;并且就返回(结束递归删除)
    211.         if(this.right != null && this.right.no == no) {
    212.             this.right = null;
    213.             return;
    214.         }
    215.         //4.我们就需要向左子树进行递归删除
    216.         if(this.left != null) {
    217.             this.left.delNode(no);
    218.         }
    219.         //5.则应当向右子树进行递归删除
    220.         if(this.right != null) {
    221.             this.right.delNode(no);
    222.         }
    223.     }
    225.     //编写前序遍历的方法
    226.     public void preOrder() {
    227.         System.out.println(this); //先输出父结点
    228.         //递归向左子树前序遍历
    229.         if(this.left != null) {
    230.             this.left.preOrder();
    231.         }
    232.         //递归向右子树前序遍历
    233.         if(this.right != null) {
    234.             this.right.preOrder();
    235.         }
    236.     }
    237.     //中序遍历
    238.     public void infixOrder() {
    240.         //递归向左子树中序遍历
    241.         if(this.left != null) {
    242.             this.left.infixOrder();
    243.         }
    244.         //输出父结点
    245.         System.out.println(this);
    246.         //递归向右子树中序遍历
    247.         if(this.right != null) {
    248.             this.right.infixOrder();
    249.         }
    250.     }
    251.     //后序遍历
    252.     public void postOrder() {
    253.         if(this.left != null) {
    254.             this.left.postOrder();
    255.         }
    256.         if(this.right != null) {
    257.             this.right.postOrder();
    258.         }
    259.         System.out.println(this);
    260.     }
    262.     //前序遍历查找
    263.     /**
    264.      * 
    265.      * @param no 查找no
    266.      * @return 如果找到就返回该Node ,如果没有找到返回 null
    267.      */
    268.     public HeroNode preOrderSearch(int no) {
    269.         System.out.println("进入前序遍历");
    270.         //比较当前结点是不是
    271.         if(this.no == no) {
    272.             return this;
    273.         }
    274.         //1.则判断当前结点的左子节点是否为空，如果不为空，则递归前序查找
    275.         //2.如果左递归前序查找，找到结点，则返回
    276.         HeroNode resNode = null;
    277.         if(this.left != null) {
    278.             resNode = this.left.preOrderSearch(no);
    279.         }
    280.         if(resNode != null) {//说明我们左子树找到
    281.             return resNode;
    282.         }
    283.         //1.左递归前序查找，找到结点，则返回，否继续判断，
    284.         //2.当前的结点的右子节点是否为空，如果不空，则继续向右递归前序查找
    285.         if(this.right != null) {
    286.             resNode = this.right.preOrderSearch(no);
    287.         }
    288.         return resNode;
    289.     }
    291.     //中序遍历查找
    292.     public HeroNode infixOrderSearch(int no) {
    293.         //判断当前结点的左子节点是否为空，如果不为空，则递归中序查找
    294.         HeroNode resNode = null;
    295.         if(this.left != null) {
    296.             resNode = this.left.infixOrderSearch(no);
    297.         }
    298.         if(resNode != null) {
    299.             return resNode;
    300.         }
    301.         System.out.println("进入中序查找");
    302.         //如果找到，则返回，如果没有找到，就和当前结点比较，如果是则返回当前结点
    303.         if(this.no == no) {
    304.             return this;
    305.         }
    306.         //否则继续进行右递归的中序查找
    307.         if(this.right != null) {
    308.             resNode = this.right.infixOrderSearch(no);
    309.         }
    310.         return resNode;
    312.     }
    314.     //后序遍历查找
    315.     public HeroNode postOrderSearch(int no) {
    317.         //判断当前结点的左子节点是否为空，如果不为空，则递归后序查找
    318.         HeroNode resNode = null;
    319.         if(this.left != null) {
    320.             resNode = this.left.postOrderSearch(no);
    321.         }
    322.         if(resNode != null) {//说明在左子树找到
    323.             return resNode;
    324.         }
    326.         //如果左子树没有找到，则向右子树递归进行后序遍历查找
    327.         if(this.right != null) {
    328.             resNode = this.right.postOrderSearch(no);
    329.         }
    330.         if(resNode != null) {
    331.             return resNode;
    332.         }
    333.         System.out.println("进入后序查找");
    334.         //如果左右子树都没有找到，就比较当前结点是不是
    335.         if(this.no == no) {
    336.             return this;
    337.         }
    338.         return resNode;
    339.     }
    341. }
    343. //
    1. package com.atguigu.tree;
    3. import java.util.HashSet;
    5. public class Test {
    7.     @SuppressWarnings("unused")
    8.     public static void main(String[] args) {
    10.     }
    11. }