用顺序存储结构来存储一颗具有n个结点的二叉树,编写算法实现对该二叉树进行先序遍历,输出先序遍历序列。,c语言伪代码
时间: 2024-05-14 10:17:55 浏览: 9
假设二叉树的结点数据类型为NodeType,其先序遍历序列为:根节点 -> 左子树 -> 右子树。
伪代码如下:
```
// 定义栈的结构体
typedef struct Stack {
NodeType data[MAX_SIZE];
int top;
} Stack;
// 初始化栈
void initStack(Stack* s) {
s->top = -1;
}
// 判断栈是否为空
int isStackEmpty(Stack* s) {
return s->top == -1;
}
// 入栈
void push(Stack* s, NodeType value) {
if (s->top == MAX_SIZE - 1) {
return; // 栈满
}
s->data[++s->top] = value;
}
// 出栈
NodeType pop(Stack* s) {
if (isStackEmpty(s)) {
return NULL; // 栈空
}
return s->data[s->top--];
}
// 获取栈顶元素
NodeType getTop(Stack* s) {
if (isStackEmpty(s)) {
return NULL; // 栈空
}
return s->data[s->top];
}
// 先序遍历二叉树
void preOrderTraversal(BinaryTree* tree) {
if (tree == NULL) {
return;
}
Stack s;
initStack(&s);
NodeType node = tree;
while (node != NULL || !isStackEmpty(&s)) { // 当二叉树还有结点未遍历或栈非空时
while (node != NULL) { // 遍历左子树
printf("%d ", node->data); // 输出结点值
push(&s, node); // 将结点入栈
node = node->left;
}
if (!isStackEmpty(&s)) { // 遍历右子树
node = pop(&s); // 出栈
node = node->right;
}
}
}
```
其中,`BinaryTree` 为二叉树的结构体,包含 `data` 表示结点的值,`left` 和 `right` 分别表示左右子树的指针。`MAX_SIZE` 为栈的最大容量。