什么是二叉树

发布时间:2021-02-4编辑:RainNight阅读(1435)

    什么是二叉树?

    • 树有很多种, 每个节点最多只能有两个子节点的叫二叉树

    • 二叉树的子节点分为左节点和右节点
      avatar

    • 如果二叉树的所有叶子节点都在最后一层, 并且结点总数=2^n-1, n为层数, 则我们称之为满二叉数
      avatar

    • 如果该二叉树的所有叶子节点(没有子节点的节点)都在最后一层或者倒数第二层, 而且最后一层的叶子节点在左边连续, 倒数第二层的叶子节点在右边连续, 我们称之为完全二叉树
      img

    遍历二叉树

    • 前序、中序和后序三种遍历方式

    • 前序遍历, 先输出父节点, 再遍历左子树和右子树

    • 中序遍历, 先遍历左子树, 再输出父节点, 再遍历右子树

    • 后序遍历, 先遍历左子树, 再遍历右子树, 最后输出父节点

    代码实现

    • Java

    /**
      1. 定义节点
     /class HeroNode{
        private int no;
        private String name;
        private HeroNode left;
        private HeroNode right;

        public HeroNode(int no, String name) {         this.no = no;         this.name = name;     }

        public int getNo() {         return no;     }

        public void setNo(int no) {         this.no = no;     }

        public String getName() {         return name;     }

        public void setName(String name) {         this.name = name;     }

        public HeroNode getLeft() {         return left;     }

        public void setLeft(HeroNode left) {         this.left = left;     }

        public HeroNode getRight() {         return right;     }

        public void setRight(HeroNode right) {         this.right = right;     }

        @Override     public String toString() {         return "HeroNode{" +                 "no=" + no +                 ", name='" + name + ''' +                 '}';     }             /**       前序遍历      /     public void preOrder(){         // 1. 先输出父节点         System.out.println(this);         // 2. 递归向左子树前序遍历         if(this.left != null){             this.left.preOrder();         }         //3. 递归向右子树前序遍历         if(this.right != null){             this.right.preOrder();         }     }

        /**       中序遍历      /     public void midOrder(){         //1.递归向左子树前序遍历         if(this.left != null){             this.left.midOrder();         }

            //2.先输出父节点         System.out.println(this);

            //3.递归向右子树前序遍历         if(this.right != null){             this.right.midOrder();         }     }

            /**       后序遍历      /     public void postOrder(){         //1.递归向左子树前序遍历         if(this.left != null){             this.left.postOrder();         }

            //2.递归向右子树前序遍历         if(this.right != null){             this.right.postOrder();         }

            //3.先输出父节点         System.out.println(this);     }

         /**       查找节点       @param no      */     public HeroNode preOrderSearch(int no){         //当前节点是不是         if (this.no == no){             return this;         }

            HeroNode  heroNode = null;         //在左子树找到         if(this.left != null){             heroNode = this.left.preOrderSearch(no);             if (heroNode != null){                 return heroNode;             }         }

            //在右子树找到         if(this.right != null){             heroNode = this.right.preOrderSearch(no);             if (heroNode != null){                 return heroNode;             }         }         return null;     }

          /**       删除节点       @param no 要删除节点的ID      *       思路:       1. 先判断左支节点不为空且是要删除的节点, 就将this.left = null; 返回, 结束遍历;       2. 再判断右支节点不为空且是要删除的节点, 就将this.right = null; 返回, 结束遍历;       3. 如果1,2两步没有删除节点, 那我们就先向左子树进行递归删除       4. 如果第3步页也没有删除节点, 就应当向右子树进行递归删除      /     public void delNode(int no){         // 1.先判断左支节点不为空且是要删除的节点, 就将this.left = null; 返回, 结束遍历;         if(this.left != null && this.left.no == no){             this.left = null;             return;         }         //2. 再判断右支节点不为空且是要删除的节点, 就将this.right = null; 返回, 结束遍历;         if(this.right != null && this.right.no == no){             this.right = null;             return;         }         //3. 如果1,2两步没有删除节点, 那我们就先向左子树进行递归删除         if(this.left != null){             this.left.delNode(no);         }         //4. 如果第3步页也没有删除节点, 就应当向右子树进行递归删除         if (this.right != null){             this.right.delNode(no);         }     }}/**   2. 定义二叉树  /class BinaryTree{

        private HeroNode root;     public void setRoot(HeroNode root){         this.root = root;     }

        //前序遍历     public void preOrder(){         if(this.root != null){             this.root.preOrder();         }else{             System.out.println("二叉树为空, 无法遍历");         }     }

        //中序遍历     public void midOrder(){         if(this.root != null){             this.root.midOrder();         }else{             System.out.println("二叉树为空, 无法遍历");         }     }

        //后序遍历     public void postOrder(){         if(this.root != null){             this.root.postOrder();         }else{             System.out.println("二叉树为空, 无法遍历");         }     }

        //前序查找     public HeroNode preOrderSearch(int no){         if(this.root != null){             return this.root.preOrderSearch(no);         }else {             return null;         }     }

        // 删除节点     public void delNode(int no){         if(root != null){             // 判断root节点是不是要删除的节点             if(root.getNo() == no){                 root = null;             }else {                 // 递归删除                 root.delNode(no);             }         }else {             System.out.println("空二叉树, 不能删…");         }     }}/**   3. 测试  /public class erCha {     public static void main(String[] args) {

            // 1. 创建一个二叉树         BinaryTree binaryTree = new BinaryTree();

            // 2. 创建节点         HeroNode root = new HeroNode(1, "张三");         HeroNode node2 = new HeroNode(2, "李四");         HeroNode node3 = new HeroNode(3, "王五");         HeroNode node4 = new HeroNode(4, "赵六");         HeroNode node5 = new HeroNode(5, "宋七");

            //3. 手动创建二叉树         root.setLeft(node2);         root.setRight(node3);         node3.setRight(node4);         node3.setLeft(node5);         binaryTree.setRoot(root);

            //4. 遍历         System.out.println("前序遍历");         binaryTree.preOrder();         System.out.println("中序遍历");         binaryTree.midOrder();         System.out.println("后序遍历");         binaryTree.postOrder();

            // 查找节点         System.out.println("查找节点");         HeroNode heroNode = binaryTree.preOrderSearch(3);         System.out.println(heroNode.toString());     }}输出: 前序遍历 HeroNode{no=1, name='张三'}HeroNode{no=2, name='李四'}HeroNode{no=3, name='王五'}HeroNode{no=5, name='宋七'}HeroNode{no=4, name='赵六'}中序遍历 HeroNode{no=2, name='李四'}HeroNode{no=1, name='张三'}HeroNode{no=5, name='宋七'}HeroNode{no=3, name='王五'}HeroNode{no=4, name='赵六'}后序遍历 HeroNode{no=2, name='李四'}HeroNode{no=5, name='宋七'}HeroNode{no=4, name='赵六'}HeroNode{no=3, name='王五'}HeroNode{no=1, name='张三'}查找节点 HeroNode{no=3, name='王五'}

    在这里插入图片描述


关键字二叉树

Collect from 雨夜的博客 雨夜的博客