<你想看的我这里都有😎 >
二叉树的遍历
概念：二叉树遍历是按照某种特定的规则，依次对二叉树中的节点进行相应的操作，并且每个节点只操作一次遍历是二叉树上最重要的运算之一，也是二叉树上进行其它运算的基础。
二叉树的递归定义：二叉树是一棵空树，或者是一棵由一个根节点和两棵互不相交的，分别称作根的左子树和右子树组成的非空树，左子树和右子树又同样都是二叉树。
包含内容：
- 前序遍历——访问根结点的操作发生在遍历其左右子树之前，即根->左->右
- 中序遍历——访问根结点的操作发生在遍历其左右子树之中，即左->根->右
- 后序遍历——访问根结点的操作发生在遍历其左右子树之后，即左->右->根
为了方便学习，我们将空的位置仍然以NULL表示
模拟实现二叉树（链式二叉树）
#include <stdio.h> #include <assert.h> #include <stdlib.h> typedef int BTDataType; typedef struct BinaryTreeNode { BTDataType data; struct BinaryTreeNode* left; struct BinaryTreeNode* right; }TreeNode; TreeNode* BuyTreeNode(int x) { TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode)); assert(node); node->data = x; node->left = NULL; node->right = NULL; return node; } TreeNode* CreatTree() { TreeNode* node1 = BuyTreeNode(1); TreeNode* node2 = BuyTreeNode(2); TreeNode* node3 = BuyTreeNode(3); TreeNode* node4 = BuyTreeNode(4); TreeNode* node5 = BuyTreeNode(5); TreeNode* node6 = BuyTreeNode(6); node1->left = node2; node1->right = node4; node2->left = node3; //node2->right = NULL; //node3->left = NULL; //node3->right = NULL; node4->left = node5; node4->right = node6; //node5->left = NULL; //node5->right = NULL; //node6->left = NULL; //node6->right= NULL; return node1; } int main() { TreeNode* root = CreatTree(); return 0; }
前序遍历
前序遍历的实现
#include <stdio.h> #include <assert.h> #include <stdlib.h> typedef int BTDataType; typedef struct BinaryTreeNode { BTDataType data; struct BinaryTreeNode* left; struct BinaryTreeNode* right; }TreeNode; TreeNode* BuyTreeNode(int x) { TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode)); assert(node); node->data = x; node->left = NULL; node->right = NULL; return node; } TreeNode* CreatTree() { TreeNode* node1 = BuyTreeNode(1); TreeNode* node2 = BuyTreeNode(2); TreeNode* node3 = BuyTreeNode(3); TreeNode* node4 = BuyTreeNode(4); TreeNode* node5 = BuyTreeNode(5); TreeNode* node6 = BuyTreeNode(6); node1->left = node2; node1->right = node4; node2->left = node3; //node2->right = NULL; //node3->left = NULL; //node3->right = NULL; node4->left = node5; node4->right = node6; //node5->left = NULL; //node5->right = NULL; //node6->left = NULL; //node6->right= NULL; return node1; } void PrevOrder(TreeNode* root) { if(root == NULL) { printf("N "); return; } printf("%d ", root->data); PrevOrder(root->left); PrevOrder(root->right); } int main() { TreeNode* root = CreatTree(); PrevOrder(root); return 0; }
实现步骤：
1、在完成一个二叉树的基础上，我们实现了前序遍历的理论变现，即根->左->右
2、先令前序遍历函数接收总根节点的值（单链表的头）
3、进入函数后判断此时的根节点（1）是否为空，若为空则打印N表示空，若不为空则打印对应的值（1）
4、此后递归的读取当前结点（1）的左子树的根节点（3），若该结点不为空则打印对应的值（3），然后继续递归读取其左子树的根节点（NULL），此时结点为空打印N后返回上一次的位置（3），然后执行当前结点（3）的右递归，当前结点的右子树的根节点（NULL）为空打印N后结束，返回上一次的位置（2）（到这里整个左子树最底层的一个PrevOrder已经结束了），然后执行当前结点（2）的右递归，当前结点的右子树的根节点（NULL）为空打印N后结束，返回上一次位置（1）（到这里整个左子树的倒数第二个PrevOrder已经结束了）
5、接下俩就应该去读取（1）的右子树的根节点（4）了（因为到这里第一个PrevOrder的左递归才算完全结束，现在开始右递归）
6、（4）不为空打印对应的值（4），然后继续递归读取其左子树的根节点（5），不为空打印对应的值（5），然后继续递归读取其左子树的根节点（NULL）为空打印N后返回上一次的位置（5），然后继续递归读取其右子树的根节点（NULL）为空打印N后返回上一次的位置（4）（到这里整个右子最底层的一个PrevOrder已经结束了）然后继续递归读取其右子树的根节点（6），不为空打印对应的值（6），然后继续递归读取其左子树的根节点（NULL）为空打印N后返回上一次的位置（6），然后继续递归读取其右子树的根节点（NULL）为空后打印N后返回上一次的位置（4）
7、至此，该二叉树的前序遍历完成
一共用了五次PrevOrder，左子树两次，右子树两次，主二叉树一次
二叉树的递归遍历图
中序遍历
中序遍历的实现
#include <stdio.h> #include <assert.h> #include <stdlib.h> typedef int BTDataType; typedef struct BinaryTreeNode { BTDataType data; struct BinaryTreeNode* left; struct BinaryTreeNode* right; }TreeNode; TreeNode* BuyTreeNode(int x) { TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode)); assert(node); node->data = x; node->left = NULL; node->right = NULL; return node; } TreeNode* CreatTree() { TreeNode* node1 = BuyTreeNode(1); TreeNode* node2 = BuyTreeNode(2); TreeNode* node3 = BuyTreeNode(3); TreeNode* node4 = BuyTreeNode(4); TreeNode* node5 = BuyTreeNode(5); TreeNode* node6 = BuyTreeNode(6); node1->left = node2; node1->right = node4; node2->left = node3; //node2->right = NULL; //node3->left = NULL; //node3->right = NULL; node4->left = node5; node4->right = node6; //node5->left = NULL; //node5->right = NULL; //node6->left = NULL; //node6->right= NULL; return node1; } void InOrder(TreeNode* root) { if (root == NULL) { printf("N "); return; } InOrder(root->left); printf("%d ", root->data); InOrder(root->right); } int main() { TreeNode* root = CreatTree(); InOrder(root); return 0; }
实现步骤：中序遍历只是将前序遍历的PrevOrder中的 (root->data)与 (root->left)交换了位置，具体实现内容建议自行尝试
后序遍历
后序遍历的实现
#include <stdio.h> #include <assert.h> #include <stdlib.h> typedef int BTDataType; typedef struct BinaryTreeNode { BTDataType data; struct BinaryTreeNode* left; struct BinaryTreeNode* right; }TreeNode; TreeNode* BuyTreeNode(int x) { TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode)); assert(node); node->data = x; node->left = NULL; node->right = NULL; return node; } TreeNode* CreatTree() { TreeNode* node1 = BuyTreeNode(1); TreeNode* node2 = BuyTreeNode(2); TreeNode* node3 = BuyTreeNode(3); TreeNode* node4 = BuyTreeNode(4); TreeNode* node5 = BuyTreeNode(5); TreeNode* node6 = BuyTreeNode(6); node1->left = node2; node1->right = node4; node2->left = node3; //node2->right = NULL; //node3->left = NULL; //node3->right = NULL; node4->left = node5; node4->right = node6; //node5->left = NULL; //node5->right = NULL; //node6->left = NULL; //node6->right= NULL; return node1; } void LaterOrder(TreeNode* root) { if (root == NULL) { printf("N "); return; } LaterOrder(root->left); LaterOrder(root->right); printf("%d ", root->data); } int main() { TreeNode* root = CreatTree(); LaterOrder(root); printf("\n"); return 0; }
注意事项：
1、建议多画图自己尝试一遍
2、搞懂此时的root是谁以及root->data到底打印的是谁的值，是完成三次遍历的基础
整体代码
#include <stdio.h> #include <assert.h> #include <stdlib.h> typedef int BTDataType; typedef struct BinaryTreeNode { BTDataType data; struct BinaryTreeNode* left; struct BinaryTreeNode* right; }TreeNode; TreeNode* BuyTreeNode(int x) { TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode)); assert(node); node->data = x; node->left = NULL; node->right = NULL; return node; } TreeNode* CreatTree() { TreeNode* node1 = BuyTreeNode(1); TreeNode* node2 = BuyTreeNode(2); TreeNode* node3 = BuyTreeNode(3); TreeNode* node4 = BuyTreeNode(4); TreeNode* node5 = BuyTreeNode(5); TreeNode* node6 = BuyTreeNode(6); node1->left = node2; node1->right = node4; node2->left = node3; //node2->right = NULL; //node3->left = NULL; //node3->right = NULL; node4->left = node5; node4->right = node6; //node5->left = NULL; //node5->right = NULL; //node6->left = NULL; //node6->right= NULL; return node1; } void PrevOrder(TreeNode* root) { if(root == NULL) { printf("N "); return; } printf("%d ", root->data); PrevOrder(root->left); PrevOrder(root->right); } void InOrder(TreeNode* root) { if (root == NULL) { printf("N "); return; } InOrder(root->left); printf("%d ", root->data); InOrder(root->right); } void LaterOrder(TreeNode* root) { if (root == NULL) { printf("N "); return; } LaterOrder(root->left); LaterOrder(root->right); printf("%d ", root->data); } int main() { TreeNode* root = CreatTree(); PrevOrder(root); printf("\n"); InOrder(root); printf("\n"); LaterOrder(root); printf("\n"); return 0; }
~over~
