南昌商城网站建设公司,广告设计公司实习周记,深圳做棋牌网站建设多少钱,从山海经取公司名文章目录 5.3.1 树的存储结构5. 左儿子右兄弟链接结构 5.3.2 获取结点的算法1. 获取大儿子、大兄弟结点2. 搜索给定结点的父亲3. 搜索指定数据域的结点a. 算法FindTargetb. 算法解析c. 代码实现a. 使用指向指针的指针b. 直接返回找到的节点 4. 代码整合 5.3.1 树的存储结构
5.… 文章目录 5.3.1 树的存储结构5. 左儿子右兄弟链接结构 5.3.2 获取结点的算法1. 获取大儿子、大兄弟结点2. 搜索给定结点的父亲3. 搜索指定数据域的结点a. 算法FindTargetb. 算法解析c. 代码实现a. 使用指向指针的指针b. 直接返回找到的节点 4. 代码整合 5.3.1 树的存储结构
5. 左儿子右兄弟链接结构
【数据结构】树与二叉树十九树的存储结构——左儿子右兄弟链接结构树、森林与二叉树的转化 左儿子右兄弟链接结构通过使用每个节点的三个域FirstChild、Data、NextBrother来构建一棵树同时使得树具有二叉树的性质。具体来说每个节点包含以下信息
FirstChild 存放指向该节点的大儿子最左边的子节点的指针。这个指针使得我们可以迅速找到一个节点的第一个子节点。Data 存放节点的数据。NextBrother 存放指向该节点的大兄弟同一层中右边的兄弟节点的指针。这个指针使得我们可以在同一层中迅速找到节点的下一个兄弟节点。 通过这样的结构整棵树可以用左儿子右兄弟链接结构表示成一棵二叉树。这种表示方式有时候被用于一些特殊的树结构例如二叉树、二叉树的森林等。这种结构的优点之一是它更紧凑地表示树而不需要额外的指针来表示兄弟关系。 A/|\B C D/ \E FA
|
B -- C -- D|E -- F即 A/ B \C/ \ E D\F 5.3.2 获取结点的算法
1. 获取大儿子、大兄弟结点
【数据结构】树与二叉树二十树获取大儿子、大兄弟结点的算法GFC、GNB
2. 搜索给定结点的父亲
【数据结构】树与二叉树廿四树搜索给定结点的父亲算法FindFather
3. 搜索指定数据域的结点
a. 算法FindTarget b. 算法解析 算法FindTarget在以t为根指针的树中搜索数据成员等于target的节点类似先根遍历其时间复杂度为O(n) 。
首先将result指针设置为空。如果t为空直接返回。如果t的数据成员等于target表示找到了目标节点将result指针指向t然后返回。将指针p指向t的第一个子节点。进入一个循环只要p不为空 递归调用FindTarget函数传入参数p和target并将结果存储在result中。如果result不为空表示已经找到了目标节点直接返回。将指针p更新为p的下一个兄弟节点。 如果循环结束仍然没有找到目标节点那么result仍然为空。
c. 代码实现
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. 直接返回找到的节点
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;}
}两种实现方式在逻辑上是等价的主要的区别在于结果的返回方式和对指针的处理。
4. 代码整合
#include stdio.h
#include stdlib.h// 定义树节点
typedef struct TreeNode {char data;struct TreeNode* firstChild;struct TreeNode* nextBrother;
} TreeNode;// 创建树节点
TreeNode* createNode(char data) {TreeNode* newNode (TreeNode*)malloc(sizeof(TreeNode));if (newNode ! NULL) {newNode-data data;newNode-firstChild NULL;newNode-nextBrother NULL;}return newNode;
}// 释放树节点及其子树
void freeTree(TreeNode* root) {if (root ! NULL) {freeTree(root-firstChild);freeTree(root-nextBrother);free(root);}
}// 算法GFC获取大儿子结点
TreeNode* getFirstChild(TreeNode* p) {if (p ! NULL p-firstChild ! NULL) {return p-firstChild;}return NULL;
}// 算法GNB获取下一个兄弟结点
TreeNode* getNextBrother(TreeNode* p) {if (p ! NULL p-nextBrother ! NULL) {return p-nextBrother;}return NULL;
}// 队列结构
typedef struct QueueNode {TreeNode* treeNode;struct QueueNode* next;
} QueueNode;typedef struct {QueueNode* front;QueueNode* rear;
} Queue;// 初始化队列
void initQueue(Queue* q) {q-front NULL;q-rear NULL;
}// 入队列
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;}
}// 出队列
TreeNode* dequeue(Queue* q) {if (q-front NULL) {return NULL; // 队列为空}TreeNode* treeNode q-front-treeNode;QueueNode* temp q-front;q-front q-front-next;free(temp);if (q-front NULL) {q-rear NULL; // 队列为空}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) {// 访问当前结点printf(%c , p-data);// 将大儿子结点入队列if (getFirstChild(p) ! NULL) {enqueue(queue, getFirstChild(p));}// 移动到下一个兄弟结点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() {// 构建左儿子右兄弟链接结构的树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;// 要查找的目标值char targetValue C;// 使用算法 FindTarget 查找结点// TreeNode* result FindTarget(A, targetValue);TreeNode* result NULL;FindTarget(A, targetValue, result);// 输出结果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);// 释放树节点freeTree(A);return 0;
}
