设二叉排序树以二叉链表形式存放,用类C语言设计非递归算法从大到小输出一棵根结点为T的二叉树所有不小于k的数据元素
时间: 2024-05-07 17:18:29 浏览: 122
建立二叉树链表(非递归)C语言
可以使用中序遍历的逆序来实现从大到小输出,具体算法如下:
1. 初始化栈S为空,指针p指向根结点T;
2. 当p不为空或栈S不为空时,执行以下循环:
- 若p不为空,则将p入栈,p指向左子树;
- 否则,从栈顶弹出一个结点并访问,若该结点的值不小于k,则输出该结点的值;
- 然后将p指向该结点的右子树;
3. 循环结束。
代码实现如下:
```c
typedef struct Node {
int data;
struct Node *left, *right;
} Node;
void reverseInorder(Node* T, int k) {
Node* p = T;
Stack* S = createStack();
while (p != NULL || !isEmpty(S)) {
if (p != NULL) {
push(S, p);
p = p->right;
} else {
Node* node = pop(S);
if (node->data >= k) {
printf("%d ", node->data);
}
p = node->left;
}
}
destroyStack(S);
}
```
其中,Stack是一个栈的结构体,包含以下三个函数:
```c
typedef struct Stack {
int top;
int capacity;
Node** array;
} Stack;
Stack* createStack(int capacity) {
Stack* S = (Stack*) malloc(sizeof(Stack));
S->capacity = capacity;
S->top = -1;
S->array = (Node**) malloc(S->capacity * sizeof(Node*));
return S;
}
void push(Stack* S, Node* node) {
S->array[++S->top] = node;
}
Node* pop(Stack* S) {
return S->array[S->top--];
}
int isEmpty(Stack* S) {
return S->top == -1;
}
void destroyStack(Stack* S) {
free(S->array);
free(S);
}
```
阅读全文