树,二叉树,二叉搜索树笔试编程题必须知道的做题思路

￡神魔★判官ぃ 2021-07-24 22:40 323阅读 0赞

### 文章目录 ###

*  树 二叉树 二叉搜索树
 *  树的相关知识
 *   *  基本概念
     *   *  基本术语:
         *  树的代码实现:(基于链式存储)
     *  二叉树的遍历
     *  二叉搜索树
     *  二叉搜索树的操作
     *   *  二叉搜索树的插入
         *  二叉搜索树的创建
         *  二叉搜索树的删除
     *  树 二叉树的常见面试题

# 树 二叉树 二叉搜索树 #

# 树的相关知识 #

## 基本概念 ##

### 基本术语: ###

*  结点的度：结点的子树个数
 *  树的度：树中所有结点的度的最大值
 *  路径和路径长度：从结点n1到nk的**路径**是一个结点序列n1、n2、… 、nk其中ni是ni+1的父结点。路径所包含的边的个数叫做**路径的长度**
 *  结点的层次：规定根结点的层次为1层，其他任一结点的层次为其父结点的层次加一
 *  树的深度：树中所有结点的层次最大值是这棵树的深度

### 树的代码实现:(基于链式存储) ###

![image-20200929144302469][]

## 二叉树的遍历 ##

由于树的结构时可以分为根节点和左子树和右子树.遍历一个数也要按照一定的顺序遍历完所有的节点,根据遍历顺序的不同,我们可以将树的遍历分为前序遍历,中序遍历和后序遍历.

分别指的是:(不论是那种遍历方式,都是现在同一层操作,操作完才会去下一层)

*  前序遍历:先遍历根节点,然后遍历左子树,最后遍历右子树
 *  中序遍历:左 - 根— 右
 *  后序遍历: 左- 右 -根

那么如何遍历一根数:中心思想就是`递归`,因为在树定义中,树本身的结构就是一种递归的结构

那么使用递归的方式进行遍历树的结构,本质上是一种深度优先的遍历方式.

树本身的查询的时间复杂度是O(n)的,它需要遍历到树的每一个节点,直到找到对应的元素,而这个时间复杂度平均来说,就是0(n)。

## 二叉搜索树 ##

![image-20200929145149140][]

## 二叉搜索树的操作 ##

二叉搜索树的查询和插入的时间复杂度不再是0(n)了,而是0(log(n))

对比于链表来说,链表的查询时O(n)的,需要遍历链表,直到找到对应的元素,链表的插入相对来说比较简单,时间复杂度是O(1)的,可以直接插入到链表中指定的位置。

细致的解读二叉搜索树的查询的时间复杂度：

![image-20200929145939637][]

类似这样的一个树的结构：

1.  如果只知道是二叉树，那么查询的时间复杂度是O（n）的，这个是毋庸置疑的。
2.  如果现在知道是二叉搜索树，那么意味着，左子树的所有结点的值都小于根节点，而右子树的所有结点的值全部都大于根节点，当我们需要查找一个元素值时，我们只需要去查找左子树或者是右子树（有点类似于二分查找的意味）。每次都会筛选出一半的不符合要求的节点（这些节点集中在当前查找的根节点的左边或者右边）。

### 二叉搜索树的插入 ###

> 思想:
> 
> 先查找,如果能找到需要插入的元素,那么count+1,如果查找不到,那么就找到查找到的最近的一个节点,在其下面插入该元素
> 
> 二叉搜索树不会出现重复元素，所以遇到重复元素的时候就不插入。

### 二叉搜索树的创建 ###

> 注意:
> 
> `一颗空的树也是一个二叉搜索树`,那么二叉搜索树的关键就是如何将元素按照二叉搜索树的规则插入到树中去。
> 
> 也就是不断的调用插入操作即可。

### 二叉搜索树的删除 ###

> 删除的话分为两种情况:
> 
> 1.  要删除的节点是一个叶子节点,那么直接删除即可。（叶子节点的元素节点删除对于树的形态不会发生变化，因此可以直接删除）。
> 2.  如果要删除的节点是一个根节点（如果要删除的节点是`一些关键的节点`）,我们删除这样的节点,为了防止改变树的形态,我们需要找到一个新的节点,来替换该节点之前所在的位置来充当根节点。`这时有两种常见的策略`
> 3.  选取比该节点相近小的节点
> 4.  选取比该节点相近大的节点

![image-20200929152041882][]

图解`采用的是策略2(找较大的)`:

要删除的节点是41,采用策略2,那么会在有子树找,找到72,72是一个根节点,不符合要求,那么要找比要删除的根节点稍大的(最相近的)的节点,那么会在72的左子树寻找,找到50

![image-20200929152601072][]

/** * @author 雷雨 * @date 2020/9/29 23:29 */
    public class TreeNode { 
        public Integer value;
        public TreeNode left;
        public TreeNode right;
        //默认不提供左子树和右子树
        //默认只实现一个空的二叉树
        public TreeNode(int value){ 
            this.value = value;
        }
    
        /** * 实现先序遍历 * 根-----左-----右 */
        public void preOrder(){ 
            //输出根节点
            System.out.println(this);
            //递归实现左子树的遍历
            if (this.left != null){ 
                this.left.preOrder();
            }
            //递归实现右子树的遍历
            if (this.right != null ){ 
                this.right.preOrder();
            }
        }
    
        /** * 实现中序遍历 * 左 ------ 根 ----- 右 */
        public void infixOrder(){ 
            //递归实现左子树的遍历
            if (this.left != null) { 
                this.left.infixOrder();
            }
            //输出根节点
            System.out.println(this);
            if (this.right != null) { 
                this.right.infixOrder();
            }
        }
    
        /** * 实现后序遍历 * 左 --- 右 -- 根 */
        public void postOrder(){ 
            if (this.left != null) { 
                this.left.postOrder();
            }
            if (this.right != null) { 
                this.right.postOrder();
            }
            System.out.println(this);
        }
    
        /** * 实现先序查找 * 先序查找和先序遍历有着很多相似的地方 * 都需要按照先序遍历的顺序,只是查找需要提供一个value值,根据value值来确定返回 * @param value 需要查找的值 * @return value值对应的节点 */
        public TreeNode preOrderSearch(Integer value){ 
            System.out.println("开始先序查找");
            //如果需要查找的值就是当前的节点,那么直接返回当前节点
            if (this.value == value){ 
                return this;
            }
            //定义了一个结果集用来存储需要查找的值的节点
            TreeNode resNode = null;
            if (this.left != null) { 
                resNode= this.left.preOrderSearch(value);
            }
            //结果集不为空,代表在遍历查找左子树时找到了对应的元素
            if (resNode != null){ 
                return resNode;
            }
            if (this.right != null){ 
                resNode = this.right.preOrderSearch(value);
            }
            return resNode;
        }
    
        /** * 实现中序查找 * 左 根 右 * @param value * @return */
        public TreeNode infixOrderSearch(Integer value){ 
            System.out.println("开始中序遍历查找");
            TreeNode resNode = null;
            if (this.left != null) { 
                resNode = this.left.infixOrderSearch(value);
            }
            if (resNode != null){ 
                return resNode;
            }
            if (this.value == value){ 
                return this;
            }
            if (this.right != null){ 
                resNode = this.right.infixOrderSearch(value);
            }
            return resNode;
        }
    
        /** * 实现后序遍历查找 * * 左 --- 右 -- 根 * @param value * @return */
        public TreeNode postOrderSearch(Integer value){ 
            TreeNode resNode = null;
            if (this.left != null){ 
                resNode = this.postOrderSearch(value);
            }
            if (resNode != null){ 
                return resNode;
            }
            if (this.right != null){ 
                resNode = this.right.postOrderSearch(value);
            }
            if (resNode!=null){ 
                return resNode;
            }
            if (this.value == value){ 
                return this;
            }
            return resNode;
        }
    }

## 树 二叉树的常见面试题 ##

**树的面试题的解法通常是递归**

1.  对于树的结构来说,树分为根节点和左子树和右子树,想要访问到所有的节点,那么就要按照顺序依次把树的所有的左子树和右子树都访问到,而本身就是一个递归的结构,因此访问的方式也是递归的访问方式。

对于树的结构来说,树分为根节点和左子树和右子树,想要访问到所有的节点,那么就要按照顺序依次把树的所有的左子树和右子树都访问到,而本身就是一个递归的结构,因此访问的方式也是递归的访问方式。

树和二叉树的常见面试题其实就是关于树的操作,要熟练掌握树的遍历,树的插入和删除等操作。

[image-20200929144302469]: /images/20210724/31c82f344c9944de95c82b61ee45497e.png
[image-20200929145149140]: /images/20210724/f3f6338fd0ca41c896fdd04c499fdd14.png
[image-20200929145939637]: /images/20210724/1daec8a2c2864c04b0276afeff42e4cc.png
[image-20200929152041882]: /images/20210724/30d0de73811e4799a08b1b947314aa65.png
[image-20200929152601072]: /images/20210724/aa24a0b3d9534a24a7e0839bfda5fdb6.png