二叉树概念: 1.空树 2.非空:根节点,根节点的左子树,根节点的右子树组成 注意!注意!时刻记得二叉树是根,根的左子树,根的右子树;根,根的左子树,根的右子树… 谓二叉树遍历(Traversal)是按照某种特定的规则,依次对二叉 树中的节点进行相应的操作,并且每个节点只操作一次。 按照规则,二叉树的遍历有:前序/中序/后序的递归结构遍历:
eg: 前序遍历)
typedef int BTDataType; typedef struct BinaryNode { BTDataType data; struct BinaryNode* left; struct BinaryNode* right; }BTNode; //前序遍历 根 左 右 void PreOder(BTNode* root) { if (root == NULL) { printf("NULL"); return; } printf("%d ", root->data); PreOder(root->left);//根的左节点作为新的根向下递归,直到为空, //此时的根作为左节点返回,继续遍历右节点 PreOder(root->right);//根的右节点作为新的根向下递归 }
方便进一步理解,可通过递归展开图进行理解。 为方便,选个数少点的。 eg:
//中序遍历 左 中 右 void InOder(BTNode* root) { //判断根节点是否为空 if (root == NULL) { printf(" NULL "); return; } //不为空,那么左节点作为根继续遍历 InOder(root->left);//递归遍历左子树,左子结点作为根, printf(" %d ", root->data); //遍历完左子树,遍历右子树 InOder(root->right); }
//二叉树的后续遍历 左 右 中 void PostOdrder(BTNode* root) { // if (root == NULL) { printf(" NULL "); return; } PostOdrder(root->left); PostOdrder(root->right);//遍历完右节点,返回打印根节点的值 printf(" %d ",root->data); }
#include <stdio.h> #include <stdlib.h> #include <assert.h> typedef int BTDataType; typedef struct BinaryNode { BTDataType data; struct BinaryNode* left; struct BinaryNode* right; }BTNode; //前序遍历 根 左 右 void PreOder(BTNode* root) { if (root == NULL) { printf(" NULL"); return; } printf(" %d ", root->data); PreOder(root->left);//根的左节点作为新的根向下递归 PreOder(root->right);//根的右节点作为新的根向下递归 } //中序遍历 左 中 右 void InOder(BTNode* root) { // if (root == NULL) { printf(" NULL "); return; } InOder(root->left);//递归遍历左子树,左子结点作为根, printf(" %d ", root->data); //遍历完左子树,遍历右子树 InOder(root->right); } //二叉树的后续遍历 左 右 中 void PostOdrder(BTNode* root) { // if (root == NULL) { printf(" NULL "); return; } PostOdrder(root->left); PostOdrder(root->right);//遍历完右节点,返回打印根节点的值 printf(" %d ",root->data); } BTNode* CreateTree() { BTNode* n1 = (BTNode*)malloc(sizeof(BTNode)); assert(n1); BTNode* n2 = (BTNode*)malloc(sizeof(BTNode)); assert(n2); BTNode* n3 = (BTNode*)malloc(sizeof(BTNode)); assert(n3); BTNode* n4 = (BTNode*)malloc(sizeof(BTNode)); assert(n4); BTNode* n5 = (BTNode*)malloc(sizeof(BTNode)); assert(n5); BTNode* n6 = (BTNode*)malloc(sizeof(BTNode)); assert(n6); BTNode* n7 = (BTNode*)malloc(sizeof(BTNode)); assert(n7); n1->data = 1; n2->data = 2; n3->data = 3; n4->data = 4; n5->data = 5; n6->data = 6; n7->data = 7; n1->left = n2; n1->right = n3; n2->left = n4; n2->right = n5; n3->left = n6; n3->right = n7; n4->left = NULL; n4->right = NULL; n5->left = NULL; n5->right = NULL; n6->left = NULL; n6->right = NULL; n3->right = n7; n7->left = NULL; n7->right = NULL; return n1; } int main() { BTNode* root = CreateTree(); PreOder(root); printf("\n"); InOder(root); printf("\n"); PostOdrder(root); printf("\n"); return 0; }