有向图,无向图
环形图,无环图
二叉树 : 有向无环图
线性代数, 有序对,无序对
答案 A,B
答案B,D
所有层都是满的, 答案 A
要么有没子节点,如果有必须有两个子节点 , 答案 A,B
#如何构造二叉树? 用对象
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
<script type="text/javascript">
function Node (data, left, right) {
this.data = data;
this.left = left;
this.right = right;
}
function setTree () {
var root = new Node(1, null, null);
var node1 = new Node(2, null, null);
var node2 = new Node(3, null, null);
var node3 = new Node(4, null, null);
var node4 = new Node(5, null, null);
var node5 = new Node(6, null, null);
var node6 = new Node(6, null, null);
root.left = node1;
root.right = node2;
node1.left = node3;
node1.right = node4;
node2.left = node5;
node2.right = node6;
return root;
}
console.log(setTree());
</script>
如何遍历二叉树?
前,中,后 指的是 根节点是 第一个,中间,还是最后遍历的意思
前序: 根,左,右, : 1,2,4,5,3,6
中序: 左,中,右, : 4,2,5,1,3,6
后序: 左, 右, 中 : 4,5,2,6,3,1
前序: 1,2,4,8,9,5,3,6,7
中序: 8,4,9,2,5,1,6,3,7
后序: 8,9,4,5,2,6,7,3,1
代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
function perMid (per, mid) {
if(per.length == 0 || mid.length == 0){
return null;
}
if (per.length != mid.length) {
throw "数据有问题"
}
// 跟节点数据
var rootData = per[0];
// 根节点在中序遍历中的位置
var midRootIndex = mid.indexOf(rootData);
// 左子树中序遍历
// slice 是闭开截取数组
var leftMid = mid.slice(0,midRootIndex);
// 右子树中序遍历
var rightMid = mid.slice(midRootIndex + 1);
// 左子树的前序遍历
// 前序,第一个元素是 根节点,要刨除
var leftPer = per.slice(1,leftMid.length + 1);
//
var rightPer = per.slice(leftMid.length + 1);
// 下面是就是递归了.
var left = perMid(leftPer, leftMid);
var right = perMid(rightPer, rightMid);
// 创建 元素
var node = new Node(rootData, left, right);
return node;
}
var pre = [1,2,4,5,3,6];
var mid = [4,2,5,1,3,6]
var tree = perMid(pre, mid);
console.log(tree);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
function afterMid (after, mid) {
if(after.length == 0 || mid.length == 0){
return null;
}
if (after.length != mid.length) {
throw "数据有问题"
}
// 跟节点数据 // 在后序遍历中,最后一个是 根节点
var len = after.length;
var rootData = after[len - 1];
// 根节点在中序遍历中的位置
var midRootIndex = mid.indexOf(rootData);
// 左子树中序遍历
// slice 是闭开截取数组
var leftMid = mid.slice(0,midRootIndex);
// 右子树中序遍历
var rightMid = mid.slice(midRootIndex + 1 );
// 左子树的后序遍历
// 前序,第一个元素是 根节点,要刨除
var leftAfter = after.slice(0,leftMid.length);
// 右子树的后序遍历
var rightAfter = after.slice(leftMid.length,len - 1);
// 下面是就是递归了.
var left = afterMid(leftAfter, leftMid);
var right = afterMid(rightAfter, rightMid);
// 创建 元素
var node = new Node(rootData, left, right);
return node;
}
var after = [4,5,2,6,3,1];
var mid = [4,2,5,1,3,6];
var tree = afterMid(after,mid)
console.log(tree);
前序和后序能够确定 根节点
中序 加上根节点已知时, 能够确定子节点.
前序 + 后序, 是不能完全确定唯一的树的.
代码遍历二叉树
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
<script type="text/javascript">
function Node (data, left, right) {
this.data = data;
this.left = left;
this.right = right;
}
function setTree () {
var root = new Node(1, null, null);
var node1 = new Node(2, null, null);
var node2 = new Node(3, null, null);
var node3 = new Node(4, null, null);
var node4 = new Node(5, null, null);
var node5 = new Node(6, null, null);
var node6 = new Node(7, null, null);
root.left = node1;
root.right = node2;
node1.left = node3;
node1.right = node4;
node2.left = node5;
node2.right = node6;
return root;
}
console.log(setTree());
var tree = setTree();
// 前序遍历// 先序遍历
function pre (tree) {
if (tree == null) {
return
}
console.log(tree.data);
pre(tree.left);
pre(tree.right);
}
// 后序遍历
function later (tree) {
if (tree == null) {
return
}
later(tree.left);
later(tree.right);
console.log(tree.data)
}
// 中序遍历
function mid (tree) {
if (tree == null) {
return
}
mid(tree.left);
console.log(tree.data)
mid(tree.right);
}
later(tree);
================================================= 回顾第一遍
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
<script type="text/javascript">
// 创建一个节点
function Node (data, left, right) {
this.data = data;
this.left = left;
this.right = right;
}
// 创建一棵树
// [1,2,3,4,5,6,7]
// 遍历方式是 一层一层遍历
function setTree () {
// 创建 七个 节点
var arr = [];
// 有个问题, 如果元素都为undefined forEach 不会执行.
for(var i = 0; i < 7; i++) {
arr[i] = new Node(i + 1, null, null)
}
arr[0].left = arr[1];
arr[0].right = arr[2];
arr[1].left = arr[3];
arr[1].right = arr[4];
arr[2].left = arr[5];
arr[2].right = arr[6];
return arr[0];
}
var root = setTree();
var pre = [1,2,4,5,3,6,7];
var mid = [4,2,5,1,6,3,7];
var aft = [4,5,2,6,7,3,1];
// 第一个问题,
//根据 前序 中序还原树
function preMidTree (pre, mid) {
// 出口
if (pre.length != mid.length) {
throw "数据有问题"
}
if (pre.length == 0 || mid.length == 0) {
return
}
// 前序找到根节点
var rootData = pre[0];
// 中序找到根节点 的索引
var rootMidIndex = mid.indexOf(rootData);
// 找到左子树中序
var leftMid = mid.slice(0, rootMidIndex);
// 找到右子树中序
var rightMid = mid.slice(rootMidIndex + 1);
// 跟据length
// 找到左子树 前序
var leftPre = pre.slice(1,leftMid.length + 1);
// 找到右子树 前序
var rightPre = pre.slice(leftMid.length + 1);
// 递归
var left = preMidTree(leftPre, leftMid);
var right = preMidTree(rightPre, rightMid);
// 创建节点
var root = new Node(rootData, left, right);
return root
}
var root1 = preMidTree(pre, mid);
console.log(root1);
// 第二个问题
// 根据 后序 和 中序, 还原树
function aftMidTree (aft, mid) {
// 出口
if (aft.length != mid.length) {
throw "数据有问题"
}
if (aft.length == 0 || mid.length == 0) {
return
}
// 后序找到根节点
var len = aft.length;
var rootData = aft[len - 1];
// 中序找到根节点 的索引
var rootMidIndex = mid.indexOf(rootData);
// 找到左子树中序
var leftMid = mid.slice(0, rootMidIndex);
// 找到右子树中序
var rightMid = mid.slice(rootMidIndex + 1);
// 跟据length
// 找到左子树 后序
var leftAft = aft.slice(0,leftMid.length);
// 找到右子树 后序
var rightAft = aft.slice(leftMid.length, len - 1);
// 递归
var left = aftMidTree(leftAft, leftMid);
var right = aftMidTree(rightAft, rightMid);
// 创建节点
var root = new Node(rootData, left, right);
return root
}
前序遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
// 树 前序遍历 返回数组
function preArr (root, arr) {
var arr = arr || [];
arr.push(root.data);
if (root.left) {
preArr(root.left, arr);
}
if(root.right){
preArr(root.right, arr);
}
return arr;
}
中序遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
// 树 中序遍历 返回数组
function midArr (root, arr) {
var arr = arr || [];
if (root.left) {
midArr(root.left, arr);
}
arr.push(root.data);
if(root.right){
midArr(root.right, arr);
}
return arr;
}
后序遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
// 树 后序遍历 返回数组
function aftArr (root, arr) {
var arr = arr || [];
if (root.left) {
aftArr(root.left, arr);
}
if(root.right){
aftArr(root.right, arr);
}
arr.push(root.data);
return arr;
}
按层级遍历成数组
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 我记得不久前在哪里看过. 关键思路是要有一个中间数组.
// 不好递归啊!
function level (root, arr) {
// 需要一个层级 变量 n
var arr = [];
var nodelist = [root]
for ( ;nodelist.length; ) {
var node = nodelist.shift();
arr.push(node.data);
node.left && nodelist.push(node.left);
node.right && nodelist.push(node.right);
}
return arr;
}
var arr = level(root1);
console.log(arr);
反过来,我们根据按层级遍历的数组,还原成树 (前提是满二叉树,或者数组中用undefined,null占位?)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function level (root) {
// 需要一个层级 变量 n
var arr = [];
var nodelist = [root]
for ( ;nodelist.length; ) {
var node = nodelist.shift();
arr.push(node.data);
node.left && nodelist.push(node.left);
node.right && nodelist.push(node.right);
}
return arr;
}
var arr = level(root1);
console.log(arr);
