二叉樹遍歷

在數(shù)據(jù)結(jié)構(gòu)中，二叉樹是一種常用且重要的數(shù)據(jù)結(jié)構(gòu)。二叉樹的遍歷是指按照一定順序訪問二叉樹的所有節(jié)點，常見的遍歷方式有前序遍歷、中序遍歷和后序遍歷。本文將詳細介紹這三種遍歷算法，并介紹最優(yōu)二叉樹。

二叉樹的基本定義

首先，我們先來了解一下二叉樹的基本定義。二叉樹是每個節(jié)點最多有兩個子節(jié)點的樹結(jié)構(gòu)。每個節(jié)點都可以有左子節(jié)點和右子節(jié)點，也可以沒有子節(jié)點。二叉樹可以為空，即沒有任何節(jié)點。

1、前序遍歷

前序遍歷是先訪問根節(jié)點，然后按照左子樹、右子樹的順序遞歸遍歷。前序遍歷的訪問順序為“根左右”。

代碼

void preOrderTraversal(TreeNode* root) {
    if (root == NULL) return;
    printf("%c ", root->data);
    preOrderTraversal(root->left);
    preOrderTraversal(root->right);
}

2、中序遍歷

中序遍歷是先按照左子樹的順序遞歸遍歷，然后訪問根節(jié)點，最后按照右子樹的順序遞歸遍歷。中序遍歷的訪問順序為“左根右”。

代碼

void inOrderTraversal(TreeNode* root) {
    if (root == NULL) return;
    inOrderTraversal(root->left);
    printf("%c ", root->data);
    inOrderTraversal(root->right);
}

3、后序遍歷

后序遍歷是先按照左子樹、右子樹的順序遞歸遍歷，然后訪問根節(jié)點。后序遍歷的訪問順序為“左右根”。

代碼

void postOrderTraversal(TreeNode* root) {
    if (root == NULL) return;
    postOrderTraversal(root->left);
    postOrderTraversal(root->right);
    printf("%c ", root->data);
}

全部代碼（這里是遞歸的方式，也可以是用隊列或者是棧來實現(xiàn)，但是有點麻煩）

①tree.h

#ifndef _TREE_H_
#define _TREE_H_
#include <stdio.h>
#include <stdlib.h>

typedef struct TreeNode {
    char data;
    struct TreeNode* left;
    struct TreeNode* right;
} TreeNode;

//創(chuàng)建樹
TreeNode* createTree();

//先序
void preOrderTraversal(TreeNode* root);

//中序
void inOrderTraversal(TreeNode* root);

//后序
void postOrderTraversal(TreeNode* root);

#endif

②tree.c

#include "tree.h"
//創(chuàng)建樹
TreeNode* createTree() {
    char ch;
    scanf("%c", &ch);
    if (ch == '#') {
        return NULL;
    }

    TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));
    newNode->data = ch;
    newNode->left = createTree();
    newNode->right = createTree();

    return newNode;
}

//先序
void preOrderTraversal(TreeNode* root) {
    if (root == NULL) return;
    printf("%c ", root->data);
    preOrderTraversal(root->left);
    preOrderTraversal(root->right);
}

//中序
void inOrderTraversal(TreeNode* root) {
    if (root == NULL) return;
    inOrderTraversal(root->left);
    printf("%c ", root->data);
    inOrderTraversal(root->right);
}

//后序
void postOrderTraversal(TreeNode* root) {
    if (root == NULL) return;
    postOrderTraversal(root->left);
    postOrderTraversal(root->right);
    printf("%c ", root->data);
}

③tree_main.c

#include "tree.h"
#include "tree.c"
int main() {
    printf("輸入先序序列（包含null節(jié)點，使用#表示）：\n");
    TreeNode* root = createTree();

    printf("構(gòu)造的二叉樹先序遍歷結(jié)果為：\n");
    preOrderTraversal(root);

    printf("\n構(gòu)造的二叉樹中序遍歷結(jié)果為：\n");
    inOrderTraversal(root);

    printf("\n構(gòu)造的二叉樹后序遍歷結(jié)果為：\n");
    postOrderTraversal(root);

    return 0;
}

運行結(jié)果

和上面我們畫圖連線是一樣的結(jié)果。

1、由先序和中序求后序

先序：A B C E F G H D I J K L M
中序：E C B G F H A J I K D M L
求后序？

2、由后序和中序求先序

中序：E C B G F H A J I K D M L
后序：E C G H F B J K I M L D A
求先序？
文章來源地址http://www.zghlxwxcb.cn/news/detail-609713.html

到了這里，關(guān)于十三、數(shù)據(jù)結(jié)構(gòu)——二叉樹的遍歷（先序、中序和后序）詳細思路和代碼的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！