資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學使用 C++ 列印給定二叉樹節點的祖先節點（非遞迴）
在這個問題中，我們給定一棵二叉樹，需要打印出二叉樹中某個節點的祖先節點。
二叉樹是一種特殊的樹，其每個節點最多有兩個子節點。因此，每個節點要麼是葉子節點，要麼有一個或兩個子節點。
例如：
**祖先節點**是指在二叉樹中位於給定節點上層的一個節點。
讓我們來看一個祖先節點的例子：
在這棵二叉樹中，值為 3 的節點的祖先節點是 **8**，
為了解決這個問題，我們將從根節點遍歷到目標節點，逐步向下遍歷二叉樹。並在路徑中列印所有遇到的節點。
這理想情況下會涉及到對路徑中從根節點到目標節點的每個節點都進行相同方法的遞迴呼叫。
因此，非遞迴方法需要使用迭代遍歷和一個棧，該棧將儲存樹中目標節點的祖先節點。我們將進行二叉樹的後序遍歷。並將祖先節點儲存到棧中，最後列印棧的內容，這些內容就是該節點的祖先節點。
示例
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100
struct Node{
int data;
struct Node *left, *right;
};
struct Stack{
int size;
int top;
struct Node* *array;
};
struct Node* insertNode(int data){
struct Node* node = (struct Node*) malloc(sizeof(struct Node));
node->data = data;
node->left = node->right = NULL;
return node;
}
struct Stack* createStack(int size){
struct Stack* stack = (struct Stack*) malloc(sizeof(struct Stack));
stack->size = size;
stack->top = -1;
stack->array = (struct Node**) malloc(stack->size * sizeof(struct Node*));
return stack;
}
int isFull(struct Stack* stack){
return ((stack->top + 1) == stack->size);
}
int isEmpty(struct Stack* stack){
return stack->top == -1;
}
void push(struct Stack* stack, struct Node* node){
if (isFull(stack))
return;
stack->array[++stack->top] = node;
}
struct Node* pop(struct Stack* stack){
if (isEmpty(stack))
return NULL;
return stack->array[stack->top--];
}
struct Node* peek(struct Stack* stack){
if (isEmpty(stack))
return NULL;
return stack->array[stack->top];
}
void AncestorNodes(struct Node *root, int key){
if (root == NULL) return;
struct Stack* stack = createStack(MAX_SIZE);
while (1){
while (root && root->data != key){
push(stack, root);
root = root->left;
}
if (root && root->data == key)
break;
if (peek(stack)->right == NULL){
root = pop(stack);
while (!isEmpty(stack) && peek(stack)->right == root)
root = pop(stack);
}
root = isEmpty(stack)? NULL: peek(stack)->right;
}
while (!isEmpty(stack))
printf("%d ", pop(stack)->data);
}
int main(){
struct Node* root = insertNode(15);
root->left = insertNode(10);
root->right = insertNode(25);
root->left->left = insertNode(5);
root->left->right = insertNode(12);
root->right->left = insertNode(20);
root->right->right = insertNode(27);
root->left->left->left = insertNode(1);
root->left->right->right = insertNode(14);
root->right->right->left = insertNode(17);
printf("The ancestors of the given node are : ");
AncestorNodes(root, 17);
getchar();
return 0;
}輸出
The ancestors of the given node are : 27 25 15
更新於：2020年1月3日
135 次檢視
廣告