二叉树遍历-c实现
2023-09-27 14:28:09 时间
这里主要是三种遍历,先序(preorder,NLR),中序(Inorder,LNR),后序(Postorder,LRN)
N:node,L:left,R:right
基本排序:先序(NLR,节点,左,右),中序(LNR,左,节点,右),后序(LRN,左,右,节点)
要点:在每一种排序里,必须遵守基本排序。看图:
为了更加直观的了解,看下面的c语言实现的代码,参考了:https://www.geeksforgeeks.org/tree-traversals-inorder-preorder-and-postorder/
#include<cstdio> #include<cstdlib> using namespace std; struct node{ int data; struct node* left; struct node* right; }; struct node* newNode(int data){ struct node* node = (struct node*)malloc(sizeof(struct node)); node->data=data; node->left=NULL; node->right=NULL; return node; } void printPostorder(struct node* node){ if(node == NULL) return; printPostorder(node->left); printPostorder(node->right); printf("%d ",node->data); } void printInorder(struct node* node){ if(node==NULL){ return; } printInorder(node->left); printf("%d ",node->data); printInorder(node->right); } void printPreorder(struct node* node){ if(node==NULL){ return; } printf("%d ",node->data); printPreorder(node->left); printPreorder(node->right); } int main(){ struct node *root=newNode(1); root->left=newNode(2); root->right=newNode(3); root->left->left=newNode(4); root->left->right=newNode(5); root->right->left=newNode(6); root->right->right=newNode(7); root->left->left->left=newNode(8); root->left->left->right=newNode(9); root->left->right->left=newNode(10); root->left->right->right=newNode(11); root->right->left->left=newNode(12); root->right->left->right=newNode(13); root->right->right->left=newNode(14); root->right->right->right=newNode(15); printf("\nPreorder raversal of binary tree is \n"); printPreorder(root); printf("\nInorder raversal of binary tree is \n"); printInorder(root); printf("\nPostorder raversal of binary tree is \n"); printPostorder(root); return 0; }
输出:
Preorder raversal of binary tree is 1 2 4 8 9 5 10 11 3 6 12 13 7 14 15 Inorder raversal of binary tree is 8 4 9 2 10 5 11 1 12 6 13 3 14 7 15 Postorder raversal of binary tree is 8 9 4 10 11 5 2 12 13 6 14 15 7 3 1
写一个中序输出的图解:
相关文章
- 数据结构基础 后序遍历和中序遍历还原二叉树
- 【算法】【链表模块】二叉树空间复杂度为O(1)的遍历方法(Morris算法)
- 快速判断二叉树先序遍历 后序遍历
- 二叉树的遍历
- 二叉树的遍历
- 二叉树遍历(前序、中序、后序)stack
- java编写二叉树以及前序遍历、中序遍历和后序遍历 .
- 100、【树与二叉树】leetcode ——105. 从前序与中序遍历序列构造二叉树+106. 从中序与后序遍历序列构造二叉树(C++版本)
- 【剑指offer】22从上往下打印二叉树
- 2022&2023华为OD机试 - 二叉树层次遍历(Python)
- 已知二叉树的先序遍历序列和中序遍历序列,输出该二叉树的后序遍历序列
- 二叉树的遍历实现
- 求二叉树的先序遍历
- [LeetCode] 1104. Path In Zigzag Labelled Binary Tree 之字形二叉树路径
- [LeetCode] Encode N-ary Tree to Binary Tree 将N叉树编码为二叉树
- [LeetCode] Path Sum IV 二叉树的路径和之四