如何通过数据结构二叉树的遍历实现高效查询？

本文共计817个文字，预计阅读时间需要4分钟。

前序、中序及后序遍历+学习二叉树结构，最简单的方式就是遍历。所谓二叉树遍历（Traversal）就是按照某种特定的规则，依次访问二叉树中的所有节点，且每个节点只访问一次。

前序、中序以及后序遍历

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

按照规则，二叉树的遍历有：前序/中序/后序的递归结构遍历：

1. 前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点的操作发生在遍历其左右子树之前。

2. 中序遍历(Inorder Traversal)——访问根结点的操作发生在遍历其左右子树之中（间）。

3. 后序遍历(Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后。

由于被访问的结点必是某子树的根，所以N(Node）、L(Left subtree）和R(Right subtree）又可解释为根、根的左子树和根的右子树。NLR、LNR和LRN分别又称为先根遍历、中根遍历和后根遍历。

// 二叉树前序遍历 void PreOrder(BTNode* root); // 二叉树中序遍历 void InOrder(BTNode* root); // 二叉树后序遍历 void PostOrder(BTNode* root);

下面主要分析前序递归遍历，中序与后序图解类似，同学们可自己动手绘制。

前序遍历

前序遍历递归图解：

代码解析：

#define _CRT_SECURE_NO_WARNINGS 1 #include<stdio.h> #include<assert.h> #include<stdlib.h> typedef int BTDataType; typedef struct BinaryTreeNode { BTDataType data; struct BinaryTreeNode* left; struct BinaryTreeNode* right; }BTNode; BTNode* BuyNode(BTDataType x) { BTNode* node = (BTNode*)malloc(sizeof(BTNode)); if (node == NULL) { perror("malloc fail"); return; } node->data = x; node->left = NULL; node->right = NULL; return node; } BTNode* CreatTree() { BTNode* node1 = BuyNode(1); BTNode* node2 = BuyNode(2); BTNode* node3 = BuyNode(3); BTNode* node4 = BuyNode(4); BTNode* node5 = BuyNode(5); BTNode* node6 = BuyNode(6); BTNode* node7 = BuyNode(7); node1->left = node2; node1->right = node4; node2->left = node3; node2->right = NULL; node4->left = node5; node4->right = node6; return node1; } //前序排列 void PreOrder(BTNode* root) { if (root==NULL) { printf("NULL "); return; } printf("%d ",root->data); PreOrder(root->left); PreOrder(root->right); } int main() { BTNode* root = CreatTree(); PreOrder(root); printf("\n"); return 0; }

中序遍历

中序遍历递归图解：

代码解析：

void InOrder(BTNode* root) { if (root == NULL) { printf("NULL "); return; } InOrder(root->left); printf("%d ", root->data); InOrder(root->right); }

后序遍历

后序遍历递归图解：

代码解析：

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