資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會科學
時裝研究
法律研究在不生成樹的情況下檢查相同的二叉搜尋樹（英語）
有兩個陣列來表示二叉搜尋樹的元素。如果從左至右從陣列中提取元素，並形成二叉搜尋樹，那麼透過從兩個陣列中提取，將會形成同一棵二叉搜尋樹。必須檢查是否兩者形成的相同。但是約束條件是無法形成二叉搜尋樹。假設兩個陣列分別為 {2, 4, 1, 3} 和 {2, 1, 4, 3}，如果觀察一下，這兩個序列都可以形成相同的二叉搜尋樹。
方法很簡單。眾所周知，左子樹的元素小於根節點，右子樹的元素大於根節點。如果對於每個元素 x，x 的左子樹和右子樹中的元素在兩個陣列中都出現在它的後面，那麼這兩個列表可以表示相同的二叉搜尋樹。左子樹和右子樹的根節點也是如此。將檢查在兩個陣列中較小的下一個元素和較大的下一個元素是否相同。對於左子樹和右子樹，相同的方式進行遞迴檢查。
示例
#include <iostream>
using namespace std;
bool isSameCheckHelper(int tree1[], int tree2[], int n, int i1, int i2, int min, int max) {
int j, k;
for (j = i1; j < n; j++)
if (tree1[j] > min && tree1[j] < max)
break;
for (k = i2; k < n; k++)
if (tree2[k] > min && tree2[k] < max)
break;
if (j==n && k==n) //If the parent element is leaf in both arrays
return true;
if (((j==n)^(k==n)) || tree1[j]!=tree2[k])
return false;
return isSameCheckHelper(tree1, tree2, n, j+1, k+1, tree1[j], max) &&
// for Right Subtree
isSameCheckHelper(tree1, tree2, n, j+1, k+1, min, tree1[j]); // for Left Subtree
}
bool areBSTSame(int first[], int second[], int n) {
return isSameCheckHelper(first, second, n, 0, 0, INT_MIN, INT_MAX);
}
int main() {
int first[] = {8, 3, 6, 1, 4, 7, 10, 14, 13};
int second[] = {8, 10, 14, 3, 6, 4, 1, 7, 13};
int n=sizeof(first)/sizeof(first[0]);
if(areBSTSame(first, second, n)) {
cout << "Two BSTs are same";
} else {
cout << "Two BSTs are not same";
}
}輸出
Two BSTs are same
更新於：2019 年 10 月 21 日
87 次瀏覽
廣告