JS—二叉树的三种遍历和通过先\后序、中序生成二叉树

一、二叉树的基础知识

1、树是n（n>=0)个结点的有限集。n=0时称为空树。在任意一颗非空树中：
1）有且仅有一个特定的称为根（Root）的结点；
2）当n>1时，其余结点可分为m(m>0)个互不相交的有限集T1、T2、…、Tn，其中每一个集合本身又是一棵树，并且称为根的子树。

此外，树的定义还需要强调以下两点：
1）n>0时根结点是唯一的，不可能存在多个根结点，数据结构中的树只能有一个根结点。
2）m>0时，子树的个数没有限制，但它们一定是互不相交的

2、结点**：是数据结构中的基础，是构成复杂数据结构的基本组成单位。

3、结点的度：结点拥有的子树数目称为结点的度

4、二叉树**（Binary tree）是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简单，

​ 二叉树是n个有限元素的集合，该集合或者为空、或者由一个称为根（root）的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成，是有序树。当集合为空时，称该二叉树为空二叉树。在二叉树中，一个元素也称作一个结点

5、二叉树特点：

1）每个结点最多有两颗子树，所以二叉树中不存在度大于2的结点。
2）左子树和右子树是有顺序的，次序不能任意颠倒。
3）即使树中某结点只有一棵子树，也要区分它是左子树还是右子树。

6、二叉树的性质：

1）在二叉树的第i层上最多有2i-1 个节点 。（i>=1）
2）二叉树中如果深度为k,那么最多有2k-1个节点。(k>=1）
3）n0=n2+1 n0表示度数为0的节点数，n2表示度数为2的节点数。
4）在完全二叉树中，具有n个节点的完全二叉树的深度为[log2n]+1，其中[log2n]是向下取整

二、已知二叉树的结构，求出此二叉树的先，中，后序 ：

​ 利用前序序列根节点在前找到根节点，用根节点去中序序列划分成两部分，左部分是左子树，右部分是右子树。再利用子树长度去前序序列把前序序列中的左右子树找出来，同时可以找出根节点。递归进行此步骤，如果子树长度为0，则不需要生成子节点

/**已知二叉树，求出此二叉树的先，中，后序 */

class Node2 {

constructor(val) {

​ this.val = val; // Number

​ this.left; // Node

​ this.right; // Node

}

}

let a = new Node2(1);

let b = new Node2(2);

let c = new Node2(3);

let d = new Node2(4);

let e = new Node2(5);

let f = new Node2(6);

let g = new Node2(7);

let h = new Node2(8);

a.left = b;

a.right = c;

b.left = d;

d.right = g;

c.left = e;

c.right = f;

f.left = h;

let pre = []; //前序

let mid = []; //中序

let vin = []; //后序

/**先序遍历 */

function front(node) {

if (!node) {

​ return;

}

// 自己

pre.push(node.val);

// 左

front(node.left);

// 右

front(node.right);

}

/**中序遍历 */

function centre(node) {

if (!node) {

​ return;

}

// 左

centre(node.left);

// 自己

mid.push(node.val);

// 右

centre(node.right);

}

/**后序遍历 */

function rear(node) {

if (!node) {

​ return;

}

// 左

rear(node.left);

// 右

rear(node.right);

// 自己

vin.push(node.val);

}

front(a);

centre(a);

rear(a);

console.log("–先序–", pre);

console.log("–中序–", mid);

console.log("–后序–", vin);

三、已知树的先\后序，要求还原此二叉树

​ 1、已知二叉树的先序为{1,2,4,7,3,5,6,8}，和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。

/**JZ04 重建二叉树 */

function TreeNode(x) {

this.val = x;

this.left = null;

this.right = null;

}

let preList = [1, 2, 4, 7, 3, 5, 6, 8];

let vinList = [4, 7, 2, 1, 5, 3, 8, 6];

function reConstructBinaryTree(pre, vin) {

if (!pre.length || !vin.length) {

​ return null;

}

let rootVal = pre[0];

let node = new TreeNode(rootVal);

let i;/* i有两个含义，一个是根节点在中序遍历结果中的下标，另一个是当前左子树的节点个数*/

for (i = 0; i < vin.length; ++i) {

​ if (vin[i] === rootVal) {

​ break;

​ }

}

node.left = reConstructBinaryTree(pre.slice(1, i + 1), vin.slice(0, i));

node.right = reConstructBinaryTree(pre.slice(i + 1), vin.slice(i + 1));

return node;

}

let head = reConstructBinaryTree(preList, vinList)

rear(head);

console.log("–后序–", vin);

console.log("–根节点–", head);