二叉树及其遍历
2022/3/7 6:17:08
本文主要是介绍二叉树及其遍历,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
二叉树及其遍历
二叉树概念定义
什么是二叉树
二叉树特点是每个节点最多只能有两棵子树,且有左右之分的树。
注:关于数据结构——树的一些基本概念可以参考《树的概念及基本术语》 - CairBin's Blog
二叉树的基本性质
关于二叉树的基本性质前面已经写的很详细了,可以回顾文章《二叉树》 - CairBin's Blog
二叉树结构体定义
- 结构体定义及其构造函数
//链式二叉树结构体定义 typedef struct _BinTree { int data; //存放数据 struct _BinTree* lc; //左儿子 struct _BinTree* rc; //右儿子 //构造函数 _BinTree(int d, struct _BinTree* l = NULL, struct _BinTree* r = NULL) :data(d), lc(l), rc(r) {}; }Node;
- 析构函数
//析构函数 void destroyBinTree(Node* node) { //如果不存在该节点说明已经到该路径底部,则返回 if (node == NULL) return; //如果没到达该路径尽头则删除路上节点并继续向下走 //保存指向子节点的指针 Node* pl = node->lc; Node* pr = node->rc; delete node; //删除当前节点 node = NULL; //指针置为空,防止野指针 //递归,向下走 destroyBinTree(pl); destroyBinTree(pr); }
- 创建二叉树并写入数据
//创建二叉树结构并写入数据 //代码参考https://blog.csdn.net/u013575812/article/details/50129435 void buildBinTree(Node** node) { int data; cin >> data; if (data == -1) *node = NULL; else { *node = (Node*)malloc(sizeof(Node)); (*node)->data = data; buildBinTree(&(*node)->lc); buildBinTree(&(*node)->rc); } }
二叉树的遍历
宽度优先遍历(BFS)
层序遍历
图解分析
-
二叉树宽度优先遍历就是要一层一层去遍历,故对于二叉树又叫层序遍历。
-
以上图举例,BFS遍历顺序为EBCADFICH
注:
我们用队列实现搜索过程,关于队列的知识可以看文章《队列》 - CairBin's Blog
此处为了方便,就不手动写队列(queue)了,直接使用C++ STL模板里的Queue
代码
下面给出代码:
//BFS、层序遍历 void levelOrder(Node* node, queue<Node*>& que) { if (!node) return; Node* p = node; que.push(p); while (!que.empty()) { p = que.front(); //p设为队列头部元素 que.pop(); //队列尾部元素出队 cout << p->data << endl; if (p->lc) que.push(p->lc); if (p->rc) que.push(p->rc); } }
深度优先遍历(DFS)
按深度搜索的顺序访问二叉树,对根(父)节点、左儿子、右儿子进行组合,有三种访问顺序
- 先序遍历
- 中序遍历
- 后序遍历
这些遍历组合有如下性质
- 中序+先序——可确定该树
- 中序+后序——可确定该树
- 先序+后续,且不知道中序——不可确定该树
这些遍历又分别有两种方法:
- 递归方法
- 非递归方法
对于非递归方法需要用到数据结构——栈(stack),关于栈的知识可以参考文章
- 《栈的概念及性质》 - CairBin's Blog
- 《顺序栈的操作》 - CairBin's Blog
- 《链栈的操作》 - CairBin's Blog
这里同样用STL模板里的Stack
先序遍历
图解分析
我们依旧用该图
- 先序遍历顺序:父节点、左儿子、右儿子
- 本图访问顺序为:EBADCGFIH
代码
- 递归方法
//先序遍历,递归 void preOrder_A(Node* node) { if (node == NULL) return; cout << node->data << endl; preOrder_A(node->lc); preOrder_A(node->rc); }
- 非递归方法
//先序遍历,非递归 void preOrder_B(Node* node, stack<Node*> &st) { if (!node) return; Node* p = node; while (p || !st.empty()) { //从根节点一直往左入栈 while (p) { st.push(p); cout << p->data << endl; p = p->lc; } //访问栈,从左节点获得右边节点数据 if (!st.empty()) { p = st.top(); st.pop(); p = p->rc; } } }
中序遍历
图解分析
- 中序遍历顺序:左儿子、父节点、右儿子
- 本图遍历顺序:ABCDEFG
- 上述顺序正好为字典顺序,这并不是巧合,这是因为此图是个二叉搜索树,在进行中序遍历时实现了排序功能
- 中序遍历特征:已知根节点,从中序遍历结果来看,排在根节点左边的都在左子树上,排在根节点右边的都在右子树上。例如E是根节点,ABCD都在左子树
代码
- 递归方法
//中序遍历,递归 void inOrder_A(Node* node) { if (!node) return; inOrder_A(node->lc); cout << node->data << endl; inOrder_A(node->rc); }
- 非递归方法
//中序遍历,非递归 void inOrder_B(Node* node, stack<Node*>& st) { if (!node) return; Node* p = node; while (p || !st.empty()) { //左边一直入栈 while (p) { st.push(p); p = p->lc; } //从最左下儿子开始向右访问 if (!st.empty()) { p = st.top(); cout << p->data << endl; st.pop(); p = p->rc; } } }
后序遍历
图解分析
- 后序遍历顺序: 左儿子、右儿子、父节点
- 图中顺序:ACDBFHIGE
- 后续遍历最后一个节点是根节点
代码
- 递归方法
//后序遍历,递归 void postOrder_A(Node* node) { if (!node) return; postOrder_A(node->lc); postOrder_A(node->rc); cout << node->data << endl; }
- 非递归方法
//后序遍历,非递归 void postOrder_B(Node* node) { if (!node) return; stack<Node*> s; // 保证前序遍历 stack<Node*> t; // 反向输出左右根 Node* p = node; while (p || !s.empty()) { while (p) { s.push(p); t.push(p); p = p->lc; } if (!s.empty()) { p = s.top(); s.pop(); p = p->lc; } } while (!t.empty()) { cout << t.top()->data << endl; t.pop(); } }
本文参考
- 从上往下打印二叉树BFS(C++)_柠檬不加糖的博客-CSDN博客
- 二叉树DFS/BFS实现(C++)_usstmiracle的博客-CSDN博客
- 二叉树遍历总结:DFS+BFS【C++】 - Ueeei - 博客园 (cnblogs.com)
- C++基础]队列中的常用函数 - Horstxu - 博客园 (cnblogs.com)
- 二叉树_百度百科 (baidu.com)
- 《算法竞赛入门到进阶》—— 清华大学出版社
这篇关于二叉树及其遍历的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)