以孩子兄弟表示法做存储结构,求树中结点x的 第i个孩子
时间: 2024-05-11 07:18:18 浏览: 112
凹入表示法打印二叉树结构.docx
5星 · 资源好评率100%
对于以孩子兄弟表示法存储的树,每个结点都有两个指针,一个指向第一个孩子,一个指向下一个兄弟。因此,我们可以按照以下步骤求出结点x的第i个孩子:
1. 找到结点x的第一个孩子p。
2. 依次遍历p的下一个兄弟q,直到找到第i个孩子或者已经遍历完所有孩子。
3. 如果找到了第i个孩子,返回该孩子的指针;否则,返回空指针。
具体实现可以参考以下代码:
```c++
// 以孩子兄弟表示法存储的树结点定义
struct TreeNode {
char data; // 结点数据
TreeNode *firstChild; // 指向第一个孩子的指针
TreeNode *nextSibling; // 指向下一个兄弟的指针
};
// 求结点x的第i个孩子
TreeNode* getChild(TreeNode *x, int i) {
if (x == nullptr || i < 1) {
return nullptr;
}
TreeNode *p = x->firstChild;
int j = 1;
while (p != nullptr && j < i) {
p = p->nextSibling;
j++;
}
return p;
}
```
需要注意的是,如果i超过了结点x的孩子个数,返回的是空指针。
阅读全文