資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學用C++列印二叉樹的所有葉子節點（從右到左）
在這個問題中，我們給定一棵二叉樹，需要從右到左列印所有葉子節點。
讓我們來看一個例子來理解這個問題
輸入 -
輸出 - 7 4 1
為了解決這個問題，我們需要遍歷二叉樹。這種遍歷可以透過兩種方式完成：
先序遍歷 - 這種遍歷使用遞迴。在這裡，我們將遍歷根節點，然後是左子樹，最後是右子樹。如果遇到葉子節點，則列印它，否則檢查節點的子節點並探索它們以查詢葉子節點。
示例
展示我們解決方案實現的程式：
#include <iostream>
using namespace std;
struct Node {
int data;
struct Node *left, *right;
};
Node* insertNode(int data) {
Node* temp = new Node;
temp->data = data;
temp->left = temp->right = NULL;
return temp;
}
void findLeafNode(Node* root) {
if (!root)
return;
if (!root->left && !root->right) {
cout<<root->data<<"\t";
return;
}
if (root->right)
findLeafNode(root->right);
if (root->left)
findLeafNode(root->left);
}
int main() {
Node* root = insertNode(21);
root->left = insertNode(5);
root->right = insertNode(11);
root->left->left = insertNode(8);
root->left->right = insertNode(98);
root->right->left = insertNode(2);
root->right->right = insertNode(8);
cout<<"Leaf nodes of the tree from right to left are:\n";
findLeafNode(root);
return 0;
}輸出
Leaf nodes of the tree from right to left are − 18 2 98 8
後序遍歷 - 這種查詢葉子節點的遍歷將使用迭代。我們將使用一個棧來儲存資料，並以後序方式遍歷樹（先右子樹，然後左子樹，最後根節點），並列印葉子節點。
示例
展示我們解決方案實現的程式：
#include<bits/stdc++.h>
using namespace std;
struct Node {
Node* left;
Node* right;
int data;
};
Node* insertNode(int key) {
Node* node = new Node();
node->left = node->right = NULL;
node->data = key;
return node;
}
void findLeafNode(Node* tree) {
stack<Node*> treeStack;
while (1) {
if (tree) {
treeStack.push(tree);
tree = tree->right;
} else {
if (treeStack.empty())
break;
else {
if (treeStack.top()->left == NULL) {
tree = treeStack.top();
treeStack.pop();
if (tree->right == NULL)
cout<<tree->data<<"\t";
}
while (tree == treeStack.top()->left) {
tree = treeStack.top();
treeStack.pop();
if (treeStack.empty())
break;
}
if (!treeStack.empty())
tree = treeStack.top()->left;
else
tree = NULL;
}
}
}
}
int main(){
Node* root = insertNode(21);
root->left = insertNode(5);
root->right = insertNode(11);
root->left->left = insertNode(8);
root->left->right = insertNode(98);
root->right->left = insertNode(2);
root->right->right = insertNode(18);
cout<<"Leaf nodes of the tree from right to left are:\n";
findLeafNode(root);
return 0;
}輸出
Leaf nodes of the tree from right to left are − 18 2 98 8
更新於：2020年1月22日
537 次瀏覽
廣告