二叉树，二叉树遍历，二叉树搜索

向右看齐 2023-07-07 12:30 9阅读 0赞

## 树形结构 ##

树形结构应该就比较容易理解了，树是二维数据结构中的一种，至于说二叉树又是树的一种了。

树和图的区别在这里说明一下，重点：  
**树形结构为二维数据结构中的一种特殊结构**

1.树形结构有一个根节点
    2.树形结构没有回路（就是只能一直往下，有回路的称为图，树是图的一种）
    3.树形结构我们称为  有向循环图
    几个关键字，拓补结构，树，图，有向循环图

## 二叉树 ##

就三种，一种根节点，一种节点，一种叶子节点
    二叉树，就是只有两个枝的结构

二叉树代码实现：

//二叉树结构
        function Rout(value) {
            this.value = value;
            this.left = null;
            this.right = null;
        }
    
        // 赋值
        var a = new Rout("a");
        var b = new Rout("b");
        var c = new Rout("c");
        var d = new Rout("d");
        var e = new Rout("e");
        var f = new Rout("f");
        var g = new Rout("g");
    
        // 结构图
        a.left = b;
        a.right = c;
        b.left = d;
        b.right = e;
        c.left = f;
        c.right = g;

**跟节点应该好理解**

叶子节点：下边没有其他节点
    节点：既不是根节点，也不是叶子节点的普通节点

**满二叉树：**  
1.所有的叶子节点都在最底层  
2.每个非叶子节点都有两个子节点

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NjI0Mzg2_size_16_color_FFFFFF_t_70]

**完全二叉树：**  
若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。

国内定义

1.叶子节点都在最后一层或者倒数第二层
    2.叶子节点都向左聚拢

国际定义

1.叶子节点都在最后一层或者倒数第二层
    2.如果有叶子节点，就必然有两个叶子节点

**画了一个二叉树，这是一个满的二叉树，接下来我们说遍历，遍历分为三种：**

> 1.前序遍历  
> 2.中序遍历  
> 3.后序遍历

**前序遍历：深度优先原则  
先打印当前的，再打印左边的，再打印右边的  
中序：先打印左边的，再打印当前的，再打印右边的  
后序遍历：先打印左边的，再打印右边的，再打印当前的**

总的来说：  
专业的名词了解下：

> 前序遍历：先根次序遍历  
> 中序遍历：中根次序遍历  
> 后序遍历：后根次序遍历

前序遍历代码实现：

//输出 前序遍历
        function f1(root){
            //判断
            if(root == null) return;
            console.log(root.value);
            f1(root.left);
            f1(root.right);
        }
        //调用
        f1(a);

中序遍历代码实现：

//输出 中序遍历
        function f1(root) {
            //判断
            if (root == null) return;
            f1(root.left);
            console.log(root.value);
            f1(root.right);
        }
        //调用
        f1(a);

后序遍历代码实现：

//输出 后序遍历
        function f1(root) {
            //判断
            if (root == null) return;
            f1(root.left);
            f1(root.right);
            console.log(root.value);
        }
        //调用
        f1(a);

**二叉树的搜索，搜索肯定就分为两种搜了，应该很容易理解**  
深度优先  
广度优先

**深度搜索代码示例：**

// 深度搜索代码
        function dfsSearch(root,target){
            //判断  代码的严谨性 返回 true  或者  false
            if(root == null) return false;
            if(root.value == target) return true;
            //赋值
            var left = deepSearch(root.left,target);
            var right = deepSearch(root.right,target);
            //返回
            return left || right;
        }
    
        //调用 打印输出 搜索h节点是否存在
        console.log(dfsSearch(a,"h"));

**广度搜索代码：**

// 广度搜索代码
        function bfsSearch(rootlist,target){
            //判断 代码的严谨性
            if(rootlist == null || rootlist.length == 0) return false;
            //创建存储空间
            var childlist = [];
            //循环存储信息
            for(var i = 0;i < rootlist.length;i++){
                //判断为false时是否继续
                if(!rootlist[i]) continue;
                //判断
                if(rootlist[i] != null && rootlist[i].value == target){
                    return true;
                }else{
                    //添加左子树
                    childlist.push(rootlist[i].left);
                    //添加右子树
                    childlist.push(rootlist[i].right);
                }
            }
    
            //返回
            return bfsSearch(childlist,target);
        }
    
        //调用 打印输出 搜索h节点是否存在
        console.log(bfsSearch([a],"h"));

深搜代码，查找h是否存在，返回true或者false  
代码里面都是用到了大量的递归，都是跟链表的逆置是一个思想的

小拓展：  
**二叉树的比较**：判断两个二叉树是否相等

（1）首先，创建两个二叉树

//二叉树结构
        function Rout(value) {
            this.value = value;
            this.left = null;
            this.right = null;
        }
    
        //第一个二叉树
        // 赋值
        var a = new Rout("a");
        var b = new Rout("b");
        var c = new Rout("c");
        var d = new Rout("d");
        var e = new Rout("e");
        var f = new Rout("f");
        var g = new Rout("g");
    
        // 结构图
        a.left = b;
        a.right = c;
        b.left = d;
        b.right = e;
        c.left = f;
        c.right = g;
    
        //第二个二叉树
        // 赋值
        var a1 = new Rout("a");
        var b1 = new Rout("b");
        var c1 = new Rout("c");
        var d1 = new Rout("d");
        var e1 = new Rout("e");
        var f1 = new Rout("f");
        var g1 = new Rout("g");
    
        // 结构图
        a1.left = b1;
        a1.right = c1;
        b1.left = d1;
        b1.right = e1;
        c1.left = g1;
        c1.right = f1;

(2)比较两个二叉树是否相等

//比较是否相等
        function twiceOver(rootlist1, rootlist2) {
            //判断  代码的严谨性
            if (rootlist1 == rootlist2) return true; //为同一颗树
            if (rootlist1 == null && rootlist2 != null || rootlist1 != null && rootlist2 == null) return false;  //其中一个二叉树结构不同时
            if (rootlist1.value != rootlist2.value) return false;  //相同位置的值不相等时
            //赋值判断
            var twiceleft = twiceOver(rootlist1.left, rootlist2.left);   //判断左子树是否相等
            var twiceright = twiceOver(rootlist1.right, rootlist2.right);    //判断右子树是否相等
            //返回
            return twiceleft && twiceright;     //只要左右子树都相等二叉树才相等
        }
    
        //调用
        console.log(twiceOver(a, a1));

**面试中注意事项：**  
填空题和笔试题都有可能出现的  
1.给出前序中序还原二叉树，要求写出后序遍历  
2.给出后序中序还原二叉树，要求写出前序遍历  
注意：必须要有中序遍历，没有中序遍历，不能实现还原二叉树

**还原二叉树代码示例：**

1.根据前序、中序遍历，还原二叉树，进行后序遍历

//根据前序、中序遍历，还原二叉树，进行后序遍历
        var qian = ["a","b","d","e","c","f","g"];
        var zhong = ["d","b","e","a","f","c","g"];
    
        //构造函数
        function f2(qian,zhong){
            //判断 代码的严谨性
            if(qian == null || zhong == null || qian.length == 0 || zhong.length == 0 || qian.length != zhong.length) return null;
            //获取根节点
            var root = new Rout(qian[0]);
            //找到根节点中序遍历 中 的位置
            var index = zhong.indexOf(root.value);
    
            //分离前序遍历
            //前序遍历的左子树
            var qianleft = qian.slice(1,index + 1);
            //前序遍历的右子树
            var qianright = qian.slice(1 + index,qian.length);
    
            //分离中序遍历
            //中序遍历的左子树
            var zhongleft = zhong.slice(0,index);
            //中序遍历的右子树
            var zhongright = zhong.slice(1 + index,zhong.length);
    
            // 还原二叉树
            // 根据左子树还原二叉树的左子树
            root.left = f2(qianleft,zhongleft);
            // 根据右子树还原二叉树的右子树
            root.right = f2(qianright,zhongright);
            //返回
            return root;
    
        }
        // 输出 后序遍历
        var root = f2(qian,zhong);
        console.log(root.left);
        console.log(root.right);
        后序遍历
        console.log(root.left.left.value);
        console.log(root.left.right.value);
        console.log(root.left.value);
        console.log(root.right.left.value);
        console.log(root.right.right.value);
        console.log(root.right.value);
        console.log(root.value);

2.根据后序、中序遍历，还原二叉树，进行前序遍历

//根据后序、中序遍历，还原二叉树，进行前序遍历
        var hou = ["d", "e", "b", "f", "g", "c", "a"];
        var zhong = ["d", "b", "e", "a", "f", "c", "g"];
    
        //构造函数
        function f2(hou, zhong) {
            //判断  代码的严谨性
            if (hou == null || zhong == null || hou.length == 0 || zhong.length == 0 || hou.length != zhong.length) return null;
            //获取根节点
            var root = new Rout(hou[hou.length - 1]);
            //根据根节点获取中序遍历 中  的位置
            var index = zhong.indexOf(root.value);
    
            //分离后序遍历
            //后序遍历的左子树
            var houleft = hou.slice(0, index);
            //后序遍历的右子树
            var houright = hou.slice(index, hou.length - 1);
    
            //分离中序遍历
            //中序遍历的左子树
            var zhongleft = zhong.slice(0, index);
            //中序遍历的右子树
            var zhongright = zhong.slice(index + 1, zhong.length);
    
            //还原二叉树
            //根据左子树还原二叉树的左子树
            root.left = f2(houleft, zhongleft);
            // 根据右子树还原二叉树的右子树
            root.right = f2(houright, zhongright);
            //返回
            return root;
    
        }
    
        // 输出
        var root = f2(hou, zhong);
        console.log(root.left);
        console.log(root.right);
        // 前序遍历
        console.log(root.value);
        console.log(root.left.value);
        console.log(root.left.left.value);
        console.log(root.left.right.value);
        console.log(root.right.value);
        console.log(root.right.left.value);
        console.log(root.right.right.value);

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NjI0Mzg2_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200223124404385.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NjI0Mzg2,size_16,color_FFFFFF,t_70