数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
安卓
Python
C 编程
C++
C#
MongoDB
MySQL
JavaScript
PHP
物理
化学
生物
数学
英语
经济
心理学
社会学
时尚研究
法律研究在 C++ 编程中当二叉树成为叶节点时打印这些节点。
给定一棵二叉树，我们必须打印它的叶节点，然后删除这些叶节点，然后重复操作，直到树中不再有节点为止。
示例
因此，该问题的输出应该是 −
6 7 9 13 14 3 4 2 1
方法
我们采用了一种应用 DFS 的方法。
为了应用一个临时值，将零分配给每个值，然后使用值 最大（两个子节点值之和）+1 分配所有节点。
算法
START STEP 1-> DEFINE A struct Node WITH DATA MEMBERS data, order, *left, *right STEP 2-> DEFINE A struct Node* newNode(int data, int order) WITH struct Node* node = new Node, node->data = data, node->order = order, node->left = NULL, node->right = NULL, return (node) FUNCTION void postod(struct Node* node, vector<pair<int, int> >& v) STEP 1-> IF node == NULL THEN, RETURN STEP 2-> CALL FUNCTION postod(node->left, v) STEP 3-> CALL FUNCTION postod(node->right, v) STEP 4-> IF node->right == NULL && node->left == NULL THEN, SET node->order AS 1 v.push_back(make_pair(node->order, node->data)) ELSE node->order = max((node->left)->order, (node->right)->order) + 1 v.push_back(make_pair(node->order, node->data)) END IF FUNCTION void printLeafNodes(int n, vector<pair<int, int> >& v) STEP 1-> sort(v.begin(), v.end()) STEP 2-> LOOP FOR i = 0 AND i < n AND i++ IF v[i].first == v[i + 1].first THEN, PRINT v[i].second ELSE PRINT v[i].second END IF END FOR IN main() STEP 1-> CREATE A ROOT NODE LIKE struct Node* root = newNode(8, 0) STEP 2-> DECLARE AND SET n = 9 STEP 3-> CALL postod(root, v); STEP 4-> CALL printLeafNodes(n, v);
示例
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
int order;
struct Node* left;
struct Node* right;
};
struct Node* newNode(int data, int order){
struct Node* node = new Node;
node->data = data;
node->order = order;
node->left = NULL;
node->right = NULL;
return (node);
}
void postod(struct Node* node, vector<pair<int, int> >& v){
if (node == NULL)
return;
/* first recur on left child */
postod(node->left, v);
/* now recur on right child */
postod(node->right, v);
// If current node is leaf node, it's order will be 1
if (node->right == NULL && node->left == NULL) {
node->order = 1;
// make pair of assigned value and tree value
v.push_back(make_pair(node->order, node->data));
} else {
node->order = max((node->left)->order, (node->right)->order) + 1;
v.push_back(make_pair(node->order, node->data));
}
}
void printLeafNodes(int n, vector<pair<int, int> >& v){
sort(v.begin(), v.end());
for (int i = 0; i < n; i++) {
if (v[i].first == v[i + 1].first)
cout << v[i].second << " ";
else
cout << v[i].second << "\n";
}
}
int main(){
struct Node* root = newNode(1, 0);
root->left = newNode(2, 0);
root->right = newNode(3, 0);
root->left->left = newNode(4, 0);
root->left->right = newNode(6, 0);
root->right->left = newNode(14, 0);
root->right->right = newNode(9, 0);
root->left->left->left = newNode(7, 0);
root->left->left->right = newNode(13, 0);
int n = 9;
vector<pair<int, int> > v;
postod(root, v);
printLeafNodes(n, v);
return 0;
}输出
此程序将打印输出 −
6 7 9 13 14 3 4 2 1
更新于：2019-09-04
103 浏览量
广告