算法疑难(js实现)---9、二叉树的深度优先遍历

一、总结

一句话总结：

1、先序遍历：（根左右）

2、中序遍历：（左根右）

3、后序遍历：（左右根）

 1 1、
 2 先序遍历：（根左右）
 3 a、访问根节点（得到节点的值）
 4 b、递归的访问左子树
 5 c、递归的访问右子树
 6 
 7 2、
 8 中序遍历：（左根右）
 9 a、递归的访问左子树
10 b、访问根节点（得到节点的值）
11 c、递归的访问右子树
12 
13 3、
14 后序遍历：（左右根）
15 a、递归的访问左子树
16 b、递归的访问右子树
17 c、访问根节点（得到节点的值）
18 
19 //1、先序遍历二叉树
20 function preOrderTraversal(tree,ans){
21     //递归的终止条件：叶子节点
22     //递归的递推表达式：根左右
23     //递归的返回值：不需要
24 
25     //如果不是叶子节点，就递归的访问左右子树
26     if(tree){
27         //a、访问根节点（得到节点的值）
28         //console.log(tree.val);
29         ans.push(tree.val);
30         //b、递归的访问左子树
31         preOrderTraversal(tree.left,ans);
32         //c、递归的访问右子树
33         preOrderTraversal(tree.right,ans);
34     }else{
35         //console.log('#');
36         ans.push('#');
37     }
38 }
39 let ans=[];
40 preOrderTraversal(tree,ans);
41 console.log(ans);
42 
43 //2、中序遍历二叉树
44 function inOrderTraversal(tree,ans){
45     if(tree){
46         //a、递归的访问左子树
47         inOrderTraversal(tree.left,ans);
48         //b、访问根节点（得到节点的值）
49         ans.push(tree.val);
50         //c、递归的访问右子树
51         inOrderTraversal(tree.right,ans);
52     }else{
53         ans.push('#');
54     }
55 }
56 
57 //3、后序遍历二叉树
58 function postOrderTraversal(tree,ans){
59     if(tree){
60         //a、递归的访问左子树
61         postOrderTraversal(tree.left,ans);
62         //b、递归的访问右子树
63         postOrderTraversal(tree.right,ans);
64         //c、访问根节点（得到节点的值）
65         ans.push(tree.val);
66     }else{
67         ans.push('#');
68     }
69 }

二、二叉树的深度优先遍历

博客对应课程的视频位置：9、二叉树的深度优先遍历
https://www.fanrenyi.com/video/20/245

  1 <!DOCTYPE html>
  2 <html lang="en">
  3 <head>
  4     <meta charset="UTF-8">
  5     <title>二叉树的深度优先遍历</title>
  6 </head>
  7 <body>
  8 <!--
  9 需求：
 10 先序、中序、后序三种方式遍历二叉树
 11                 a
 12             b       c
 13          d     #  #    e
 14        #   f         #    #
 15          #   #
 16 
 17 先序遍历序列：['a','b','d','#','f','#','#','#','c','#','e','#','#']
 18 中序遍历序列：["#","d","#","f","#","b","#","a","#","c","#","e","#"]
 19 后序遍历序列：["#","#","#","f","d","#","b","#","#","#","e","c","a"]
 20 
 21 算法：
 22 递归
 23 
 24 1、
 25 先序遍历：（根左右）
 26 a、访问根节点（得到节点的值）
 27 b、递归的访问左子树
 28 c、递归的访问右子树
 29 
 30 2、
 31 中序遍历：（左根右）
 32 a、递归的访问左子树
 33 b、访问根节点（得到节点的值）
 34 c、递归的访问右子树
 35 
 36 3、
 37 后序遍历：（左右根）
 38 a、递归的访问左子树
 39 b、递归的访问右子树
 40 c、访问根节点（得到节点的值）
 41 
 42 -->
 43 <script>
 44     function TreeNode(val){
 45         this.val=val;
 46         this.left=null;
 47         this.right=null;
 48     }
 49 
 50     //根据二叉树的层次遍历的序列结果，创建二叉树
 51     function createTree_levelOrder(levelOrderArr) {
 52         let queue=[];
 53         let root=null;
 54 
 55         if(levelOrderArr[0]!==undefined){
 56             //1、找到根节点，将根节点加入到队列（层次遍历结果序列的第一个一定是根节点）
 57             let nodeVal=levelOrderArr.shift();
 58             root=new TreeNode(nodeVal);
 59             queue.push(root);
 60 
 61             //2、循环的将队列队首的元素出队，把和出队元素相关的元素加入到队列（循环中的元素为空，循环就运行完了）
 62 
 63             //队列不为空
 64             while(queue.length){
 65                 //1、将队列队首的元素出队（要么是整棵树的根节点、要么是子树的根节点）
 66                 let head= queue.shift();
 67                 //2、把和出队元素相关的元素加入到队列（先创建节点，根节点的左右孩子）
 68                 //a、创建左节点，将它加入到队列
 69                 nodeVal=levelOrderArr.shift();
 70                 if(nodeVal!='#'){
 71                     head.left=new TreeNode(nodeVal);
 72                     queue.push(head.left);
 73                 }
 74 
 75                 //b、创建右节点，将它加入到队列
 76                 nodeVal=levelOrderArr.shift();
 77                 if(nodeVal!='#'){
 78                     head.right=new TreeNode(nodeVal);
 79                     queue.push(head.right);
 80                 }
 81             }
 82         }
 83 
 84         return root;
 85     }
 86     let levelOrderArr=['a','b','c','d','#','#','e','#','f','#','#','#','#'];
 87     let tree=createTree_levelOrder(levelOrderArr);
 88     console.log(tree);
 89 
 90     // //1、先序遍历二叉树
 91     // function preOrderTraversal(tree,ans){
 92     //     //递归的终止条件：叶子节点
 93     //     //递归的递推表达式：根左右
 94     //     //递归的返回值：不需要
 95     //
 96     //     //如果不是叶子节点，就递归的访问左右子树
 97     //     if(tree){
 98     //         //a、访问根节点（得到节点的值）
 99     //         //console.log(tree.val);
100     //         ans.push(tree.val);
101     //         //b、递归的访问左子树
102     //         preOrderTraversal(tree.left,ans);
103     //         //c、递归的访问右子树
104     //         preOrderTraversal(tree.right,ans);
105     //     }else{
106     //         //console.log('#');
107     //         ans.push('#');
108     //     }
109     // }
110     // let ans=[];
111     // preOrderTraversal(tree,ans);
112     // console.log(ans);
113 
114     // //2、中序遍历二叉树
115     // function inOrderTraversal(tree,ans){
116     //     if(tree){
117     //         //a、递归的访问左子树
118     //         inOrderTraversal(tree.left,ans);
119     //         //b、访问根节点（得到节点的值）
120     //         ans.push(tree.val);
121     //         //c、递归的访问右子树
122     //         inOrderTraversal(tree.right,ans);
123     //     }else{
124     //         ans.push('#');
125     //     }
126     // }
127     // let ans=[];
128     // inOrderTraversal(tree,ans);
129     // console.log(ans);
130 
131     //3、后序遍历二叉树
132     function postOrderTraversal(tree,ans){
133         if(tree){
134             //a、递归的访问左子树
135             postOrderTraversal(tree.left,ans);
136             //b、递归的访问右子树
137             postOrderTraversal(tree.right,ans);
138             //c、访问根节点（得到节点的值）
139             ans.push(tree.val);
140         }else{
141             ans.push('#');
142         }
143     }
144     let ans=[];
145     postOrderTraversal(tree,ans);
146     console.log(ans);
147 
148 </script>
149 </body>
150 </html>