二叉树概念小谈

作者: json_q | 来源:发表于2019-11-09 10:36 被阅读0次

二叉树概念小谈
小谈“概念”、与“概念不清”。
12.树Tree（2）
浅谈（二叉树，真，满，完全）
从零开始学数据结构和算法(七) huffman 树与 AVL 树
JavaScript和树（二叉树）
java实现堆排序（大根堆）
二叉排序树BST
二叉树的基本概念与遍历方法实现
自己动手作图深入理解二叉树、满二叉树及完全二叉树

二叉树概念

二叉树是一个层级的数据结构，每一个二叉树都包含头节点或者子节点，并且二叉树的子节点最多是两个，如下几个图都是二叉树

image.png

二叉树的性质（基本的二叉树）

二叉树必须要有一个头节点
二叉树的子节点最多是两个
二叉树节点i的左子节点的索引是2i + 1,右子节点的索引是2i + 2
二叉树节点i的父节点索引是(i - 1) / 2, 向下取整
根节点没有父节点

二叉树的实现

网上的二叉树大多是按照数组的值去判断的，最后形成的二叉树可能是层次很乱的二叉树，但是如果就是想形成一个从左到右依次排列的二叉树的话，那种方法可能不行，除非数组的数据很好，然后自己写了一个弄了一下。

const arr = [4, 2, 3, 5, 7, 1, 6];

    const tree = function() {
      const CreateNode = function(value, left, right) {
        this.value = value;
        this.left = left;
        this.right = right;
      };

      let headList = [];
      let childList = [];
      this.root = null;

      this.insert = function(value) {
        const dom = new CreateNode(value, null, null); // 根节点的左右节点都是null

       // 判断有没有根节点，没有的话设置根节点
        if (!this.root) {
          this.root = dom;
          headList.push(this.root);

          return;
        }

        if (headList.length * 2 === childList.length) {
          headList = childList;
          childList = [];
        }

        for (let i = 0; i < headList.length; i++) {
          if (!headList[i].left) {
            headList[i].left = dom;
            childList.push(dom);

            return;
          }

          if (!headList[i].right) {
            headList[i].right = dom;
            childList.push(dom);

            return;
          }
        }
      };
    };

    const twoTree = new tree();

    arr.forEach(item => {
      twoTree.insert(item);
    });

    console.log(twoTree);

二叉树遍历

说到二叉树我们经常会提到的是二叉树的遍历，二叉树的遍历分为前序遍历，中序遍历，后序遍历和层次遍历，我们依次说明一下这几种情况，需要注意的是，如果遍历到对应节点时候，如果改节点有子节点，需要先让该节点和子节点重复以上动作，下面就用这个二叉树为例，分别写入前中后序遍历

image.png

前序遍历

前序遍历是先中，在左，在右的过程如果把上面的数组用前序遍历的话就是4， 2, 5， 7，3， 1， 6，递归遍历代码如下

// 前序遍历
    function prevTraverse(node) {
      if (node === null) return;

      console.log(node.value);
      prevTraverse(node.left);
      prevTraverse(node.right);
    }
  
   // twoTree 接上面的代码
   prevTraverse(twoTree.root);

这是递归的方式，如果用非递归的方式怎么做了，这里根据牛客网左神的视频，总结一下思路
注意以下节点都是以节点值为名称称呼节点，如节点4就是表示节点值为4的节点，也就是上图根节点

1：新建一个栈，把节点为4的节点（此时这里是根节点）放入栈中
2：抛出节点4，然后把节点4的右子节点先压入栈中，在把左子节点压入栈中
3：重复步骤2，直到栈中没有值，抛出来的值就是先序遍历

中序遍历

中序遍历是先左，在中，在右，按照上面的例子中序遍历的结果就是5,2,7,4,1,3,6，递归代码如下

// 中序遍历
    function middleTraverse(node) {
      if (node === null) return;

      middleTraverse(node.left);
      console.log(node.value);
      middleTraverse(node.right);
    }

middleTraverse(twoTree.root);

这是递归的方式，如果是非递归的怎么办了，一样提供思路

1：定义一个栈和一个变量cur，把节点4也就是根节点压入栈中，并设置cur等于根节点
2：让cur = cur.left,压入栈中
3：重复步骤二直到cur===null,然后抛出节点node,设置cur=node.right,压入栈中重复步骤二
4：直到栈空，抛出来的值就是中序遍历

后序遍历

后续遍历是先左，在右，在中，用上面的例子来说就是5,7,2,1.6.3,4，递归代码如下

function lastTraverse(node) {
      if (node === null) return;

      lastTraverse(node.left);
      lastTraverse(node.right);
      console.log(node.value);
    }
lastTraverse(twoTree.root);

这是递归的方式，如果是非递归的方式怎么办，思路如下