精华内容
下载资源
问答
  • https://zhuanlan.zhihu.com/p/153216919
    展开全文
  • 什么二叉树

    2020-08-27 21:09:42
    如果该二叉树的所有叶子节点(没有子节点的节点)都在最后一层或者倒数第二层, 而且最后一层的叶子节点在左边连续, 倒数第二层的叶子节点在右边连续, 我们称之为完全二叉树 img 遍历二叉树 前序、中序

    什么是二叉树

    什么是二叉树?

    • 树有很多种, 每个节点最多只能有两个子节点的叫二叉树
    • 二叉树的子节点分为左节点和右节点
      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='王五'}
    

    在这里插入图片描述
    雨夜的博客

    展开全文
  • 二叉树结构

    2020-02-16 22:40:13
    首先说明,二叉树没有什么原理,一个根节点,最多只能分配两个子节点,也可以有一个子节点,分别叫做的满(完全二叉树和左子树,右子树 常见的问题就是遍历 了,咱们都是搞程序编程的,如果以程序的方式遍历这...

    首先,二叉树是一个数据结果,以节点子节点存储数据的数据结构,只能有一个根节点,每个节点最多只能有两个节点,依次下推

    参照下图:

     

    首先说明,二叉树没有什么原理,一个根节点,最多只能分配两个子节点,也可以有一个子节点,分别叫做的叫满(完全)二叉树和左子树右子树

    常见的问题就是遍历 了,咱们都是搞程序编程的,如果以程序的方式遍历这个数据,并且按照一定形式输出,

    三种方式

    先序:根左右

     

    中序遍历:左根右

     

    后序遍历:左右根

     

     

    1. 应用场景:输出某个文件夹下所有文件名称(可以有子文件夹)—用先序遍历实现。
    2. 统计某个文件夹的大小(该文件夹下所有文件的大小)–用后序遍历实现。

     

     

    
    public class Node {
    		//数据名称
    		private int data;  
    		//左侧子节点
    	    private Node leftNode;  
    	    //右侧子节点
    	    private Node rightNode;  
    	    //有参构造函数
    	    public Node(int data, Node leftNode, Node rightNode){  
    	        this.data = data;  
    	        this.leftNode = leftNode;  
    	        this.rightNode = rightNode;  
    	    }  
    //此处省略 get set方法(程序编写,注意需要生成)
    public class BinaryTree {
    	
    	 /** 
         * @author yaobo
         * 二叉树的先序中序后序排序 
         */  
        public Node init() {//注意必须逆序建立,先建立子节点,再逆序往上建立,因为非叶子结点会使用到下面的节点,而初始化是按顺序初始化的,不逆序建立会报错  
            Node J = new Node(8, null, null);  
            Node H = new Node(4, null, null);  
            Node G = new Node(2, null, null);
            Node F = new Node(7, null, J);
            Node E = new Node(5, H, null);  
            Node D = new Node(1, null, G);  
            Node C = new Node(9, F, null);  
            Node B = new Node(3, D, E);  
            Node A = new Node(6, B, C);  
            
            return A;   //返回根节点  
        }
        //输出节点信息
        public void printNode(Node node){
            System.out.print(node.getData());  
        }  
        
        //先序遍历  
        public void theFirstTraversal(Node root) {
            printNode(root);  
            if (root.getLeftNode() != null) {  //使用递归进行遍历左孩子  
                theFirstTraversal(root.getLeftNode());  
            }  
            if (root.getRightNode() != null) {  //递归遍历右孩子  
                theFirstTraversal(root.getRightNode());  
            }  
        }  
        //中序遍历  
        public void theInOrderTraversal(Node root) {
            if (root.getLeftNode() != null) {  
                theInOrderTraversal(root.getLeftNode());  
            }  
            printNode(root);  
            if (root.getRightNode() != null) {  
                theInOrderTraversal(root.getRightNode());  
            }  
        }
        
        //后序遍历  
        public void thePostOrderTraversal(Node root) { 
            if (root.getLeftNode() != null) {  
                thePostOrderTraversal(root.getLeftNode());  
            }  
            if(root.getRightNode() != null) {  
                thePostOrderTraversal(root.getRightNode());  
            }  
            printNode(root);  
        }  
         
        //调用
        public static void main(String[] args) {  
            BinaryTree tree = new BinaryTree();  
            Node root = tree.init();  
            System.out.println("明瑞:先序遍历");  
            tree.theFirstTraversal(root);  
            System.out.println("");  
            System.out.println("明瑞:中序遍历");  
            tree.theInOrderTraversal(root);  
            System.out.println("");  
            System.out.println("明瑞:后序遍历");  
            tree.thePostOrderTraversal(root);  
            System.out.println("");  
            
        }  

    结果

    明瑞:先序遍历
    631254978
    明瑞:中序遍历
    123456789
    明瑞:后序遍历
    214538796

     

    展开全文
  • 二叉树的镜像

    2016-05-08 00:19:00
    看到这个题目,你第一感觉就是完了,不懂啊,没关系,我们看看什么叫二叉树的镜像,一张图说明: 二叉树图还是借用上一篇博客的图: 话说二叉树的镜像,用两个图足以说明,我们说图一是图二的一个镜像,也可以说图...

    看到这个题目,你第一感觉就是完了,不懂啊,没关系,我们看看什么叫二叉树的镜像,一张图说明:

    二叉树图还是借用上一篇博客的图:


    话说二叉树的镜像,用两个图足以说明,我们说图一是图二的一个镜像,也可以说图二的二叉树是图一二叉树的一个镜像

    看见图中的镜子了没,想想镜子起的作用,镜像就是这么来的

    两颗二叉树特点分析:

    1.都是二叉树(哈哈)

    2.二叉树中数据完全相同。

    3.除了根节点位置相同,其余所有节点的左右孩子指针相反,包括根节点,即就是交换了左右孩子的指针;

    唯一可以区分的就是第三条,也因为第三条,写出如下代码,很好理解:

    	//此二叉树的镜像
    	void ToMirror(BinaryTreeNode<T>* root)
    	{
    		if (root == nullptr)
    		{
    			return nullptr;
    		}
    
    		//交换左右孩子指针
    		swap(root->_left,root->_right);
    
    		//递归左右子树同样的操作
    		ToMirror(root->_left);
    		ToMirror(root->_right);
    	}
    赐教!

    转载于:https://www.cnblogs.com/li-ning/p/9490007.html

    展开全文
  • 加分二叉树

    2019-09-25 04:40:11
    一道入门的区间dp,当然,根据写法不同你还可以把它归类为树形dp或者记忆化搜索,其实都无所谓啦。作为一道入门题,我们完全可以“显然”地做出来,但是在这里还是想和...Q:dp要满足无后效性,什么叫无后效性?A:...
  • 1. 什么叫作顺序存储二叉树 当一颗二叉树满足如下两个条件时,就是顺序存储二叉树二叉树是以数组的方式存放数据的。如下图所示: 在遍历数组时,仍然可以按照前序遍历、中序遍历和后序遍历的方式来完成节点...
  • 堆及其相关应用

    2018-11-03 21:21:34
    提到堆就不得不说到二叉树这个结构,堆就是一颗完全二叉树,什么叫完全二叉树,用一句话来概括就是:设二叉树的深度为h,除第h层外,其它各层的结点数都达到最大个数,第h层所有的结点都连续集中在最左边,这就是...
  • 想要了解什么是堆,先要了解什么叫完全二叉树。 想要了解什么是完全二叉树,先要了解什么是满二叉树。 想要了解满二叉树… emm 到满二叉树就够了。 一些基本的概念 满二叉树,很容易理解,就是一个把节点铺满的...
  • 看这个图就很好理解什么叫完全二叉树了。真的很完美啊哈哈哈。 但是,有另外一种树结构也叫做完全二叉树。准确来说就是近似是完全二叉树。 长这样子: 上面这种二叉树,叶节点的深度的最大差距是1,最下层叶...
  • 如果该二叉树的所有叶子节点(没有子节点的节点)都在最后一层或者倒数第二层, 而且最后一层的叶子节点在左边连续, 倒数第二层的叶子节点在右边连续, 我们称之为完全二叉树 2、二叉树的三种排序方式 前序、中序...
  • 每个节点最多只能有两个子节点的树二叉树,如果除了树的最后一层之外其他层都有左右子节点,这样的树称为完全二叉树 这就是一颗完全二叉树 (1)前序遍历:根结点 —> 左子树 —> 右子树 (2)中序遍历:左...
  • 什么叫完全二叉树呢,完全二叉树指的是前面n个节点都是满二叉树中的节点换句话说就是完全二叉树的子节点必须处于树的最后两行,且是从左到右的顺序。 二、堆排序的基本思想 通过对堆的调整得到根节点,因为调整后的...
  • ②把堆顶跟完全二叉树的最后一个子叶进行交换,再把最后一个子叶放在数组的最后一位; ③重复以上①②。 3.适用场景:性能好,不稳定。适用于只求最大(小)M个数。 与快速排序不同的地方: 1.原理不同,堆排序是...
  • 数据结构中的堆:堆实际上指的就是(满足堆性质的)优先队列的一种数据结构,第1个元素有最高的...数据结构中的堆可以用一个数组来存储(完全二叉树结构。)操作系统中的堆:这里的堆是属于内存分配方式的一种:动态...
  • SPL SplHeap 堆

    2020-12-26 16:56:26
    有人会问 什么完全二叉树?首先你得知道什么是满二叉树。满二叉树的定义是:“除了最后一层无任何子节点外,每一层上的所有的节点都有两个子节点的二叉树满二叉树。”请注意,如果一棵树的层级为n,n-1层的节点...
  • 二叉堆是一种特殊的堆,可以看做是完全二叉树,它分为两个类型: 1.最大堆 2.最小堆 什么是最大堆呢?就是父结点的键值总是大于或等于任何一个子节点的键值; 什么是最小堆呢?父结点的键值总是小于或等于...
  • 即自上而下, 自左到右, 依次将每一个节点, 叠满整棵树, 这种树叫完全二叉树 当完全二叉树的每一个节点大于等于或者小于等于自己的左右子树时, 称该完全二叉树为堆 当堆的顶端是最大值时, 它叫大顶堆 当堆的...
  • 什么是堆排序

    2021-03-20 09:41:51
    堆是一颗完全二叉树 那堆有什么特点呢? 堆中的节点有如下的特征:堆中的每个节点都是不大于或者不小于其父节点的 根据堆的特征,我们可以将堆分为大顶堆和小顶堆: 大顶堆:就是堆的每个节点值都是不大于其父...
  • 二叉堆的详解

    2021-01-26 08:33:22
    堆是一种数据结构,一种叫做完全二叉树的数据结构。 什么是二叉树? 二叉树是一种特殊的树。二叉树的客店是每个结点最多有两个儿子,左边的左儿子,右边的右儿子。 二叉树的分类 二叉树中还有两种特殊的...
  • 堆是一种完全二叉树,为什么叫堆? 在完全二叉树的基础上去维护一种性质:对于任何一个根结点和左右孩子构成的三元组而言,根结点最大或最小(大顶堆、小顶堆) 什么是数据结构 数据结构=结构定义+结构操作 通过某种...
  • 堆呢顺序是随意的,可以看作一棵树的数组对象,是一颗完全二叉树(也是一种数据结构,节点做多有两个子树),是在程序运行时开辟一块动态内存空间。 而栈又“堆栈”,是一种使用堆的“方法”,遵循后进先出,先进...
  • 浅谈数据结构-堆

    2016-09-13 19:59:00
    在数据结构的世界中有一个堆的玩意,这玩意有什么用呢?无用,都去pq了 堆,其实就是一棵完全二叉树。 “若设二叉树的深度为h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数,第 h 层所有的结点都连续...
  • 堆排序

    2021-02-06 11:11:09
    什么叫堆有序 当一棵二叉树的每一个父节点都大于等于它的子节点时,被称为堆有序。 堆又分为大顶堆和小顶堆。 大顶堆的定义是:根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最大者,称为大顶堆。大顶堆要求...
  • 好,前面我们介绍了一般二叉树、完全二叉树、满二叉树,这篇文章呢,我们要介绍的是哈夫曼树。 哈夫曼树也最优二叉树,与哈夫曼树相关的概念还有哈夫曼编码,这两者其实是相同的。哈夫曼编码是哈夫曼在1952年提出...

空空如也

空空如也

1 2 3 4
收藏数 67
精华内容 26
关键字:

什么叫完全二叉树