資料結構
網路
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 瀏覽量
廣告