初探二叉树

前言

“八月的色彩是用金子铸就的，明亮而珍贵；八月的色彩是用阳光酿造的，芬芳而灿烂。”

未来的日子，愿你把自己调至最佳状态，缓缓努力，慢慢变好 Y(^o^)Y

定义

二叉树（binary tree）是指树中节点的度不大于 2 的有序树，它是一种最简单且最重要的树。

二叉树的递归定义为：二叉树是一棵空树，或者是一棵由一个根节点和两棵互不相交的，分别称作根的左子树和右子树组成的非空树；左子树和右子树又同样都是二叉树

二叉树作为一种很基础但是又很重要的数据结构，在某些场景下还是比较重要的。所以掌握二叉树的重要性就不言而喻了。

举个栗子：

var binaryTree = {
  value: 1,
  left: {
    value: 2,
    left: {
      value: 4
    }
  },
  right: {
    value: 3,
    left: {
      value: 5,
      left: {
        value: 7
      },
      right: {
        value: 8
      }
    },
    right: {
      value: 6
    }
  }
}

递归遍历

先序遍历

访问根–>遍历左子树–>遍历右子树;

var preListRec = []; //定义保存先序遍历结果的数组
var preOrderRec = function(node) {
    if (node) { //判断二叉树是否为空
        preListRec.push(node.value); //将结点的值存入数组中
        preOrderRec(node.left); //递归遍历左子树
        preOrderRec(node.right); //递归遍历右子树
    }
}
preOrderRec(tree);
console.log(preListRec)

中序遍历

遍历左子树–>访问根–>遍历右子树;

var inListRec = []; //定义保存中序遍历结果的数组
var inOrderRec = function(node) {
    if (node) { //判断二叉树是否为空
        inOrderRec(node.left); //递归遍历左子树
        inListRec.push(node.value); //将结点的值存入数组中
        inOrderRec(node.right); //递归遍历右子树
    }
}
inOrderRec(tree);
console.log(inListRec);

后序遍历

遍历左子树–>遍历右子树–>访问根;

var postListRec = []; //定义保存后序遍历结果的数组
var postOrderRec = function(node) {
    if (node) { //判断二叉树是否为空
        postOrderRec(node.left); //递归遍历左子树
        postOrderRec(node.right); //递归遍历右子树
        postListRec.push(node.value); //将结点的值存入数组中
    }
}
postOrderRec(tree);
console.log(postListRec);

非递归遍历

广度优先遍历

广度优先遍历是从二叉树的第一层（根结点）开始，自上至下逐层遍历；在同一层中，按照从左到右的顺序对结点逐一访问

实现原理：

使用数组模拟队列，首先将根结点归入队列。当队列不为空时，执行循环：取出队列的一个结点，如果该节点有左子树，则将该节点的左子树存入队列；如果该节点有右子树，则将该节点的右子树存入队列

var breadthList = []; // 定义保存广度遍历结果的数组
var breadthTraversal = function(node) {
    if (node) { // 判断二叉树是否为空
        var que = [node]; // 将二叉树放入队列 var que = []; que.push(node);
        while (que.length !== 0) { // 判断队列是否为空
            node = que.shift(); // 从队列中取出一个结点
            breadthList.push(node.value); // 将取出结点的值保存到数组
            if (node.left) que.push(node.left); // 如果存在左子树，将左子树放入队列
            if (node.right) que.push(node.right); // 如果存在右子树，将右子树放入队列
        }
    }
}
breadthTraversal(tree);
console.log(breadthList);

结语

如果这篇文章帮到了你，欢迎点赞👍和关注⭐️

文章如有错误之处，希望在评论区指正🙏🙏。