5.3.1 樹的存儲(chǔ)結(jié)構(gòu)

5. 左兒子右兄弟鏈接結(jié)構(gòu)

【數(shù)據(jù)結(jié)構(gòu)】樹與二叉樹（十九）：樹的存儲(chǔ)結(jié)構(gòu)——左兒子右兄弟鏈接結(jié)構(gòu)（樹、森林與二叉樹的轉(zhuǎn)化）
??左兒子右兄弟鏈接結(jié)構(gòu)通過使用每個(gè)節(jié)點(diǎn)的三個(gè)域（FirstChild、Data、NextBrother）來構(gòu)建一棵樹，同時(shí)使得樹具有二叉樹的性質(zhì)。具體來說，每個(gè)節(jié)點(diǎn)包含以下信息：

1. FirstChild： 存放指向該節(jié)點(diǎn)的大兒子（最左邊的子節(jié)點(diǎn)）的指針。這個(gè)指針使得我們可以迅速找到一個(gè)節(jié)點(diǎn)的第一個(gè)子節(jié)點(diǎn)。
2. Data： 存放節(jié)點(diǎn)的數(shù)據(jù)。
3. NextBrother： 存放指向該節(jié)點(diǎn)的大兄弟（同一層中右邊的兄弟節(jié)點(diǎn)）的指針。這個(gè)指針使得我們可以在同一層中迅速找到節(jié)點(diǎn)的下一個(gè)兄弟節(jié)點(diǎn)。

??通過這樣的結(jié)構(gòu)，整棵樹可以用左兒子右兄弟鏈接結(jié)構(gòu)表示成一棵二叉樹。這種表示方式有時(shí)候被用于一些特殊的樹結(jié)構(gòu)，例如二叉樹、二叉樹的森林等。這種結(jié)構(gòu)的優(yōu)點(diǎn)之一是它更緊湊地表示樹，而不需要額外的指針來表示兄弟關(guān)系。

   A/|\B C D/ \E   F

A
|
B -- C -- D|E -- F

即：

      A/ B   \C/ \ E   D\F

5.3.2 獲取結(jié)點(diǎn)的算法

1. 獲取大兒子、大兄弟結(jié)點(diǎn)

【數(shù)據(jù)結(jié)構(gòu)】樹與二叉樹（二十）：樹獲取大兒子、大兄弟結(jié)點(diǎn)的算法（GFC、GNB）

2. 搜索給定結(jié)點(diǎn)的父親

【數(shù)據(jù)結(jié)構(gòu)】樹與二叉樹（廿四）：樹搜索給定結(jié)點(diǎn)的父親（算法FindFather）

3. 搜索指定數(shù)據(jù)域的結(jié)點(diǎn)

a. 算法FindTarget

b. 算法解析

??算法FindTarget在以t為根指針的樹中搜索數(shù)據(jù)成員等于target的節(jié)點(diǎn)，類似先根遍歷，其時(shí)間復(fù)雜度為O(n) 。

1. 首先，將result指針設(shè)置為空。
2. 如果t為空，直接返回。
3. 如果t的數(shù)據(jù)成員等于target，表示找到了目標(biāo)節(jié)點(diǎn)，將result指針指向t，然后返回。
4. 將指針p指向t的第一個(gè)子節(jié)點(diǎn)。
5. 進(jìn)入一個(gè)循環(huán)，只要p不為空：
   • 遞歸調(diào)用FindTarget函數(shù)，傳入?yún)?shù)p和target，并將結(jié)果存儲(chǔ)在result中。
   • 如果result不為空，表示已經(jīng)找到了目標(biāo)節(jié)點(diǎn)，直接返回。
   • 將指針p更新為p的下一個(gè)兄弟節(jié)點(diǎn)。
6. 如果循環(huán)結(jié)束仍然沒有找到目標(biāo)節(jié)點(diǎn)，那么result仍然為空。

c. 代碼實(shí)現(xiàn)

a. 使用指向指針的指針

TreeNode* FindTarget(TreeNode* t, char target) {if (t == NULL) {return NULL;}if (t->data == target) {return t;}TreeNode* p = t->firstChild;while (p != NULL) {struct TreeNode* resultt = FindTarget(p, target);if (resultt != NULL) {return resultt;}p = p->nextBrother;}
}

b. 直接返回找到的節(jié)點(diǎn)

void FindTarget(TreeNode* t, char target, TreeNode** result) {*result = NULL;if (t == NULL) {return;}if (t->data == target) {*result = t;return;}TreeNode* p = t->firstChild;while (p != NULL) {FindTarget(p, target, result);if (*result != NULL) {return;}p = p->nextBrother;}
}

??兩種實(shí)現(xiàn)方式在邏輯上是等價(jià)的，主要的區(qū)別在于結(jié)果的返回方式和對(duì)指針的處理。

4. 代碼整合

#include <stdio.h>
#include <stdlib.h>// 定義樹節(jié)點(diǎn)
typedef struct TreeNode {char data;struct TreeNode* firstChild;struct TreeNode* nextBrother;
} TreeNode;// 創(chuàng)建樹節(jié)點(diǎn)
TreeNode* createNode(char data) {TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));if (newNode != NULL) {newNode->data = data;newNode->firstChild = NULL;newNode->nextBrother = NULL;}return newNode;
}// 釋放樹節(jié)點(diǎn)及其子樹
void freeTree(TreeNode* root) {if (root != NULL) {freeTree(root->firstChild);freeTree(root->nextBrother);free(root);}
}// 算法GFC：獲取大兒子結(jié)點(diǎn)
TreeNode* getFirstChild(TreeNode* p) {if (p != NULL && p->firstChild != NULL) {return p->firstChild;}return NULL;
}// 算法GNB：獲取下一個(gè)兄弟結(jié)點(diǎn)
TreeNode* getNextBrother(TreeNode* p) {if (p != NULL && p->nextBrother != NULL) {return p->nextBrother;}return NULL;
}// 隊(duì)列結(jié)構(gòu)
typedef struct QueueNode {TreeNode* treeNode;struct QueueNode* next;
} QueueNode;typedef struct {QueueNode* front;QueueNode* rear;
} Queue;// 初始化隊(duì)列
void initQueue(Queue* q) {q->front = NULL;q->rear = NULL;
}// 入隊(duì)列
void enqueue(Queue* q, TreeNode* treeNode) {QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode));newNode->treeNode = treeNode;newNode->next = NULL;if (q->rear == NULL) {q->front = newNode;q->rear = newNode;} else {q->rear->next = newNode;q->rear = newNode;}
}// 出隊(duì)列
TreeNode* dequeue(Queue* q) {if (q->front == NULL) {return NULL; // 隊(duì)列為空}TreeNode* treeNode = q->front->treeNode;QueueNode* temp = q->front;q->front = q->front->next;free(temp);if (q->front == NULL) {q->rear = NULL; // 隊(duì)列為空}return treeNode;
}// 層次遍歷的算法
void LevelOrder(TreeNode* root) {if (root == NULL) {return;}Queue queue;initQueue(&queue);enqueue(&queue, root);while (queue.front != NULL) {TreeNode* p = dequeue(&queue);while (p != NULL) {// 訪問當(dāng)前結(jié)點(diǎn)printf("%c ", p->data);// 將大兒子結(jié)點(diǎn)入隊(duì)列if (getFirstChild(p) != NULL) {enqueue(&queue, getFirstChild(p));}// 移動(dòng)到下一個(gè)兄弟結(jié)點(diǎn)p = getNextBrother(p);}}
}// 算法 FindTarget
void FindTarget(TreeNode* t, char target, TreeNode** result) {*result = NULL;if (t == NULL) {return;}if (t->data == target) {*result = t;return;}TreeNode* p = t->firstChild;while (p != NULL) {FindTarget(p, target, result);if (*result != NULL) {return;}p = p->nextBrother;}
}// TreeNode* FindTarget(TreeNode* t, char target) {
//     if (t == NULL) {
//         return NULL;
//     }
//
//     if (t->data == target) {
//         return t;
//     }
//
//     TreeNode* p = t->firstChild;
//
//     while (p != NULL) {
//         struct TreeNode* resultt = FindTarget(p, target);
//
//         if (resultt != NULL) {
//             return resultt;
//         }
//
//         p = p->nextBrother;
//     }
// }int main() {// 構(gòu)建左兒子右兄弟鏈接結(jié)構(gòu)的樹TreeNode* A = createNode('A');TreeNode* B = createNode('B');TreeNode* C = createNode('C');TreeNode* D = createNode('D');TreeNode* E = createNode('E');TreeNode* F = createNode('F');A->firstChild = B;B->nextBrother = C;C->nextBrother = D;C->firstChild = E;E->nextBrother = F;// 要查找的目標(biāo)值char targetValue = 'C';// 使用算法 FindTarget 查找結(jié)點(diǎn)// TreeNode* result = FindTarget(A, targetValue);TreeNode* result = NULL;FindTarget(A, targetValue, &result);// 輸出結(jié)果if (result != NULL) {printf("Node with data %c found.\n", targetValue);} else {printf("Node with data %c not found.\n", targetValue);}// 層次遍歷printf("Level Order: \n");LevelOrder(result);printf("\n");// 釋放樹節(jié)點(diǎn)freeTree(A);return 0;
}