苏州制作公司网站的,推广自己的网站,山东省建设工程招标投标管理信息网官网,公关策划公司是干什么的文章目录 5.3.1 树的存储结构5. 左儿子右兄弟链接结构 5.3.2 获取结点的算法1. 获取大儿子、大兄弟结点2. 搜索给定结点的父亲3. 搜索指定数据域的结点4. 删除结点及其左右子树a. 逻辑删除与物理删除b. 算法DSTc. 算法解析d. 代码实现递归释放树算法DS e. 算法测试 5. 代码整合… 文章目录 5.3.1 树的存储结构5. 左儿子右兄弟链接结构 5.3.2 获取结点的算法1. 获取大儿子、大兄弟结点2. 搜索给定结点的父亲3. 搜索指定数据域的结点4. 删除结点及其左右子树a. 逻辑删除与物理删除b. 算法DSTc. 算法解析d. 代码实现递归释放树算法DS e. 算法测试 5. 代码整合 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. 搜索指定数据域的结点
【数据结构】树与二叉树廿五树搜索指定数据域的结点算法FindTarget
4. 删除结点及其左右子树
a. 逻辑删除与物理删除
逻辑删除Logical Deletion 逻辑删除通常是指在数据结构中标记某个节点为被删除的状态而不是真正地从内存中删除它。 物理删除Physical Deletion 物理删除是指真正地从内存中释放某个节点及其子树的内存。
b. 算法DST c. 算法解析 检查输入参数t和p是否为空如果其中任一参数为空则返回。 调用FindFather(t, p.result)函数找到以t为根的树中根为p的子树的父节点 如果找不到父节点即result为空则表示根为p的子树不存在直接删除节点p并返回。 如果找到了父节点算法继续执行检查父节点的第一个子节点是否为p 如果第一个子节点是p则将父节点的第一个子节点设置为p的下一个兄弟节点即FirstChild(result)←NextBrother( p)然后删除节点p并返回。如果第一个子节点不是p则算法使用一个循环找到p的下一个兄弟节点q将q的下一个兄弟节点设置为p的下一个兄弟节点即NextBrother(q)←NextBrother( p)。最后删除节点p并返回。
d. 代码实现
递归释放树
void freeTree(TreeNode* root) {if (root ! NULL) {freeTree(root-firstChild);freeTree(root-nextBrother);free(root);}
}算法DS
void DelSubtree(TreeNode* t, TreeNode* p) {if (t NULL || p NULL) {return;}TreeNode* result NULL;FindFather(t, p, result);if (result NULL) {return; // 未找到父亲节点}if (result-firstChild p) {result-firstChild p-nextBrother;freeTree(p);return;}TreeNode* q result-firstChild;while (q ! NULL q-nextBrother ! p) {q q-nextBrother;}if (q ! NULL) {q-nextBrother p-nextBrother;freeTree(p);}
}
e. 算法测试
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;// 要删除的子树的根节点TreeNode* subtreeRoot F;// 使用算法 DelSubtree 删除子树DelSubtree(A, subtreeRoot);// 输出删除子树后的树结构printf(Tree after deleting subtree rooted at %c:\n, subtreeRoot-data);// 层次遍历算法printf(Level Order: \n);LevelOrder(A);printf(\n);// 释放树节点freeTree(A);return 0;
}
继续采用先前系列文章的树结构删除指定结点subtreeRoot层次遍历删除subtreeRoot结点及其子树后的树释放整棵树
5. 代码整合
#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);}}
}// 算法 FindFather
void FindFather(TreeNode* t, TreeNode* p, TreeNode** result) {*result NULL;if (t NULL || p NULL || p t) {return;}TreeNode* q t-firstChild;while (q ! NULL) {if (q p) {*result t;return;}FindFather(q, p, result);if (*result ! NULL) {return;}q q-nextBrother;}
}// 算法 DelSubtree
void DelSubtree(TreeNode* t, TreeNode* p) {if (t NULL || p NULL) {return;}TreeNode* result NULL;FindFather(t, p, result);if (result NULL) {return; // 未找到父亲节点}if (result-firstChild p) {result-firstChild p-nextBrother;freeTree(p);return;}TreeNode* q result-firstChild;while (q ! NULL q-nextBrother ! p) {q q-nextBrother;}if (q ! NULL) {q-nextBrother p-nextBrother;freeTree(p);}
}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;// 要删除的子树的根节点TreeNode* subtreeRoot F;// 使用算法 DelSubtree 删除子树DelSubtree(A, subtreeRoot);// 输出删除子树后的树结构printf(Tree after deleting subtree rooted at %c:\n, subtreeRoot-data);// 层次遍历算法printf(Level Order: \n);LevelOrder(A);printf(\n);// 释放树节点freeTree(A);return 0;
}
