树

树是一个类似于链表的二维结构，每个节点可以指向0个或多个其他节点

树形结构 - 图1

树具有以下特点：

单根：如果一个节点A指向了另一个节点B，仅能通过A直接找到B节点，不可能通过其他节点直接找到B节点
无环：节点的指向不能形成环

树的术语：

结点的度：某个节点的度 = 该节点子节点的数量
树的度：一棵树中，最大的节点的度为该树的度
结点的层：从根开始定义起，根为第1层，根的子结点为第2层，以此类推；
树的高度或深度：树中结点的最大层次
叶子节点：度为0的结点称为叶结点；
分支节点：非叶子节点
子节点、父节点：相对概念，如果A节点有一个子节点B，则A是B的父节点，B是A的子节点
兄弟节点：如果两个节点有同一个父节点，则它们互为兄弟节点
祖先节点：某个节点的祖先节点，是从树的根到该节点本身经过的所有节点
后代节点：如果A是B的祖先节点，B则是A的后代节点

树的代码表示法：

function Node(value) {
  this.value = value; // 节点中的数据
  this.children = []; // 指向其他节点的数组
}
var a = new Node("A");
var b = new Node("B");
var c = new Node("C");
var d = new Node("D");
var e = new Node("E");
var f = new Node("F");
a.children.push(b, c);
b.children.push(d, e, f);

二叉树

如果一颗树的度为2，则该树是二叉树

树形结构 - 图2

二叉树可以用下面的代码表示

function Node(value){
    this.value = value;
    this.left = null;
    this.right = null;
}

二叉树的相关算法

编写各种函数，实现下面的功能

对二叉树遍历打印
1. 前(先)序遍历 DLR (degree left right)
2. 中序遍历 LDR
3. 后序遍历 LRD
根据前序遍历和中序遍历结果，得到一颗二叉树
计算树的深度
查询二叉树
1. 深度优先 Depth First Search
2. 广度优先 Breadth First Search
比较两棵二叉树，得到它们的差异 ```javascript function Node(value) { this.value = value; this.left = null; this.right = null; }

// 前序遍历 function DLR(node) { if (!node) { return; } console.log(node.value); // 先自己 DLR(node.left); DLR(node.right); }

// 中序遍历 function LDR(node) { if (!node) { return; } LDR(node.left); console.log(node.value); LDR(node.right); }

// 后序遍历 function LRD(node) { if (!node) { return; } LRD(node.left); LRD(node.right); console.log(node.value); }

// 根据前序和中序遍历结果，得到一颗二叉树 function getTree(dlr, ldr) { if (dlr.length !== ldr.length) throw new Error(“无效的遍历值”); if (dlr.length === 0) return null;

var rootValue = dlr[0]; // 通过前序遍历的第一个字符，得到根节点的value值 var root = new Node(rootValue); // 创建根节点 var rootIndex = ldr.indexOf(rootValue); // 根节点在中序遍历中的位置

var leftLDR = ldr.substring(0, rootIndex); // 左边的中序遍历 var leftDLR = dlr.substr(1, leftLDR.length); // 左边的前序

var rightLDR = ldr.substr(rootIndex + 1); // 右边的中序 var rightDLR = dlr.substr(leftDLR.length + 1); // 右边的前序 root.left = getTree(leftDLR, leftLDR); root.right = getTree(rightDLR, rightLDR);

return root; }

// 计算树的深度 function getDeep(node) { if (!node) { return 0; } return 1 + Math.max(getDeep(node.left), getDeep(node.right)); }

// 深度优先搜索 function deepSearch(node, target) { if (!node) { return false; } console.log(node.value); if (node.value === target) { //自己就是 return true; // 找到了 } return deepSearch(node.left, target) || deepSearch(node.right, target); }

// 广度优先搜索 function breadthSearch(node, target) { function _breadthSearch(nodes) { if (nodes.length === 0) { // 数组没东西 return false; } var nextLayer = []; // 下一层的节点 for (var i = 0; i < nodes.length; i++) { console.log(nodes[i].value); if (nodes[i].value === target) { return true; } if (nodes[i].left) { nextLayer.push(nodes[i].left); } if (nodes[i].right) { nextLayer.push(nodes[i].right); } } return _breadthSearch(nextLayer); }

return _breadthSearch([node]); }

// 对比两个树的差异，返回差异结果（数组） function diff(node1, node2) { var result = []; if (!node1 && !node2) { return result; // 两个节点都没有值，不可能有差异，返回空数组即可 } if (!node1 && node2) { result.push({ type: “新增”, from: null, to: node2 }); return result; // 这种情况不需要继续往后比较了 } if (node1 && !node2) { result.push({ type: “删除”, from: node1, to: null }); return result; // 这种情况不需要继续往后比较了 } if (node1.value !== node2.value) { result.push({ type: “修改”, from: node1, to: node2 }); // 加入「修改」的变化 // 不能停止 } var leftDiff = diff(node1.left, node2.left); // 左树的差异 var rightDiff = diff(node1.right, node2.right); // 右树的差异

return result.concat(leftDiff).concat(rightDiff); // 合并差异 }

var node1 = getTree(“ABDGECF”, “GDBEAFC”); var node2 = getTree(“AKDECFT”, “DKEAFCT”);

var result = diff(node1, node2); console.log(result); ```