二叉树遍历

Posted on | In |
Words count in article: 430

这是百度前端学院2018上的一道js练习

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
var tree = {
  "id": 0,
  "name": "root",
  "left": {
      "id": 1,
      "name": "Simon",
      "left": {
          "id": 3,
          "name": "Carl",
          "left": {
              "id": 7,
              "name": "Lee",
              "left": {
                  "id": 11,
                  "name": "Fate"
              }
          },
          "right": {
              "id": 8,
              "name": "Annie",
              "left": {
                  "id": 12,
                  "name": "Saber"
              }
          }
      },
      "right": {
          "id": 4,
          "name": "Tony",
          "left": {
              "id": 9,
              "name": "Candy"
          }
      }
  },
  "right": {
      "id": 2,
      "name": "right",
      "left": {
          "id": 5,
          "name": "Carl",
      },
      "right": {
          "id": 6,
          "name": "Carl",
          "right": {
              "id": 10,
              "name": "Kai"
          }
      }
  }
}

假设id和name均不会重复，根据输入name找到对应的id

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function findIdByName(name) {
  var id;
  function node(tree) {
      if (tree) {
          if (tree.name == name) {
              id = tree.id;
          }
      node(tree.left);
      node(tree.right);
      }
  }
  node(tree);
  return id;
}
console.log(findIdByName("Annie")); // 8

假设id和name均不会重复，根据输入id找到对应的name

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function findNameById(id) {
  var name;
  function node(tree) {
      if (tree) {
          if (tree.id == id) {
              name = tree.name;
          }
      node(tree.left);
      node(tree.right);
      }
  }
  node(tree);
  return name;
}
console.log(findNameById("7")); // Lee

把这个对象中所有的名字以“前序遍历”的方式全部输出到console中

1
2
3
4
5
6
7
8
9
10
11
12
13
14
var dlr = [];
function getListWithDLR() {
  function node(tree) {
      if (tree) {
          dlr.push(tree.name);
          node(tree.left);
          node(tree.right);
      }
  }
  node(tree);
  console.log(dlr);
}
getListWithDLR();
//[ 'root','Simon','Carl','Lee','Fate','Annie','Saber','Tony','Candy','right','Carl','Carl','Kai' ]

把这个对象中所有的名字以“中序遍历”的方式全部输出到console中

1
2
3
4
5
6
7
8
9
10
11
12
13
14
var ldr = [];
function getListWithLDR() {
  function node(tree) {
      if (tree) {
          node(tree.left);
          ldr.push(tree.name);
          node(tree.right);
      }
  }
  node(tree);
  console.log(ldr);
}
getListWithLDR();
// [ 'Fate','Lee','Carl','Saber','Annie','Simon','Candy','Tony','root','Carl','right','Carl','Kai' ]

把这个对象中所有的名字以“后序遍历”的方式全部输出到console中

1
2
3
4
5
6
7
8
9
10
11
12
13
14
var lrd = [];
function getListWithLRD() {
  function node(tree) {
      if (tree) {
          node(tree.left);
          node(tree.right);
          lrd.push(tree.name);
      }
  }
  node(tree);
  console.log(lrd);
}
getListWithLRD();
// [ 'Fate','Lee','Saber','Annie','Carl','Candy','Tony','Simon','Carl','Kai','Carl','right','root' ]