前序、中序、后序遍历的基础详解

2024-06-30 00:11| 来源: 网络整理| 查看: 265

在学习二叉树结构，最简单的方式就是遍历，所谓二叉树遍历是按照某种特定规则，依次对二叉树中的结点进行相应的操作，并且每个结点只操作，。访问结点所做的操作依赖于具体的应用问题。遍历是二叉树最重要的运算之一，也是二叉树上进行其它运算的基础。

按照规则，二叉树的遍历有：前序/中序/后序的递归结构遍历： 1. 前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点的操作发生在遍历其左右子树之前。 2. 中序遍历(Inorder Traversal)——访问根结点的操作发生在遍历其左右子树之中（间）。 3. 后序遍历(Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后。

如果按照前序，我们怎么遍历上图的结构，其实前序就是先遍历头结点，在遍历左子树最后遍历右子树。所以其顺序是：A B D NULL NULL NULL C E NULL NULL F NULL NULL.

中序：先访问左子树再访问头结点最后访问右子树。所以其顺序为：NULL,D,NULL,B,NULL,A,NULL,E,C,NULL,F,NULL.

后序：先访问左子树，再访问右子树，最后访问头结点，所以顺序为：

NULL,NULL,D,NULL,B,NULL,NULL,E,NULL,NULL,F,C,A.

看看程序

#include #include typedef int BTDataType; typedef struct BinaryTreeNode { BTDataType data; struct BinaryTreeNode* left; struct BinaryTreeNode* right; }BTNode; BTNode*BuyNode(BTDataType x) { BTNode*newnode = (BTNode*)malloc(sizeof(BTNode)); if (newnode == NULL) { printf("malloc fail\n"); exit(-1); } newnode->data = x; newnode->left = NULL; newnode->right = NULL; return newnode; } BTNode* CreatBinaryTree() { BTNode* node1 = BuyNode(1); BTNode* node2 = BuyNode(2); BTNode* node3 = BuyNode(3); BTNode* node4 = BuyNode(4); BTNode* node5 = BuyNode(5); BTNode* node6 = BuyNode(6); node1->left = node2; node1->right = node4; node2->left = node3; node4->left = node5; node4->right = node6; return node1; }

这是手动创建一个链表

void PostOrder(BTNode*root) { if (root == NULL) { printf("NULL "); return; } printf("%d ", root->data); PostOrder(root->left); PostOrder(root->right); } int main() { BTNode*node = CreatBinaryTree(); PostOrder(node); return 0; }

运用的递归求解。

中序：

void PostOrder(BTNode*root) { if (root == NULL) { printf("NULL "); return; } PostOrder(root->left); printf("%d ", root->data); PostOrder(root->right); } int main() { BTNode*node = CreatBinaryTree(); PostOrder(node); return 0; }

后序

void PostOrder(BTNode*root) { if (root == NULL) { printf("NULL "); return; } PostOrder(root->left); PostOrder(root->right); printf("%d ", root->data); } int main() { BTNode*node = CreatBinaryTree(); PostOrder(node); return 0; }

其实，在遍历是同样遍历的，只是打印的时机不同，所以，结果就不同

【本文地址】

公司简介

联系我们