数据结构
网络
关系数据库管理系统 (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 次浏览
广告