本文用 js 去模拟一棵二叉树,对其进行遍历,二叉树的广度优先遍历(也叫非递归遍历)、二叉树的递归遍历(先序遍历、中序遍历、后序遍历)

  • 首先我们需要模拟一棵树像下面这样的一棵树
  • pic
    pic
  • 代码如下:
    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
    <script>
    //构建一个二叉树
    let tree = {
    value:1,
    left:{
    value:2,
    left:{
    value:4
    }
    },
    right:{
    value:3,
    left:{
    value:5,
    left:{
    value:7
    },
    right:{
    value:8
    }
    },
    right:{
    value:6
    }
    }
    };
    //存储输出的结果
    let result = [];
    let result1 = [];
    let result2 = [];
    let result3 = [];

    //递归算法:前序遍历(深度优先)
    function dlr (obj) {
    if (obj) {
    result.push(obj.value);
    arguments.callee(obj.left);
    arguments.callee(obj.right);
    }
    return result;
    }
    //递归算法:中序遍历(深度优先)
    function ldr (obj){
    if (obj) {
    arguments.callee(obj.left);
    result1.push(obj.value);
    arguments.callee(obj.right);
    }
    return result1;
    }
    //递归算法,后序遍历(深度优先)
    function lrd (obj) {
    if (obj) {
    lrd(obj.left);
    lrd(obj.right);
    result2.push(obj.value);
    }
    return result2;
    }
    //广度优先遍历
    function notRecursion (obj) {
    let arr = [];
    if (obj) arr.push(obj);
    while (arr.length != 0) {
    obj = arr.shift();
    result3.push(obj.value);
    if (obj.left) {arr.push(obj.left);}
    if (obj.right) {arr.push(obj.right);}
    }
    return result3;
    }

    console.log(dlr(tree));//[1, 2, 4, 3, 5, 7, 8, 6]
    console.log(ldr(tree));//[4, 2, 1, 7, 5, 8, 3, 6]
    console.log(lrd(tree));//[4, 2, 7, 8, 5, 6, 3, 1]
    console.log(notRecursion(tree));//[1, 2, 3, 4, 5, 6, 7, 8]
    </script>