二叉树的常见算法
2023-09-14 08:56:57 时间
二叉树的遍历
- 先序遍历指的就是先访问本节点,再访问该节点的左孩子和右孩子;
- 中序遍历指的就是:先访问左孩子,再访问本节点,最后访问右孩子;
- 后序遍历指的就是:先访问左右孩子,最后访问本节点。
- 层次遍历:按照树的每一层(高度)进行遍历。
深度遍历
- 递归实现:先序、中序、后序
- 非递归实现:先序、中序、后序
层次遍历
深度遍历
递归实现先序、中序、后序
#include <stdio.h> //声明树类型 typedef struct TREEtag TREEtagNode; struct TREEtag { int val; TREEtagNode *left; TREEtagNode *right; }; //访问 void get(TREEtagNode *node){ printf("%d\n",node->val); } //先序遍历 void r1(TREEtagNode *node){ if(node != NULL) { // get(node); // r1(node->left); // r1(node->right); } } //中序遍历 void r2(TREEtagNode *node){ if(node != NULL) { // r2(node->left); // get(node); // r2(node->right); } } //后序遍历 void r3(TREEtagNode *node){ if(node != NULL) { // r3(node->left); // r3(node->right); // get(node); } } int main () { TREEtagNode A0,A1,A2,A3,A4; A0.left = &A1; A0.right = &A2; A0.val = 10; A1.left = &A3; A1.right = NULL; A1.val = 2; A2.left = &A4; A2.right = NULL; A2.val = 7; A3.left = NULL; A3.right = NULL; A3.val = 5; A4.left = NULL; A4.right = NULL; A4.val = 9; printf("初始化成功\n"); printf("先序遍历:\n"); r1(&A0); printf("中序遍历:\n"); r2(&A0); printf("后序遍历:\n"); r3(&A0); return 0; }
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
初始化成功 先序遍历: 10 2 5 7 9 中序遍历: 5 2 10 9 7 后序遍历: 5 2 9 7 10
非递归实现:先序、中序、后序
#include <stdio.h> //声明树类型 typedef struct TREEtag TREEtagNode; struct TREEtag { int val; TREEtagNode *left; TREEtagNode *right; }; //访问 void get(TREEtagNode *node){ printf("%d\n",node->val); } #define Size 10 typedef struct stacktag { TREEtagNode *a[Size]; int top; }stack; //先序遍历 void r4(TREEtagNode *node){ if(node != NULL) { //初始化栈 stack Stack; Stack.top = -1; //初始化临时节点 TREEtagNode *p; //把根节点插入栈 Stack.a[++Stack.top] = node; //开始遍历 while(Stack.top != -1) { //取出元素 p = Stack.a[Stack.top--]; //操作 get(p); //存储元素:判断当前节点的左右节点是否存在,如果存在,则先存右元素,后存左元素 if(p->right != NULL) Stack.a[++Stack.top] = p->right; if(p->left != NULL) Stack.a[++Stack.top] = p->left; } } } //中序遍历 void r5(TREEtagNode *node){ if(node != NULL) { //初始化栈 stack Stack; Stack.top = -1; //初始化临时节点 TREEtagNode *p = NULL; p = node; //开始遍历 while(Stack.top != -1 || p != NULL) { while(p != NULL) { Stack.a[++Stack.top] = p; p = p->left; } if(Stack.top != -1) { p = Stack.a[Stack.top--]; //操作 get(p); p = p->right; } } } } //双栈法后序遍历 void r6(TREEtagNode *node){ if(node != NULL) { //初始化栈 stack Stack1; Stack1.top = -1; stack Stack2; Stack2.top = -1; //初始化临时节点 TREEtagNode *p; //把根节点插入栈 Stack1.a[++Stack1.top] = node; //开始遍历 while(Stack1.top != -1) { //取出元素 p = Stack1.a[Stack1.top--]; Stack2.a[++Stack2.top] = p; //存储元素:判断当前节点的左右节点是否存在,如果存在,则先存右元素,后存左元素 if(p->left != NULL) Stack1.a[++Stack1.top] = p->left; if(p->right != NULL) Stack1.a[++Stack1.top] = p->right; } while(Stack2.top != -1) { p = Stack2.a[Stack2.top--]; //操作 get(p); } } } int main () { TREEtagNode A0,A1,A2,A3,A4; A0.left = &A1; A0.right = &A2; A0.val = 10; A1.left = &A3; A1.right = NULL; A1.val = 2; A2.left = &A4; A2.right = NULL; A2.val = 7; A3.left = NULL; A3.right = NULL; A3.val = 5; A4.left = NULL; A4.right = NULL; A4.val = 9; printf("初始化成功\n"); printf("先序遍历:\n"); r4(&A0); printf("中序遍历:\n"); r5(&A0); printf("后序遍历:\n"); r6(&A0); return 0; }
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
初始化成功 先序遍历: 10 2 5 7 9 中序遍历: 5 2 10 9 7 后序遍历: 5 2 9 7 10
相关文章
- 用c语言实现二叉树层序遍历
- 【说站】python创建平衡二叉树的方法
- LeetCode 104. 二叉树的最大深度
- 剑指offer No.24 二叉树中和为某一值的路径
- 你需要采用前序遍历的方式,将一个二叉树转换成一个由括号和整数组成的字符串。
- 「数据结构与算法」手撕平衡二叉树
- 【算法】二叉树的最大深度
- Go 数据结构和算法篇(十六):二叉树的遍历
- 【综合笔试题】难度 1.5/5,常规二叉树爆搜题
- 前端工程师leetcode算法面试必备-简单的二叉树
- 前端leetcde算法面试套路之二叉树4
- 二叉树——堆的排序 TOP-K算法
- [数据结构]二叉树的顺序存储结构
- [数据结构]二叉树OJ(leetcode)
- JAVA语言实现二叉树的层次遍历的非递归算法及递归算法详解编程语言
- 【数据结构】之二叉树的java实现详解编程语言
- Java数据结构和算法(十)——二叉树详解编程语言
- 算法-二叉树的镜像详解编程语言
- 算法-二叉树的下一个结点详解编程语言
- 对称二叉树算法详解编程语言
- 深入探究:Linux下的二叉树数据结构解析(linux二叉树)
- python二叉树遍历的实现方法
- 二叉树前序遍历的非递归算法