前序、中序、后序遍历的基础详解 |
您所在的位置:网站首页 › 中序遍历和先序遍历 › 前序、中序、后序遍历的基础详解 |
在学习二叉树结构,最简单的方式就是遍历,所谓二叉树遍历是按照某种特定规则,依次对二叉树中的结点进行相应的操作,并且每个结点只操作,。访问结点所做的操作依赖于具体的应用问题。遍历是二叉树最重要的运算之一,也是二叉树上进行其它运算的基础。 按照规则,二叉树的遍历有:前序/中序/后序的递归结构遍历: 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; }其实,在遍历是同样遍历的,只是打印的时机不同,所以,结果就不同 |
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |