# Binary Tree Traversal
## Overview
The combination of binary trees being data structures and traversal being an algorithm relates to classic problems, either directly or indirectly.
> If you can grasp the traversal of binary trees, the traversal of other complicated trees will be easy for you.
The following are some common ways to traverse trees.
- Depth First Traversals (DFS): In-order, Pre-order, Post-order
- Level Order Traversal or Breadth First or Traversal (BFS)
There are applications for both DFS and BFS.
Stack can be used to simplify the process of DFS traversal. Besides, since tree is a recursive data structure, recursion and stack are two key points for DFS.
Graph for DFS:
![binary-tree-traversal-dfs](https://tva1.sinaimg.cn/large/007S8ZIlly1ghluhzhynsg30dw0dw3yl.gif)
The key point of BFS is how to determine whether the traversal of each level has been completed. The answer is to use a variable as a flag to represent the end of the traversal of current level.
## Pre-order Traversal
The traversal order of pre-order traversal is `root-left-right`.
Algorithm Pre-order
1. Visit the root node and push it into a stack.
2. Pop a node from the stack, and push its right and left child node into the stack respectively.
3. Repeat step 2.
Conclusion: This problem involves the classic recursive data structure (i.e. a binary tree), and the algorithm above demonstrates how a simplified solution can be reached by using a stack.
If you look at the bigger picture, you'll find that the process of traversal is as followed. `Visit the left subtrees respectively from top to bottom, and visit the right subtrees respectively from bottom to top`. If we are to implement it from this perspective, things will be somewhat different. For the `top to bottom` part we can simply use recursion, and for the `bottom to top` part we can turn to stack.
## In-order Traversal
The traversal order of in-order traversal is `left-root-right`.
So the root node is not printed first. Things are getting a bit complicated here.
Algorithm In-order
1. Visit the root and push it into a stack.
2. If there is a left child node, push it into the stack. Repeat this process until a leaf node reached.
> At this point the root node and all the left nodes are in the stack.
3. Start popping nodes from the stack. If a node has a right child node, push the child node into the stack. Repeat step 2.
It's worth pointing out that the in-order traversal of a binary search tree (BST) is a sorted array, which is helpful for coming up simplified solutions for some problems.
## Post-order Traversal
The traversal order of post-order traversal is `left-right-root`.
This one is a bit of a challenge. It deserves the `hard` tag of LeetCode.
In this case, the root node is printed not as the first but the last one. A cunning way to do it is to:
Record whether the current node has been visited. If 1) it's a leaf node or 2) both its left and right subtrees have been traversed, then it can be popped from the stack.
As for `1) it's a leaf node`, you can easily tell whether a node is a leaf if both its left and right are `null`.
As for `2) both its left and right subtrees have been traversed`, we only need a variable to record whether a node has been visited or not. In the worst case, we need to record the status for every single node and the space complexity is `O(n)`. But if you come to think about it, as we are using a stack and start printing the result from the leaf nodes, it makes sense that we only record the status for the current node popping from the stack, reducing the space complexity to `O(1)`.
## Level Order Traversal
The key point of level order traversal is how do we know whether the traversal of each level is done. The answer is that we use a variable as a flag representing the end of the traversal of the current level.
![binary-tree-traversal-bfs](https://tva1.sinaimg.cn/large/007S8ZIlly1ghlui1tpoug30dw0dw3yl.gif)
Algorithm Level-order
1. Visit the root node, put it in a FIFO queue, put in the queue a special flag (we are using `null` here).
2. Dequeue a node.
3. If the node equals `null`, it means that all nodes of the current level have been visited. If the queue is empty, we do nothing. Or else we put in another `null`.
4. If the node is not `null`, meaning the traversal of current level has not finished yet, we enqueue its left subtree and right subtree respectively.
## Bi-color marking
We know that there is a tri-color marking in garbage collection algorithm, which works as described below.
- The white color represents "not visited".
- The gray color represents "not all child nodes visited".
- The black color represents "all child nodes visited".
Enlightened by tri-color marking, a bi-color marking method can be invented to solve all three traversal problems with one solution.
The core idea is as follow.
- Use a color to mark whether a node has been visited or not. Nodes yet to be visited are marked as white and visited nodes are marked as gray.
- If we are visiting a white node, turn it into gray, and push its right child node, itself, and it's left child node into the stack respectively.
- If we are visiting a gray node, print it.
Implementation of pre-order and post-order traversal algorithms can be easily done by changing the order of pushing the child nodes into the stack.
Reference: [LeetCode](https://github.com/azl397985856/leetcode/blob/master/thinkings/binary-tree-traversal.en.md)
没有合适的资源?快使用搜索试试~ 我知道了~
python1All Algorithms implemented in Python.zip
共1444个文件
py:1327个
txt:45个
md:26个
需积分: 1 0 下载量 186 浏览量
2024-10-01
15:29:05
上传
评论
收藏 8.17MB ZIP 举报
温馨提示
python python 学习 【python1】All Algorithms implemented in Python.zip
资源推荐
资源详情
资源评论
收起资源包目录
python1All Algorithms implemented in Python.zip (1444个子文件)
CODEOWNERS 981B
sample_data.csv 70KB
ex_data.csv 1KB
perceptron.py.DISABLED 7KB
get_user_tweets.py.DISABLED 2KB
get_imdbtop.py.DISABLED 1KB
Dockerfile 406B
.gitattributes 12B
.gitignore 1KB
pytest.ini 60B
example_wikipedia_image.jpg 476KB
output.jpg 116KB
PSNR-example-comp-10.jpg 104KB
lena.jpg 102KB
input.jpg 59KB
2D_problems.jpg 57KB
2D_problems_1.jpg 40KB
example_image.jpg 29KB
lena_small.jpg 7KB
project_euler_answers.json 63KB
devcontainer.json 1KB
loudness_curve.json 812B
settings.json 87B
DIRECTORY.md 66KB
CONTRIBUTING.md 11KB
README.md 5KB
README.md 5KB
README.md 4KB
README.md 3KB
local_weighted_learning.md 3KB
README.md 3KB
README.md 3KB
normal_distribution_quick_sort.md 2KB
README.md 1KB
pull_request_template.md 1KB
README.md 1KB
LICENSE.md 1KB
README.md 894B
README.md 746B
README.md 726B
README.md 722B
ABOUT.md 452B
README.md 441B
README.md 415B
README.md 374B
README.md 303B
README.md 295B
README.md 264B
README.md 58B
PSNR-example-base.png 4.31MB
original_image.png 82KB
gaussian.png 52KB
compressed_image.png 26KB
red_black_tree.py 25KB
loss_functions.py 24KB
graph_adjacency_matrix.py 22KB
graph_adjacency_list.py 21KB
wa_tor.py 20KB
primelib.py 20KB
sequential_minimum_optimization.py 20KB
area.py 19KB
index_calculation.py 19KB
volume.py 17KB
linear_discriminant_analysis.py 17KB
binary_search_tree_recursive.py 16KB
convex_hull.py 16KB
singly_linked_list.py 16KB
directed_and_undirected_weighted_graph.py 15KB
haralick_descriptors.py 15KB
word_search.py 15KB
dijkstra_algorithm.py 15KB
mfcc.py 14KB
convolution_neural_network.py 14KB
lib.py 14KB
viterbi.py 14KB
double_ended_queue.py 14KB
sol1.py 14KB
k_means_clust.py 12KB
binomial_heap.py 12KB
resistor_color_code.py 12KB
skip_list.py 12KB
multi_level_feedback_queue.py 12KB
diffie_hellman.py 12KB
input_data.py 12KB
simplex.py 12KB
n_body_simulation.py 12KB
binary_search.py 11KB
two_hidden_layers_neural_network.py 11KB
temperature_conversions.py 11KB
davis_putnam_logemann_loveland.py 11KB
md5.py 11KB
matrix_class.py 11KB
binary_search_tree.py 11KB
frequent_pattern_growth.py 11KB
tabu_search.py 11KB
weight_conversion.py 10KB
automatic_differentiation.py 10KB
lru_cache.py 10KB
basic_graphs.py 10KB
lfu_cache.py 10KB
共 1444 条
- 1
- 2
- 3
- 4
- 5
- 6
- 15
资源评论
武昌库里写JAVA
- 粉丝: 6995
- 资源: 3205
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
最新资源
- 塑料检测23-YOLO(v5至v11)、COCO、CreateML、Paligemma、TFRecord、VOC数据集合集.rar
- Python圣诞节倒计时与节日活动管理系统
- 数据结构之哈希查找方法
- 系统DLL文件修复工具
- 塑料、玻璃、金属、纸张、木材检测36-YOLO(v5至v11)、COCO、CreateML、Paligemma、TFRecord、VOC数据集合集.rar
- Python新年庆典倒计时与节日活动智能管理助手
- Nosql期末复习资料
- 数据结构排序算法:插入排序、希尔排序、冒泡排序及快速排序算法
- 2011-2024年各省数字普惠金融指数数据.zip
- 计算机程序设计员三级(选择题)
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功