給定一個插入序列就可以唯一確定一棵二叉搜索樹。然而，一棵給定的二叉搜索樹卻可以由多種不同的插入序列得到。例如分別按照序列{2, 1, 3}和{2, 3, 1}插入初始為空的二叉搜索樹，都得到一樣的結(jié)果。于是對于輸入的各種插入序列，你需要判斷它們是否能生成一樣的二叉搜索樹。

?

?

?

#include<iostream>
#include<vector>

using namespace std;

#define Max_Node 11
#define END -1

typedef struct node
{
int left;
int right;
}Node;

void Initialize_Tree(vector<Node>& Tree,int N)//初始化樹
{
for (int i=1; i<=N; ++i)
{
Tree[i].left=END;
Tree[i].right=END;
}
}

void Build_Tree(vector<Node>& Tree,int N)//讀取輸入并建樹
{
int value,flag=0,root=0,pre=0;
while (N--)
{
cin>>value;
if (flag==0)//讀到的第一個結(jié)點為根結(jié)點，記錄下來
{
root=value;
pre=root;
flag=1;
}else
{
while (1)
{
if (value>pre && Tree[pre].right!=END)//當(dāng)前輸入值比訪問的上一個結(jié)點pre（pre最初為根結(jié)點）大，且pre有右孩子
{
pre=Tree[pre].right;
}
if (value>pre && Tree[pre].right==END)//當(dāng)前輸入值比訪問的上一個結(jié)點pre（pre最初為根結(jié)點）大，且pre無右孩子
{
Tree[pre].right=value;
pre=root;//下一次輸入數(shù)字也從根結(jié)點開始比較
break;
}
if (value<pre && Tree[pre].left!=END)//當(dāng)前輸入值比訪問的上一個結(jié)點pre（pre最初為根結(jié)點）小，且pre有左孩子
{
pre=Tree[pre].left;
}
if (value<pre && Tree[pre].left==END)//當(dāng)前輸入值比訪問的上一個結(jié)點pre（pre最初為根結(jié)點）小，且pre無左孩子
{
Tree[pre].left=value;
pre=root;//下一次輸入數(shù)字也從根結(jié)點開始比較
break;
}
}
}
}
}

bool Compare_Tree(vector<Node> Tree1,vector<Node> Tree2,int N)//比較兩棵樹的每一個結(jié)點的左右孩子結(jié)點是否相等
{
int i=1;
for (; i<=N; ++i)
{
if (!(Tree1[i].left==Tree2[i].left && Tree1[i].right==Tree2[i].right))
{
return false;
}
}
return true;
}

int main()
{
int N,L;
int flag=0;
while (1)
{
cin>>N;
if (N==0)
{
break;
}
cin>>L;
vector<vector<Node> > vec(L,vector<Node>(Max_Node));
vector<Node> Tree(Max_Node);
Initialize_Tree(Tree, N);
for (int i=0; i<L; ++i)
{
Initialize_Tree(vec[i], N);
}
Build_Tree(Tree, N);
for (int i=0; i<L; i++)
{
Build_Tree(vec[i], N);
if (Compare_Tree(Tree, vec[i], N))
{
if (flag==0)
{
flag=1;
cout<<"Yes";
}else
{
cout<<'\n'<<"Yes";
}
}else
{
if (flag==0)
{
flag=1;
cout<<"No";
}else
{
cout<<'\n'<<"No";
}
}
}
}

return 0;
}

轉(zhuǎn)載于:https://www.cnblogs.com/JAYPARK/p/9971678.html

新人創(chuàng)作打卡挑戰(zhàn)賽發(fā)博客就能抽獎！定制產(chǎn)品紅包拿不停！

總結(jié)

以上是生活随笔為你收集整理的基础数据结构——是否同一棵二叉搜索树的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。