liu97

好好学习,天天向上

  • 博客
  • 随笔
  • 关于我
所有文章 友链

liu97

好好学习,天天向上

  • 博客
  • 随笔
  • 关于我

二叉树的遍历

2020-09-02

概念

二叉树(binary tree)是指树中节点的度不大于2的有序树,它是一种最简单且最重要的树。二叉树的递归定义为:二叉树是一棵空树,或者是一棵由一个根节点和两棵互不相交的,分别称作根的左子树和右子树组成的非空树;左子树和右子树又同样都是二叉树。
二叉树展示图
二叉树有四种主要的遍历方式:

  • 前序遍历:根节点 -> 左子树 -> 右子树
  • 中序遍历:左子树 -> 根节点 -> 右子树
  • 后序遍历:左子树 -> 右子树 -> 根节点
  • 层级遍历:第一层 -> 第二层 -> 第三层

以上面二叉树图片为例,遍历顺序为:

  • 前序遍历:[A, B, D, E, C, F, G]
  • 中序遍历:[D, B, E, A, F, C, G]
  • 后序遍历:[D, E, B, F, G, C, A]
  • 层级遍历:[A, B, C, D, E, F, G]

代码实现

前序遍历

1.递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
interface TreeNode {
val: number,
left: TreeNode,
right: TreeNode,
}

let list: TreeNode[] = [];
function preOrderRecursion(node: TreeNode): void{
if(node !== null){
list.push(node);
preOrderRecursion(node.left);
preOrderRecursion(node.right);
}
}
console.dir(list)

2.迭代

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function preOrderIteration(root: TreeNode): TreeNode[]{
let list: TreeNode[] = [];
let stack: TreeNode[] = [root];
let currentNode: TreeNode = root;
while(currentNode !== null || stack.length){
if(currentNode !== null){
list.push(currentNode);
stack.push(currentNode);
currentNode = currentNode.left;
}else{
currentNode = stack.pop();
currentNode = currentNode.right;
}
}

return list;
}

中序遍历

1.递归

1
2
3
4
5
6
7
8
9
let list: TreeNode[] = [];
function cenOrderRecursion(node: TreeNode): void{
if(node !== null){
cenOrderRecursion(node.left);
list.push(node);
cenOrderRecursion(node.right);
}
}
console.dir(list)

2.迭代

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function cenOrderIteration(root: TreeNode): TreeNode[]{
let list: TreeNode[] = [];
let stack: TreeNode[] = [root];
let currentNode: TreeNode = root;
while(currentNode !== null || stack.length){
if(currentNode !== null){
stack.push(currentNode);
currentNode = currentNode.left;
}else{
currentNode = stack.pop();
list.push(currentNode);
currentNode = currentNode.right;
}
}

return list;
}

后序遍历

1.递归

1
2
3
4
5
6
7
8
9
let list: TreeNode[] = [];
function aftOrderRecursion(node: TreeNode): void{
if(node !== null){
aftOrderRecursion(node.left);
aftOrderRecursion(node.right);
list.push(node);
}
}
console.dir(list)

2.迭代

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
function aftOrderIteration(root: TreeNode): TreeNode[]{
let list: TreeNode[] = [];
let stack: TreeNode[] = [];
let currentNode: TreeNode = root;
let last: TreeNode = null;
while(currentNode !== null || stack.length){
while(currentNode !== null){ // 把当前节点的所有左子节点压入栈
stack.push(currentNode);
currentNode = currentNode.left;
}
currentNode = stack[stack.length-1];
if(currentNode.right === null || currentNode.right === last){
list.push(currentNode);
stack.pop();
last = currentNode;
currentNode = null; // 进入这里为右节点和父节点,置为空后不会继续讲遍历过的节点重复压入栈
}else{
currentNode = currentNode.right; // 转向
}
}

return list;
}

层级遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function layerIteration(root: TreeNode): TreeNode[]{
let list: TreeNode[] = [];
let queue: TreeNode[] = [root];
while(queue.length){
let currentNode = queue.shift();
list.push(currentNode);
if(currentNode.left){
queue.push(currentNode.left);
}
if(currentNode.right){
queue.push(currentNode.right);
}
};
}
赏

谢谢你请我吃糖果

支付宝
微信
  • 数据结构
  • Blogs

扫一扫,分享到微信

微信分享二维码
谈1px问题
webpack4新特性及优化
  1. 1. 概念
  2. 2. 代码实现
    1. 2.1. 前序遍历
    2. 2.2. 中序遍历
    3. 2.3. 后序遍历
    4. 2.4. 层级遍历
Like Issue Page
Error: Comments Not Initialized
Login with GitHub
Styling with Markdown is supported
Powered by Gitment
© 2020 liu97
Hexo Theme Yilia by Litten
  • 所有文章
  • 友链

tag:

  • hexo
  • react
  • js
  • ajax
  • chrome
  • css
  • git
  • jquery
  • livereload
  • wamp
  • 数据结构
  • 算法
  • web缓存
  • 移动端
  • video
  • canvas
  • 笔试
  • webpack
  • 前端
  • 随笔
  • html5

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录(注意不是yilia根目录)执行以下命令:
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置:

      jsonContent:
        meta: false
        pages: false
        posts:
          title: true
          date: true
          path: true
          text: false
          raw: false
          content: false
          slug: false
          updated: false
          comments: false
          link: false
          permalink: false
          excerpt: false
          categories: false
          tags: true
    

  • 廖雪峰
  • 阮一峰
  • 大漠
  • 张鑫旭