5.2.1 二叉樹

??二叉樹是一種常見的樹狀數(shù)據(jù)結(jié)構(gòu)，它由結(jié)點的有限集合組成。一個二叉樹要么是空集，被稱為空二叉樹，要么由一個根結(jié)點和兩棵不相交的子樹組成，分別稱為左子樹和右子樹。每個結(jié)點最多有兩個子結(jié)點，分別稱為左子結(jié)點和右子結(jié)點。

二叉樹性質(zhì)

引理5.1：二叉樹中層數(shù)為i的結(jié)點至多有$2^i$個，其中$i\ge 0$。

引理5.2：高度為k的二叉樹中至多有$2^{k+1}?1$個結(jié)點，其中$k\ge 0$。

引理5.3：設T是由n個結(jié)點構(gòu)成的二叉樹，其中葉結(jié)點個數(shù)為$n_0$，度數(shù)為2的結(jié)點個數(shù)為$n_2$，則有$n_0=n_2+1$。

• 詳細證明過程見前文：【數(shù)據(jù)結(jié)構(gòu)】樹與二叉樹（三）：二叉樹的定義、特點、性質(zhì)及相關證明

滿二叉樹、完全二叉樹定義、特點及相關證明

• 詳細證明過程見前文：【數(shù)據(jù)結(jié)構(gòu)】樹與二叉樹（四）：滿二叉樹、完全二叉樹及其性質(zhì)

5.2.2 二叉樹順序存儲

??二叉樹的順序存儲是指將二叉樹中所有結(jié)點按層次順序存放在一塊地址連續(xù)的存儲空間中，詳見：
【數(shù)據(jù)結(jié)構(gòu)】樹與二叉樹（五）：二叉樹的順序存儲（初始化，插入結(jié)點，獲取父節(jié)點、左右子節(jié)點等）

5.2.3 二叉樹鏈接存儲

??二叉樹的鏈接存儲系指二叉樹諸結(jié)點被隨機存放在內(nèi)存空間中，結(jié)點之間的關系用指針說明。在鏈式存儲中，每個二叉樹結(jié)點都包含三個域：數(shù)據(jù)域（Data）、左指針域（Left）和右指針域（Right），用于存儲結(jié)點的信息和指向子結(jié)點的指針，詳見：
【數(shù)據(jù)結(jié)構(gòu)】樹與二叉樹（六）：二叉樹的鏈式存儲

5.2.4 二叉樹的遍歷

• 遍歷（Traversal）是對二叉樹中所有節(jié)點按照一定順序進行訪問的過程。
• 通過遍歷，可以訪問樹中的每個節(jié)點，并按照特定的順序?qū)λ鼈冞M行處理。
• 對二叉樹的一次完整遍歷，可給出樹中結(jié)點的一種線性排序。
  • 在二叉樹中，常用的遍歷方式有三種：先序遍歷、中序遍歷和后序遍歷。
  • 這三種遍歷方式都可以遞歸地進行，它們的區(qū)別在于節(jié)點的訪問順序。
    • 在實現(xiàn)遍歷算法時，需要考慮遞歸終止條件和遞歸調(diào)用的順序。
  • 還可以使用迭代的方式來實現(xiàn)遍歷算法，使用?；蜿犃械葦?shù)據(jù)結(jié)構(gòu)來輔助實現(xiàn)。
• 遍歷是二叉樹中基礎而重要的操作，它為其他許多操作提供了基礎，如搜索、插入、刪除等。
  

1-3 先序、中序、后序遍歷遞歸實現(xiàn)及相關練習

【數(shù)據(jù)結(jié)構(gòu)】樹與二叉樹（七）：二叉樹的遍歷（先序、中序、后序及其C語言實現(xiàn)）

4. 中序遍歷非遞歸

【數(shù)據(jù)結(jié)構(gòu)】樹與二叉樹（八）：二叉樹的中序遍歷（非遞歸算法NIO）

5. 后序遍歷非遞歸

【數(shù)據(jù)結(jié)構(gòu)】樹與二叉樹（九）：二叉樹的后序遍歷（非遞歸算法NPO）

6. 先序遍歷非遞歸

【數(shù)據(jù)結(jié)構(gòu)】樹與二叉樹（十）：二叉樹的先序遍歷（非遞歸算法NPO）

7. 層次遍歷

【數(shù)據(jù)結(jié)構(gòu)】樹與二叉樹（十一）：二叉樹的層次遍歷（算法LevelOrder）

5.2.5 二叉樹的創(chuàng)建

• 先序遍歷
  • a b d e f g c
• 中序遍歷
  • d b f e g a c
• 后序遍歷
  • d f g e b c a
• 層次遍歷
  • a b c d e f g

先序創(chuàng)建

??由二叉樹的遍歷，很容易想到用遍歷方法去創(chuàng)建二叉樹，我們考慮從先根遍歷思想出發(fā)來構(gòu)造二叉樹。
??方法：輸入當前被創(chuàng)建結(jié)點的數(shù)據(jù)域的值，如果不空，申請空間用指針指向，然后對數(shù)據(jù)域進行賦值，再遞歸對該結(jié)點的左右指針域進行賦值，這就是先根創(chuàng)建過程。當輸入為空，則算法返回一個空指針（即空樹。遞歸出口）。
【數(shù)據(jù)結(jié)構(gòu)】樹與二叉樹（十二）：二叉樹的遞歸創(chuàng)建（算法CBT）

復制二叉樹

??考慮用后根遍歷思想遞歸復制二叉樹的算法CopyTree

a. 算法CopyTree

b. 時間復雜度

??設二叉樹有n個結(jié)點，算法CopyTree中，每個結(jié)點都要進行1次復制，即復制操作要執(zhí)行n次，每次復制都是常數(shù)級的操作，因此算法CopyTree的時間復雜度為O(n)。

c. 代碼實現(xiàn)

struct Node* CopyTree(struct Node* t) {
    if (t == NULL) {
        return NULL;
    }

    struct Node* p = createNode('\0');  // 創(chuàng)建新結(jié)點
    struct Node* newlptr = NULL;  // 初始化左指針
    struct Node* newrptr = NULL;  // 初始化右指針

    // 復制左子樹
    if (t->left != NULL) {
        newlptr = CopyTree(t->left);
    }

    // 復制右子樹
    if (t->right != NULL) {
        newrptr = CopyTree(t->right);
    }

    // 復制數(shù)據(jù)和指針
    p->data = t->data;
    p->left = newlptr;
    p->right = newrptr;

    return p;
}

代碼整合

#include <stdio.h>
#include <stdlib.h>

// 二叉樹結(jié)點的定義
struct Node {
    char data;
    struct Node* left;
    struct Node* right;
};

// 創(chuàng)建新結(jié)點
struct Node* createNode(char data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    if (newNode == NULL) {
        printf("Memory allocation failed!\n");
        exit(1);
    }
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

// 復制二叉樹
struct Node* CopyTree(struct Node* t) {
    if (t == NULL) {
        return NULL;
    }

    struct Node* p = createNode('\0');  // 創(chuàng)建新結(jié)點
    struct Node* newlptr = NULL;  // 初始化左指針
    struct Node* newrptr = NULL;  // 初始化右指針

    // 復制左子樹
    if (t->left != NULL) {
        newlptr = CopyTree(t->left);
    }

    // 復制右子樹
    if (t->right != NULL) {
        newrptr = CopyTree(t->right);
    }

    // 復制數(shù)據(jù)和指針
    p->data = t->data;
    p->left = newlptr;
    p->right = newrptr;

    return p;
}

// 中序遍歷二叉樹
void inorderTraversal(struct Node* root) {
    if (root != NULL) {
        inorderTraversal(root->left);
        printf("%c ", root->data);
        inorderTraversal(root->right);
    }
}
struct Node* CBT(char data[], int* index, char tostop) {
    char ch = data[(*index)++];
    if (ch == tostop) {
        return NULL;
    } else {
        struct Node* t = createNode(ch);
        t->left = CBT(data, index, tostop);
        t->right = CBT(data, index, tostop);
        return t;
    }
}

int main() {
    // 創(chuàng)建一棵二叉樹
    char tostop = '#';
    char input_data[] = {'a', 'b', 'd', '#', '#', 'e', 'f', '#', '#', 'g', '#', '#', 'c', '#', '#'};
    int index = 0;

    struct Node* original = CBT(input_data, &index, tostop);

    // 復制二叉樹
    struct Node* copy = CopyTree(original);

    // 中序遍歷并輸出原始二叉樹
    printf("Original Inorder Traversal: ");
    inorderTraversal(original);
    printf("\n");

    // 中序遍歷并輸出復制后的二叉樹
    printf("  Copied Inorder Traversal: ");
    inorderTraversal(copy);
    printf("\n");

    return 0;
}

文章來源地址http://www.zghlxwxcb.cn/news/detail-791401.html

到了這里，關于【數(shù)據(jù)結(jié)構(gòu)】樹與二叉樹（十三）：遞歸復制二叉樹（算法CopyTree）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！