数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学C++编程中不使用递归打印根到叶路径。
给定二叉树，程序必须找出从根到叶的多个路径，这意味着应该打印所有路径，但挑战是不使用递归。
我们将迭代遍历树，因为约束是不使用递归。为了实现这一点，我们可以使用一个STL map，它将存储根元素，并且每当通过层序遍历识别叶节点时，它将打印从根到叶的路径，因为有一个map指针指向根节点。
在上图的树中，可以生成多条从根到叶的路径：
10 -> 3 -> 140 10 -> 3 -> 162 10 -> 211 -> 100 10 -> 211 -> 146
因此，程序必须将所有给定的路径作为给定二叉树的输出打印出来。
算法
START Step 1 -> create a structure of a node as struct Node struct node *left, *right int data End Step 2 -> function to create a node node* newnode(int data) node->data = data node->left = node->right = NULL; return (node) Step 3 -> create function to calculate the path void calculatePath(Node* curr, map<Node*, Node*> first) create STL stack<Node*> stk Loop While (curr) stk.push(curr) curr = first[curr] End Loop While !stk.empty() curr = stk.top() stk.pop() print curr->data End Step 4 -> create function to find the leaf nodes void leaf(Node* root) IF root = NULL Return End Create STL stack<Node*> stc stc.push(root) Create STL map<Node*, Node*> prnt prnt[root] = NULL Loop while !stc.empty() Node* curr = stc.top() stc.pop() IF!(curr->left) && !(curr->right) calculatePath(curr, prnt) End IF curr->right prnt[curr->right] = curr stc.push(curr->right) End IF curr->left prnt[curr->left] = curr stc.push(curr->left) End End STOP
示例
#include <bits/stdc++.h>
using namespace std;
//structure of a node
struct Node{
int data;
struct Node *left, *right;
};
//function to create a new node
Node* newNode(int data){
Node* node = new Node;
node->data = data;
node->left = node->right = NULL;
return node;
}
//this function will calculate the path
void calculatePath(Node* curr, map<Node*, Node*> first){
stack<Node*> stk;
while (curr){
stk.push(curr);
curr = first[curr];
}
while (!stk.empty()){
curr = stk.top();
stk.pop();
cout << curr->data << " ";
}
cout << endl;
}
//this function will lead to the leafs
void leaf(Node* root){
if (root == NULL)
return;
stack<Node*> stc;
stc.push(root);
map<Node*, Node*> prnt;
prnt[root] = NULL;
while (!stc.empty()){
Node* curr = stc.top();
stc.pop();
if (!(curr->left) && !(curr->right))
calculatePath(curr, prnt);
if (curr->right){
prnt[curr->right] = curr;
stc.push(curr->right);
}
if (curr->left){
prnt[curr->left] = curr;
stc.push(curr->left);
}
}
}
int main(){
Node* root = newNode(67); //it will insert the nodes to create a tree
root->left = newNode(34);
root->right = newNode(89);
root->left->left = newNode(23);
root->left->right = newNode(95);
root->right->left = newNode(12);
leaf(root); //call the function leaf
return 0;
}输出
如果我们运行上述程序，它将生成以下输出
67 34 23 67 34 95 67 89 12
更新于：2019年9月4日
170 次浏览
广告