树的孩子兄弟法的树状打印
时间: 2023-05-29 07:01:18 浏览: 97
树的孩子兄弟法是一种非常常用的树的存储方法,它将每个节点的孩子和兄弟节点都用指针表示,在内存中以链表的形式存储。树的孩子兄弟法可以用一种类似于广度优先搜索的方式来遍历整个树,具有很好的效率和灵活性。
在树的孩子兄弟法中,每个节点都有一个指向第一个孩子节点的指针(child),以及一个指向下一个兄弟节点的指针(sibling),所以整个树可以用一个链表来表示。下面是一颗简单的二叉树的示例:
```
A
/ \
B C
/ \ / \
D E F G
```
用树的孩子兄弟法存储如下:
```
struct Node {
char data; // 节点数据
Node* child; // 指向第一个孩子节点的指针
Node* sibling; // 指向下一个兄弟节点的指针
};
```
对于上面的二叉树,用树的孩子兄弟法存储就是下面的样子:
```
A -> child: B sibling: NULL
| |
B C -> child: F sibling: NULL
/ \ / \
D E F G -> child: NULL sibling: NULL
```
树的遍历可以用递归来实现,下面是先序遍历的代码实现:
```
void preOrder(Node* root) { // 先序遍历
if (root == NULL) {
return;
}
cout << root->data << " ";
preOrder(root->child);
preOrder(root->sibling);
}
```
树状打印可以用递归来实现,下面是一个简单的实现:
```
void printTree(Node* root, int depth) {
if (root == NULL) {
return;
}
for (int i = 0; i < depth; i++) { // 按深度打印空格
cout << " ";
}
cout << root->data << endl; // 打印节点数据
printTree(root->child, depth + 1); // 打印孩子节点
printTree(root->sibling, depth); // 打印兄弟节点
}
```
使用函数打印上面的示例二叉树,输出如下:
```
A
B
D
E
C
F
G
```