[数据结构与算法] 面试二叉树基础知识大全

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 面试二叉树基础知识大全 -> 正文阅读

[数据结构与算法]面试二叉树基础知识大全

前言：

二叉树作为数据结构的重点知识，其重要性不言而喻
在面试中它也是高频的考点，所以掌握二叉树的知识是必须之路

问题一：二叉树有哪几种类型?

1）满二叉树：如果二叉树的所有节点都早最后一层，且它的结点总个数为2^n-1（n为二叉树的层数），这样的二叉树我们称为满二叉树

这就是慢
图1-1

完全二叉树：如果二叉树的所有叶子结点都在倒数第一层或者倒数第二层，而且倒数第一层的叶子结点在左边连续，倒数第二层的节点在右边连续，这样的二叉树称为完全二叉树

在这里插入图片描述
图1-2

问题二：二叉树的遍历方式

前序遍历：先输出父节点，再遍历左子树和右子树
图1-1：11 21 41 51 31 61 71
代码实现思路：
先输出当前节点（初始的时候在root节点）
如果左子节点不为空，则递归继续前序遍历
如果右子节点不为空，则递归继续前序遍历

//前序遍历
    public void preMethod(){
        System.out.println(this);
        //递归左子树
        if (this.leftTree!=null){
            this.leftTree.preMethod();
        }
        //递归右子树
        if(this.rightTree!=null){
            this.rightTree.preMethod();
        }
    }

中序遍历：先遍历左子树，再输出父节点，再遍历右子树
图1-1：41 21 51 11 61 31 71
如果左子节点不为空，则递归继续中序遍历
先输出当前节点
如果右子节点不为空，则递归继续中序遍历

 //中序遍历
   public void middleMethod(){
        if (this.leftTree!=null){
            this.leftTree.middleMethod();
        }
        System.out.println(this);
        if (this.rightTree!=null){
            this.rightTree.middleMethod();
        }
   }

后序遍历：先遍历左子树，再遍历右子树
再输出父节点图1-1：41 51 21 61 71 31 11
如果左子节点不为空，则递归继续后序遍历
如果右子节点不为空，则递归继续后序遍历
先输出当前节点

  //后续遍历
    public void afterMethod(){
        if (this.leftTree!=null){
            this.leftTree.afterMethod();
        }
        if (this.rightTree!=null){
            this.rightTree.afterMethod();
        }
        System.out.println(this);
    }