資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究二叉樹的邊界級別遍歷
在這個問題中，我們將按照給定的順序遍歷給定二叉樹的每個邊界。
我們將使用遞迴方法依次遍歷二叉樹的每個邊界。但是，我們還將學習使用棧的迭代方法來遍歷二叉樹的邊界，並提高程式碼的效能。
問題陳述
我們得到了一棵二叉樹，我們需要按照給定的順序遍歷樹的每個邊界。
從上到下遍歷左邊界。
從左到右遍歷底邊界。
從下到上遍歷右邊界。
示例
輸入
4 / \ 8 9
輸出
4, 8, 9
解釋
我們遍歷樹的邊界。
輸入
9
/ \
6 8
/ \
10 53
/ \
12 3
輸出
9, 6, 10, 12, 3, 8,
解釋
我們可以將 9、6、10 和 12 視為左邊界。我們可以將 10、12 和 3 視為底邊界。我們可以將 3、8 和 9 視為右邊界。在這裡，我們已經列印了所有邊界元素一次。
方法 1
在這種方法中，我們將編寫 3 個遞迴函式來遍歷左、底和右邊界的每個節點。
演算法
步驟 1 - 建立一個 treenode 類，其中包含整數變數、左指標和右指標，以及用於初始化節點的建構函式。
步驟 2 - 在 main() 方法中，建立一個二叉樹並執行 traverseBoundary() 函式。
步驟 3 - 在 traverseBoundary() 函式中，如果 head 為空，則執行 return 語句。否則，列印 head 節點的值。
步驟 4 - 呼叫 showLeft() 函式以獲取左子樹，從而遍歷左邊界。
步驟 4.1 - 在 showLeft() 函式中，如果 head 為空或不包含子節點，則從函式返回。
步驟 4.2 - 如果存在左子節點，則列印其值，並透過將其作為引數傳遞來呼叫 showLeft() 函式。否則，列印右子節點的值，並對右子節點執行 showLeft() 函式。
步驟 5 - 執行 showBottom() 函式以顯示左子樹和右子樹的邊界。
步驟 5.1 - 在 showBottom() 函式中，如果 head 為空，則執行 return 語句。
步驟 5.2 - 如果當前節點是葉子節點，則列印其值。
步驟 5.3 - 對左子節點和右子節點執行 showBottom() 函式。
步驟 6 - 執行 showRight() 函式以遍歷右邊界。
步驟 6.1 - 在 showRIght() 函式中，如果 head 為空或不包含子節點，則執行 return。
步驟 6.2 - 如果右節點不為空，則對右子樹執行 showRight() 函式，並列印右節點的值。在這裡，我們是在函式呼叫之後列印節點值，因為我們需要從下到上遍歷樹。
步驟 6.3 - 如果右子節點不存在但左子節點存在，則對左子節點進行遞迴呼叫，並在之後列印其值。
示例
#include <bits/stdc++.h>
using namespace std;
class treenode {
public:
int val;
treenode *left, *right;
// constructor
treenode() {
left = NULL;
right = NULL;
}
};
void showBottom(treenode *head) {
// Base case
if (head == NULL)
return;
// When head node is a leaf node
if ((head->left) == NULL && (head->right) == NULL)
cout << head->val << " ";
// Traverse left subtree
showBottom(head->left);
// Traverse the right subtree
showBottom(head->right);
}
void showLeft(treenode *head) {
if (head == NULL && (head->left == NULL && head->right == NULL))
return;
// When the left child exists
if (head->left != NULL) {
cout << head->val << " ";
// Recursive function call
showLeft(head->left);
} else if (head->right != NULL) {
// When the left child not exists
cout << head->val << " ";
showLeft(head->right);
}
}
void showRight(treenode *head) {
// Base case
if (head == NULL || (head->left == NULL && head->right == NULL))
return;
// When a right child is present
if (head->right != NULL) {
showRight(head->right);
cout << head->val << " ";
}
// When the right child is not present
else if (head->left != NULL) {
showRight(head->left);
cout << head->val << " ";
}
}
void traverseBoundary(treenode *head) {
// When the tree is null
if (head == NULL)
return;
// pRoot node
cout << head->val << " ";
// Showing left boundary
showLeft(head->left);
// Showing the bottom of the left subtree
showBottom(head->left);
// Showing the bottom of the right subtree
showBottom(head->right);
// Show the right boundary
showRight(head->right);
}
treenode *createNewNode(int val) {
treenode *temp = new treenode();
temp->val = val;
return temp;
}
int main() {
treenode *head = createNewNode(9);
head->left = createNewNode(6);
head->right = createNewNode(8);
head->left->left = createNewNode(10);
head->left->right = createNewNode(53);
head->left->right->left = createNewNode(12);
head->left->right->right = createNewNode(3);
traverseBoundary(head);
}
輸出
9 6 10 12 3 8
時間複雜度 - O(N) 以遍歷每個節點。
空間複雜度 - 遞迴棧的 O(H)。
方法 2
在這種方法中，我們將使用棧資料結構來遍歷二叉樹的每個邊界。
演算法
步驟 1 - 當 head 不為空時，執行以下步驟。
步驟 2 - 如果 head 不包含任何子節點，則列印其值並從函式返回。
步驟 3 - 定義 l_nodes 列表。遍歷樹的每個左節點並將其推入 l_nodes。
步驟 4 - 定義 stack_1 和 stack_2 分別儲存所有節點和葉子節點。將 head 節點插入 stack1。
步驟 5 - 現在，進行迭代，直到 stack1 變為空。
步驟 5.1 - 在迴圈中，從棧中彈出節點。如果其子節點存在，則將子節點元素插入棧中。如果子節點不存在，則將節點插入 stack_2。
步驟 6 - 現在，將 stack_2 的所有元素插入 l_nodes。
步驟 7 - 現在，定義 rightNode 列表，遍歷所有右節點，並將它們插入列表中。此外，反轉 rightNodes 列表。
步驟 8 - 將 rightNodes 的所有節點追加到 l_nodes 列表中，並列印 l_nodes 的元素。
示例
#include <bits/stdc++.h>
using namespace std;
class treenode {
public:
int val;
treenode *left, *right;
// constructor
treenode() {
left = NULL;
right = NULL;
}
};
void traverseBoundary(treenode *head) {
if (head != NULL) {
// For a tree with a single node
if ((head->left == NULL) && (head->right == NULL)) {
cout << head->val << endl;
return;
}
vector<treenode *> l_nodes; // To store node order
l_nodes.push_back(head);
treenode *leftNode = head->left; // For left boundary traversal
// Insert left noes in the list
while (leftNode->left) {
l_nodes.push_back(leftNode);
leftNode = leftNode->left;
}
stack<treenode *> stack_1; // To store all nodes
stack<treenode *> stack_2; // For storing leaf nodes
stack_1.push(head); // Insert head
while (!stack_1.empty()) {
treenode *temp = stack_1.top();
stack_1.pop();
// Insert left child in a stack
if (temp->left)
stack_1.push(temp->left);
// Insert right child in the stack
if (temp->right)
stack_1.push(temp->right);
// For leaf node
else if (!temp->left && !temp->right)
stack_2.push(temp);
}
// Show all leaf nodes
while (!stack_2.empty()) {
l_nodes.push_back(stack_2.top());
stack_2.pop();
}
vector<treenode *> rightNodes; // Right boundary
treenode *r_node = head->right;
while (r_node->right) {
rightNodes.push_back(r_node);
r_node = r_node->right;
}
reverse(rightNodes.begin(), rightNodes.end()); // Revere right node order
l_nodes.insert(l_nodes.end(), rightNodes.begin(), rightNodes.end()); // Merge two list
// Printing the boundary traversal
for (auto p : l_nodes) {
cout << p->val << " ";
}
cout << endl;
return;
}
}
treenode *createNewNode(int val) {
treenode *temp = new treenode();
temp->val = val;
return temp;
}
int main() {
treenode *head = createNewNode(9);
head->left = createNewNode(6);
head->right = createNewNode(8);
head->left->left = createNewNode(10);
head->left->right = createNewNode(53);
head->left->right->left = createNewNode(12);
head->left->right->right = createNewNode(3);
traverseBoundary(head);
}
輸出
9 6 10 12 3 8
時間複雜度 - O(N)
空間複雜度 - O(N)
使用棧的迭代方法比遞迴方法更快，但消耗更多記憶體，這可能不適合處理大型資料。
126 次瀏覽
