数据结构————树

一、深度优先遍历和广度优先遍历

深度优先遍历

从根出发，尽可能深的搜索树的节点

技巧：

1. 访问根节点
2. 对根节点的children挨个进行深度优先遍历

广度优先遍历

从根出发，优先访问离根节点最近的节点

技巧：

1. 新建一个队列，把根节点入队
2. 把队头出队
3. 把队头的children挨个入队
4. 重复2和3步，直到队列为空为止

//树
const tree = {
    val: 'a',
    children: [
        {
            val: 'b',
            children: [
                { val: 'c', children: [] },
                { val: 'd', children: [] },
            ]
        },
        {
            val: 'e',
            children: [
                { val: 'f', children: [] },
                { val: 'g', children: [] },
            ]
        }
    ]
}
//深度优先遍历
const fun1 = (root)=>{
    console.log(root.val);
    root.children.forEach(fun1);
}
fun1(tree)
//广度优先便利
const fun2 = (root) => {
    const arr=[root]
    while (arr.length > 0) {
        var item = arr.shift()
        console.log(item.val);
        item.children.forEach(item => {
            arr.push(item)
        })
    }
}
fun2(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

前序、中序、后序遍历

前序遍历(左、右)

const tree = {
    val: '1',
    left:{
        val:'2',
        left: { val: '4', left: null, right: null },
        right: { val: '5', left: null, right: null },
    },
    right: {
        val: '3',
        left: { val: '6', left: null, right: null },
        right: { val: '7', left: null, right: null },
    }
}

//递归
var preorderTraversal = function (root) {
    let arr=[]
    var fun = (node) => {
        if (node) {
            //先根节点
            arr.push(node.val)
            //遍历左子树
            fun(node.left)
            //遍历右子树
            fun(node.right)
        }
    }
    fun(root)
    return arr
}
console.log(preorderTraversal(tree));//['1', '2', '4', '5', '3', '6', '7']

//非递归
var preorderTraversalTwo=function(root){
    if (!root) return [];
    let arr = []
    //根节点入栈
    let stack = [root]
    while (stack.length) {
        let current = stack.pop()
        arr.push(current.val)
        current.right ? stack.push(current.right) :null
        current.left ? stack.push(current.left):null
    }
    return arr
}
console.log(preorderTraversalTwo(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

中序遍历（左、中，右）

const tree = {
    val: '1',
    left:{
        val:'2',
        left: { val: '4', left: null, right: null },
        right: { val: '5', left: null, right: null },
    },
    right: {
        val: '3',
        left: { val: '6', left: null, right: null },
        right: { val: '7', left: null, right: null },
    }
}

//递归
var inorderTraversal = function (root) {
    let arr=[]
    var fun = (node) => {
        if (node) {
            //遍历左子树
            fun(node.left)
            //根节点
            arr.push(node.val)
            //遍历右子树
            fun(node.right)
        }
    }
    fun(root)
    return arr
}
console.log(inorderTraversal(tree));

//非递归
var inorderTraversalTwo=function(root){
    if (!root) return [];
    let arr = []
    let stack = []
    let o=root
    while (stack.length || o) {
        while (o) {
            stack.push(o)
            o=o.left
        }
        const n = stack.pop();
        arr.push(n.val)
        o=n.right
    }
    return arr
}
console.log(inorderTraversalTwo(tree));//['4', '2', '5','1', '6', '3','7']
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

后序遍历（左、右、中）

const tree = {
    val: '1',
    left:{
        val:'2',
        left: { val: '4', left: null, right: null },
        right: { val: '5', left: null, right: null },
    },
    right: {
        val: '3',
        left: { val: '6', left: null, right: null },
        right: { val: '7', left: null, right: null },
    }
}

//递归
var postorderTraversal = function (root) {
    let arr=[]
    var fun = (node) => {
        if (node) {
            //遍历左子树
            fun(node.left)
            //遍历右子树
            fun(node.right)
            //根节点
            arr.push(node.val)
        }
    }
    fun(root)
    return arr
}
console.log(postorderTraversal(tree));['4', '5', '2','6', '7', '3','1']

//非递归
var postorderTraversalTwo=function(root){
    if (!root) return [];
    let arr = []
    //根节点入栈
    let stack = [root]
    while (stack.length) {
        let current = stack.pop()
        arr.unshift(current.val)
        current.left ? stack.push(current.left) : null
        current.right ? stack.push(current.right) : null
    }
    return arr
}
console.log(postorderTraversalTwo(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