查看並輸出二叉樹不同的地方： <!DOCTYPE html> <html lang="en"> <head> <meta charset="UTF-8"> <meta name="viewport" content="width=device-width, initial-scale=1.0"> < ...
查看並輸出二叉樹不同的地方：
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<title>Document</title>
</head>
<body>
<script>
function Node(value) {
this.value = value;
this.left = null;
this.right = null;
}
var nodeA = new Node("a");
var nodeB = new Node("b");
var nodeC = new Node("c");
var nodeD = new Node("d");
var nodeE = new Node("e");
var nodeF = new Node("f");
var nodeG = new Node("g");
nodeA.left = nodeB;
nodeA.right = nodeC;
nodeB.left = nodeD;
nodeB.right = nodeE;
nodeC.left = nodeF;
nodeC.right = nodeG;
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");
var g = new Node("g");
a.right = b;
a.left = c;
b.left = d;
b.right = e;
c.left = f;
c.right = g;
//要找到兩個二叉樹之間有什麼不同
//1.新增了節點
//2.刪除了節點
//3.修改了節點
//不同的地方，存入diffList中
function diffTree(root1, root2, diffList) {
var diff = diffList || [];
if (root1 == root2) return diff; //若兩者是同一顆樹，則直接返回diff
if (root1 == null && root2 != null) { //root2新增了一個節點
diff.push({
type: "新增",
origin: null,
new: root2
});
} else if (root1 != null && root2 == null) { //root2刪除了一個節點
diff.push({
type: "刪除",
origin: root1,
new: null
});
} else if (root1.value != root2.value) { //root2節點的值被修改了
diff.push({
type: "修改",
origin: root1.value,
new: root2.value
});
//二叉樹的節點值被修改，還需要再次判斷子節點
diffTree(root1.left, root2.left, diff); //判斷左子樹
diffTree(root1.right, root2.right, diff); //判斷右子樹
} else {
diffTree(root1.left, root2.left, diff); //判斷左子樹
diffTree(root1.right, root2.right, diff); //判斷右子樹
}
return diff;
}
var diffList = [];
var diff = diffTree(nodeA, a, diffList);
console.log(diff);
</script>
</body>
</html>
二叉樹diff演算法
