想要實現二叉樹的遍歷可以創建一個鏈式結構的二叉樹

回顧一下二叉樹的概念，二叉樹分為空樹和非空二叉樹，非空二叉樹由根節點、根節點的左子樹和根節點的右子樹組成。

typedef char BTDataType;          // 數據類型
typedef struct BinaryTreeNode
{BTDataType data;struct BinaryTreeNode* left;  // 二叉樹的左節點struct BinaryTreeNode* right; // 二叉樹的右節點
}BTNode;

前中后序遍歷

1）前序遍歷(Preorder Traversal 亦稱先序遍歷)：訪問根結點的操作發?在遍歷其左右?樹之前

訪問順序為：根結點、左?樹、右?樹

A- > B -> D?-> NULL -> NULL -> NULL -> C -> E -> NULL -> NULL -> F -> NULL -> NULL

2）中序遍歷(Inorder Traversal)：訪問根結點的操作發?在遍歷其左右?樹之中（間）

訪問順序為：左?樹、根結點、右?樹

NULL -> D -> NULL -> B -> NULL -> A -> NULL -> E ->?NULL -> C -> NULL -> F -> NULL

3）后序遍歷(Postorder Traversal)：訪問根結點的操作發?在遍歷其左右?樹之后

訪問順序為：左?樹、右?樹、根結點

NULL -> NULL -> D -> NULL -> B -> NULL -> NULL -> E -> NULL -> NULL -> F -> C -> A

創建節點

BTNode* ByeNode(BTDataType x)
{BTNode* root = (BTNode*)malloc(sizeof(BTNode));if (root == NULL){perror("malloc fail!");exit(1);}root->data = x;root->left = root->right = NULL;return root;
}BTNode* createBinaryTree()
{BTNode* rootA = ByeNode('A');BTNode* rootB = ByeNode('B');BTNode* rootC = ByeNode('C');BTNode* rootD = ByeNode('D');BTNode* rootE = ByeNode('E');BTNode* rootF = ByeNode('F');rootA->left = rootB;rootA->right = rootC;rootB->left = rootD;rootC->left = rootE;rootC->right = rootF;return rootA;
}

代碼實現前序遍歷

// 先序遍歷二叉樹——根左右
void preOrder(BTNode* root)
{if (root == NULL){printf("NULL ");return;}printf("%c ", root->data);preOrder(root->left);preOrder(root->right);
}

畫了一個簡易的遞歸圖，原圖過長且太小了

中序遍歷代碼

// 中序遍歷二叉樹——左根右
void inOrder(BTNode* root)
{if (root == NULL){printf("NULL ");return;}inOrder(root->left);printf("%c ", root->data);inOrder(root->right);
}

后序遍歷代碼

//后序遍歷二叉樹——左右根
void postOrder(BTNode* root)
{if (root == NULL){printf("NULL ");return;}postOrder(root->left);postOrder(root->right);printf("%c ", root->data);
}