資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究使用C++中一個棧從左到右列印二叉樹的葉子節點
程式應該從左到右列印二叉樹的葉子節點，但挑戰在於只能使用一個棧。
透過push()函式插入二叉樹的節點，並透過pop()操作顯示葉子節點。
葉子節點是左右指標都為NULL的末端節點，這意味著該節點不是父節點。
示例
Input : 12 21 32 41 59 33 70 Output : 41 59 33 70
棧是一種後進先出(LIFO)的資料結構，其中頂部指標指向最後插入的元素，因此葉子節點將最後插入棧中，並且根據棧的結構，它們將在任何其他節點之前從棧中彈出或移除。
下面的程式碼顯示了使用STL的C++演算法實現。
演算法
START Step 1 -> create node variable of type structure Declare int data Declare pointer of type node using *left, *right Step 2 -> create function for inserting node with parameter as val Declare node variable of node using malloc Set node->data = val Set node->left = node->right = NULL return node step 3 -> Declare Function void leaf(Node *ptr) create vector stack<Node*>stck Loop While 1 IF ptr Stck.push(ptr) Ptr = ptr->left Else IF (stck.empty()) Break Else IF (stck.top()->right == NULL) Set ptr = stck.top() Set stck.pop() IF ptr->left = NULL Print ptr->data End Loop While ptr == stck.top()->right Set ptr = stck.top() Call stck.pop() IF stck.empty() Break End IF !stck.empty() Set ptr = tck.top()->right Else Set ptr = NULL EndIF End End End Step 4-> In main() Call New passing value user want to insert as Node* root = New(12) Call leaf(root) STOP
示例
#include <bits/stdc++.h>
using namespace std;
// Structure of a node
struct Node {
Node* left;
Node* right;
int data;
};
//Function to create a new node
Node* New(int val) {
Node* node = new Node();
node->left = node->right = NULL;
node->data = val;
return node;
}
// leaf node using stack
void leaf(Node* ptr) {
// stack that will store nodes
stack<Node*> stck;
while (1) {
if (ptr) {
stck.push(ptr);
ptr = ptr->left;
} else {
if (stck.empty())
break;
else {
if (stck.top()->right == NULL) {
ptr = stck.top();
stck.pop();
// Print the leaf node
if (ptr->left == NULL)
printf("%d ", ptr->data);
}
while (ptr == stck.top()->right) {
ptr = stck.top();
stck.pop();
if (stck.empty())
break;
}
if (!stck.empty())
ptr = stck.top()->right;
else
ptr = NULL;
}
}
}
}
int main() {
printf("leaf nodes at end level are : ");
Node* root = New(12);
root->left = New(21);
root->right = New(32);
root->left->left = New(41);
root->left->right = New(59);
root->right->left = New(33);
root->right->right = New(70);
leaf(root);
return 0;
}輸出
如果執行上述程式，它將生成以下輸出。
leaf nodes at end level are : 41 59 33 70
更新於：2019年8月22日
175 次瀏覽
廣告