資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會研究
時尚研究
法律研究從給定的先序遍歷中構造二叉搜尋樹-第 2 部分 in C++
假設我們有先序遍歷。我們基於此遍歷生成樹。如果遍歷類似於 [10, 5, 1, 7, 40, 50]，那麼樹形結構將如下所示 −
為了解決這個問題，我們將遵循以下步驟 −
建立空棧
將第一個值作為根並將其推入棧中。
現在，持續彈出，直到棧不為空且下一個值大於棧頂元素，將其作為最後彈出的節點的右子節點。現在將新節點推入棧中。
當下一個值小於棧頂元素時，將其作為棧頂元素的左子節點。現在將新節點推入棧中。
重複步驟 2 和 3，直到檢查完所有先序列表元素。
示例
#include <iostream>
#include <stack>
using namespace std;
class node {
public:
int data;
node *left;
node *right;
};
node* getNode (int data) {
node* temp = new node();
temp->data = data;
temp->left = temp->right = NULL;
return temp;
}
node* constructTree ( int pre[], int size ) {
stack<node*> stk;
node* root = getNode( pre[0] );
stk.push(root);
int i;
node* temp;
for ( i = 1; i < size; ++i ) {
temp = NULL;
while ( !stk.empty() && pre[i] > stk.top()->data ) {
temp = stk.top();
stk.pop();
}
if ( temp != NULL) {
temp->right = getNode( pre[i] );
stk.push(temp->right);
} else {
node* peek_node = stk.top();
peek_node->left = getNode( pre[i] );
stk.push(stk.top()->left);
}
}
return root;
}
void inord (node* node) {
if (node == NULL)
return;
inord(node->left);
cout << node->data << " ";
inord(node->right);
}
int main () {
int pre[] = {10, 5, 1, 7, 40, 50};
int size = sizeof( pre ) / sizeof( pre[0] );
node *root = constructTree(pre, size);
cout << "Inorder traversal: ";
inord(root);
}輸出
Inorder traversal: 1 5 7 10 40 50
更新於： 2020 年 1 月 3 日
158 次瀏覽
廣告