当树采用孩子表示法进行存储时，（1）写出在树中找某节点的孩子节点的算法；（2）写出在树中找某节点的双亲节点的算法

当树采用孩子表示法进行存储时，可以使用以下算法来查找某节点的孩子节点和双亲节点：

1. 找孩子节点算法：

（1）首先找到该节点在数组中的下标位置；

（2）遍历该节点的孩子链表，依次查找每个孩子节点，直到找到目标节点或者遍历完整个孩子链表。

如果找到目标节点，则返回目标节点的下标位置；否则返回空。

2. 找双亲节点算法：

（1）遍历整个树，查找每个节点的孩子链表，依次遍历每个孩子节点，直到找到目标节点或者遍历完整个树。

（2）如果找到目标节点，就可以返回该节点的双亲节点，即目标节点所在的节点。

需要注意的是，在孩子表示法中，每个节点都知道自己的双亲节点，因此可以在遍历孩子链表时记录每个孩子节点的双亲节点，以便在找到目标节点时可以直接返回其双亲节点。

相关问题

5.17在以双亲链表表示法存储结构的树中，写出以下算法： （1）求树中结点双亲的算法； （2）求树中结点孩子的算法。5.14编一算法判别给定的二叉树是否是完全二叉树。

算法1：求树中结点双亲

1. 输入参数：当前节点p，根节点root
2. 如果p为根节点root，则p没有双亲，返回空
3. 从root开始进行深度优先遍历，直到找到p的父节点parent
4. 返回parent作为p的双亲节点

算法2：求树中结点孩子

1. 输入参数：当前节点p
2. 如果p没有孩子节点，返回空
3. 如果p有左孩子节点，返回左孩子节点
4. 如果p没有左孩子节点，但有右孩子节点，返回右孩子节点

算法3：判断二叉树是否为完全二叉树

1. 输入参数：二叉树的根节点root
2. 开始进行层次遍历，将每个节点依次加入队列中
3. 对于队列中的每个节点p，如果p有左孩子节点但没有右孩子节点，则不是完全二叉树；如果p有右孩子节点但没有左孩子节点，则不是完全二叉树；如果p没有左孩子节点和右孩子节点，则它后面的所有节点都必须没有孩子节点，否则不是完全二叉树
4. 如果遍历完所有节点都没有发现不符合条件的节点，则是完全二叉树

假设树采用指针方式的孩子表示法表示，试编写一个非递归函数void preorder1(tree root)，实现树的前序遍历算法。

假设树的节点表示为Node类型，包含左右子节点和数据域。则以先序遍历方式遍历一棵树的非递归函数的实现，可以参考以下代码：

void preorder1(Node* root){
stack<Node*> s;
s.push(root);
while(!s.empty()){
Node* curr = s.top();
s.pop();
if(curr){
//处理当前节点
cout << curr->data << " ";
//右子节点先入栈
s.push(curr->right);
//左子节点再入栈
s.push(curr->left);
}
}
}

在实现上，我们使用了一个栈来保存需要访问的节点。从根节点开始，每当访问一个节点时，就先打印其数据域，并将其右子节点和左子节点分别入栈，右子节点先入。这样可以保证后出栈的是左子节点。遍历完整棵树，即可实现先序遍历。

另外，需要注意的是，如果树中有空节点，则需要在遍历时做好空节点的判断和处理，以免程序崩溃。