摘要：然而，一棵給定的二叉搜索樹卻可以由多種不同的插入序列得到。輸出格式對每一組需要檢查的序列，如果其生成的二叉搜索樹跟對應(yīng)的初始序列生成的一樣，輸出，否則輸出。
本篇為關(guān)于樹的編程題，給出編譯器 C++(g++)的解答。主要記錄題意理解和代碼學(xué)習(xí)過程。
1 樹的同構(gòu)
題目
給定兩棵樹T1和T2。如果T1可以通過若干次左右孩子互換就變成T2，則我們稱兩棵樹是“同構(gòu)”的。例如圖1給出的兩棵樹就是同構(gòu)的，因為我們把其中一棵樹的結(jié)點A、B、G的左右孩子互換后，就得到另外一棵樹。而圖2就不是同構(gòu)的。
現(xiàn)給定兩棵樹，請你判斷它們是否是同構(gòu)的。
輸入格式：
輸入給出2棵二叉樹樹的信息。對于每棵樹，首先在一行中給出一個非負整數(shù)N (≤10)，即該樹的結(jié)點數(shù)（此時假設(shè)結(jié)點從0到N?1編號）；隨后N行，第i行對應(yīng)編號第i個結(jié)點，給出該結(jié)點中存儲的1個英文大寫字母、其左孩子結(jié)點的編號、右孩子結(jié)點的編號。如果孩子結(jié)點為空，則在相應(yīng)位置上給出“-”。給出的數(shù)據(jù)間用一個空格分隔。注意：題目保證每個結(jié)點中存儲的字母是不同的。
輸出格式：
如果兩棵樹是同構(gòu)的，輸出“Yes”，否則輸出“No”。
輸入樣例1（對應(yīng)圖1）：
8
A 1 2
B 3 4
C 5 -
D - -
E 6 -
G 7 -
F - -
H - -
8
G - 4
B 7 6
F - -
A 5 1
H - -
C 0 -
D - -
E 2 -
輸出樣例1:
Yes
輸入樣例2（對應(yīng)圖2）：
8
B 5 7
F - -
A 0 3
C 6 -
H - -
D - -
G 4 -
E 1 -
8
D 6 -
B 5 -
E - -
H - -
C 0 2
G - 3
F - -
A 1 4
輸出樣例2:
No
解讀題目
首先理解同構(gòu)的意思，題目中的同構(gòu)是指左右孩子相同即可。一種簡單的判斷兩棵樹是否同構(gòu)的方法是看結(jié)點的兒子，如果都一樣，則是同構(gòu)。很明顯，圖1中的兩棵樹是同構(gòu)的，而圖2中的兩棵樹C下面的兒子就不同，因此它們不同構(gòu)。
本題要求我們輸入兩棵樹的信息，判斷它們是否同構(gòu)。這棵二叉樹的信息表示如輸入樣例所示，第一個數(shù)是整數(shù)，告訴我們這棵樹有幾個結(jié)點，對每個結(jié)點來說有三個信息：結(jié)點本身，左兒子，右兒子。左右兒子通過編號來表示，若為空則用-來表示。但要注意的是這里沒有規(guī)定一定要從根節(jié)點來開始編號，即能以任意的順序進行編號。所以要解這道題我們還需要進行判別根結(jié)點在哪里。
我們需要的事情有三個：二叉樹表示，建二叉樹，同構(gòu)判別。
實現(xiàn)代碼
#include
#include
using namespace std;
#define Max_Node 11
#define END -1
typedef struct node
{
char value;
int left;
int right;
}Node;
//獲取樹的輸入，并將輸入的字符合理轉(zhuǎn)化成整型數(shù)字
void CreateTree(vector& Tree,int N)
{
char value,left,right;
for (int i=0; i>value>>left>>right;
Tree[i].value=value;
if (left=="-")
{
Tree[i].left=END;
}else
{
Tree[i].left=left-"0";
}
if (right=="-")
{
Tree[i].right=END;
}else
{
Tree[i].right=right-"0";
}
}
}
//尋找樹的樹根：樹根沒有其它的結(jié)點指向它
int FindTreeRoot(vector& Tree,int N)
{
int Flag[Max_Node];
for (int i=0; i& Tree1,vector& Tree2)
{
if (Tree1[Root1].value==Tree2[Root2].value)
{
//兩結(jié)點相等，并都是葉子結(jié)點
if (Tree1[Root1].left==END && Tree1[Root1].right==END && Tree2[Root2].left==END && Tree2[Root2].right==END)
{
return true;
}
//以下四種情況：兩個結(jié)點都是有一個孩子為空，另一個子樹不空且這兩個孩子相等的情形
if (Tree1[Tree1[Root1].left].value==Tree2[Tree2[Root2].left].value && Tree1[Root1].right==END && Tree2[Root2].right==END)
{
return IsOmorphic(Tree1[Root1].left, Tree2[Root2].left, Tree1, Tree2);
}
if (Tree1[Tree1[Root1].left].value==Tree2[Tree2[Root2].right].value && Tree1[Root1].right==END && Tree2[Root2].left==END)
{
return IsOmorphic(Tree1[Root1].left, Tree2[Root2].right, Tree1, Tree2);
}
if (Tree1[Tree1[Root1].right].value==Tree2[Tree2[Root2].left].value && Tree1[Root1].left==END && Tree2[Root2].right==END)
{
return IsOmorphic(Tree1[Root1].right, Tree2[Root2].left, Tree1, Tree2);
}
if (Tree1[Tree1[Root1].right].value==Tree2[Tree2[Root2].right].value && Tree1[Root1].left==END && Tree2[Root2].left==END)
{
return IsOmorphic(Tree1[Root1].right, Tree2[Root2].right, Tree1, Tree2);
}
//以下兩種：兩個結(jié)點的孩子都相等的情形
if (Tree1[Tree1[Root1].left].value==Tree2[Tree2[Root2].left].value && Tree1[Tree1[Root1].right].value==Tree2[Tree2[Root2].right].value)
{
return (IsOmorphic(Tree1[Root1].left, Tree2[Root2].left, Tree1, Tree2))&&(IsOmorphic(Tree1[Root1].right, Tree2[Root2].right, Tree1, Tree2));
}
if (Tree1[Tree1[Root1].left].value==Tree2[Tree2[Root2].right].value && Tree1[Tree1[Root1].right].value==Tree2[Tree2[Root2].left].value)
{
return (IsOmorphic(Tree1[Root1].left, Tree2[Root2].right, Tree1, Tree2))&&(IsOmorphic(Tree1[Root1].right, Tree2[Root2].left, Tree1, Tree2));
}
}
//不符合以上7種情況表明這兩棵樹不同構(gòu)
return false;
}
int main(int argc, const char * argv[])
{
//輸入兩顆二叉樹的信息
int N1=0;
cin>>N1;
vector Tree1(Max_Node);
CreateTree(Tree1,N1);
int N2=0;
cin>>N2;
vector Tree2(Max_Node);
CreateTree(Tree2,N2);
if (N1!=N2)
{
cout<<"No";
}else
{
if (N1==0)
{
cout<<"Yes";
}else
{
//建二叉樹
int root1=FindTreeRoot(Tree1,N1);
int root2=FindTreeRoot(Tree2,N2);
//判斷是否同構(gòu)
if (IsOmorphic(root1, root2, Tree1, Tree2))
{
cout<<"Yes";
}else
{
cout<<"No";
}
}
}
return 0;
}
提交結(jié)果
2 List Leaves
題目
Given a tree, you are supposed to list all the leaves in the order of top down, and left to right.
Input Specification:
Each input file contains one test case. For each case, the first line gives a positive integer N (≤10) which is the total number of nodes in the tree -- and hence the nodes are numbered from 0 to N?1. Then N lines follow, each corresponds to a node, and gives the indices of the left and right children of the node. If the child does not exist, a "-" will be put at the position. Any pair of children are separated by a space.
Output Specification:
For each test case, print in one line all the leaves" indices in the order of top down, and left to right. There must be exactly one space between any adjacent numbers, and no extra space at the end of the line.
Sample Input:
8
1 -
- -
0 -
2 7
- -
- -
5 -
4 6
Sample Output:
4 1 5
實現(xiàn)代碼
#include
#include
#include
int flag=0;//用于判斷結(jié)果輸出格式的
struct NodeInf{//樹的節(jié)點信息，左右兒子下標
int LeftIndex;
int RightIndex;
};
struct BinTreeNode{//樹節(jié)點
int Element;//編號
struct BinTreeNode* Left;
struct BinTreeNode* Right;
};
int FindTreeHead(int book[],int n)//查找樹根
{
for(int i=0;iElement=treehead;
Queue[tail++]=BinTree;
while(headElement].LeftIndex!=-1){
Temp=(struct BinTreeNode*)malloc(sizeof(struct BinTreeNode));
Temp->Element=nodeinf[Queue[head]->Element].LeftIndex;
Queue[head]->Left=Temp;
Queue[tail++]=Temp;
}
else{
Queue[head]->Left=NULL;
}
if(nodeinf[Queue[head]->Element].RightIndex!=-1){
Temp=(struct BinTreeNode*)malloc(sizeof(struct BinTreeNode));
Temp->Element=nodeinf[Queue[head]->Element].RightIndex;
Queue[head]->Right=Temp;
Queue[tail++]=Temp;
}
else{
Queue[head]->Right=NULL;
}
if(Queue[head]->Left==NULL&&Queue[head]->Right==NULL){//判斷是否為葉子
if(flag)
printf("%c"," ");
printf("%d",Queue[head]->Element);
flag=1;
}
head++;
}
putchar("
");
return;
}
int main()
{
int n;
char ch;
struct NodeInf nodeinf[10];//存儲節(jié)點信息
int treehead;//樹根
int book[10];//標記是別人兒子的節(jié)點，則未標記的就為樹根
memset(book,0,sizeof(book));
scanf("%d",&n);
for(int i=0;i=0&&ch-"0"<=9){
nodeinf[i].LeftIndex=ch-"0";
book[ch-"0"]=1;
}
else
nodeinf[i].LeftIndex=-1;
getchar();
scanf("%c",&ch);
if(ch-"0">=0&&ch-"0"<=9){
nodeinf[i].RightIndex=ch-"0";
book[ch-"0"]=1;
}
else
nodeinf[i].RightIndex=-1;
}
treehead=FindTreeHead(book,n);//找樹根
CreBinTreeAndPriLeaves(treehead,nodeinf);
return 0;
}
提交結(jié)果
3 是否同一棵二叉搜索樹
題目
給定一個插入序列就可以唯一確定一棵二叉搜索樹。然而，一棵給定的二叉搜索樹卻可以由多種不同的插入序列得到。例如分別按照序列{2, 1, 3}和{2, 3, 1}插入初始為空的二叉搜索樹，都得到一樣的結(jié)果。于是對于輸入的各種插入序列，你需要判斷它們是否能生成一樣的二叉搜索樹。
輸入格式:
輸入包含若干組測試數(shù)據(jù)。每組數(shù)據(jù)的第1行給出兩個正整數(shù)N (≤10)和L，分別是每個序列插入元素的個數(shù)和需要檢查的序列個數(shù)。第2行給出N個以空格分隔的正整數(shù)，作為初始插入序列。最后L行，每行給出N個插入的元素，屬于L個需要檢查的序列。
簡單起見，我們保證每個插入序列都是1到N的一個排列。當讀到N為0時，標志輸入結(jié)束，這組數(shù)據(jù)不要處理。
輸出格式:
對每一組需要檢查的序列，如果其生成的二叉搜索樹跟對應(yīng)的初始序列生成的一樣，輸出“Yes”，否則輸出“No”。
輸入樣例:
4 2
3 1 4 2
3 4 1 2
3 2 4 1
2 1
2 1
1 2
0
輸出樣例:
Yes
No
No
解讀題目
本題要求我們對于輸入的各種插入序列，判斷它們是否能生成一樣的二叉搜索樹。在輸入樣例中包含三部分內(nèi)容。第一部分是第一行的兩個整數(shù)：4表示插入序列所包含的個數(shù)，即二叉樹的結(jié)點個數(shù)，2表示后面有兩個序列需要取比較和前面是否一樣；第二部分是輸入的序列；第三部分就是后面輸入的若干組序列，它們要和第一組序列做比較。
這道題實際上是兩個序列是否對應(yīng)相同搜索樹的判別。
實現(xiàn)代碼
#include
#include
using namespace std;
typedef struct node Node;
struct node{
int left;
int right;
};
//初始化二叉樹函數(shù)
void Init_Tree(vector &Tree,int N)
{
for ( int i = 1 ; i <= N ; i++){
Tree[i].left = -1;
Tree[i].right = -1;
}
}
//建樹函數(shù)
void Build_Tree(vector &Tree,int N)
{
int value;
int flag = 0;
int root = 0;
int pre = 0;
while(N--){
cin>>value;
if ( flag == 0){
root = value;
pre = root;
flag = 1;
}else{
while(1){
//當前輸入值比訪問的上一個結(jié)點pre（pre最初為根結(jié)點）大，且pre有右孩子
if (value > pre && Tree[pre].right != -1){
pre = Tree[pre].right;
}
//當前輸入值比訪問的上一個結(jié)點pre（pre最初為根結(jié)點）大，且pre無右孩子
if (value > pre && Tree[pre].right == -1){
Tree[pre].right = value;
pre = root;//下一次輸入數(shù)字也從根結(jié)點開始比較
break;
}
//當前輸入值比訪問的上一個結(jié)點pre（pre最初為根結(jié)點）小，且pre有左孩子
if (value &Tree1,vector &Tree2 ,int N)
{
bool flag = true;
for ( int i = 1 ; i <= N ; i++){
if (!(Tree1[i].left == Tree2[i].left && Tree1[i].right == Tree2[i].right)){
flag = false;
break;
}
}
return flag;
}
int main()
{
int N,L;
int flag = 0;
while(1){
cin>>N;
if ( N == 0){
break;
}
cin>>L;
vector> Tree(L,vector(11));
vector tree(11);
Init_Tree(tree,N);
for ( int i = 0 ; i < L ; i++){
Init_Tree(Tree[i],N);
}
Build_Tree(tree,N);
for ( int i = 0 ; i < L ; i++){
Build_Tree(Tree[i],N);
if (Compare_Tree(tree,Tree[i],N)){
if ( flag == 0){
flag = 1;
cout<<"Yes";
}else{
cout<<"
"<<"Yes";
}
}else{
if ( flag == 0){
flag = 1;
cout<<"No";
}else{
cout<<"
"<<"No";
}
}
}
}
return 0;
}
提交結(jié)果
4 Root of AVL Tree
題目
An AVL tree is a self-balancing binary search tree. In an AVL tree, the heights of the two child subtrees of any node differ by at most one; if at any time they differ by more than one, rebalancing is done to restore this property. Figures 1-4 illustrate the rotation rules.
Now given a sequence of insertions, you are supposed to tell the root of the resulting AVL tree.
Input Specification:
Each input file contains one test case. For each case, the first line contains a positive integer N (≤20) which is the total number of keys to be inserted. Then N distinct integer keys are given in the next line. All the numbers in a line are separated by a space.
Output Specification:
For each test case, print the root of the resulting AVL tree in one line.
Sample Input 1:
5
88 70 61 96 120
Sample Output 1:
70
Sample Input 2:
7
88 70 61 96 120 90 65
Sample Output 2:
88
實現(xiàn)代碼
#include
using namespace std;
typedef int ElemType;
typedef struct AVLTreeNode *AVLTree;
struct AVLTreeNode {
ElemType data;
AVLTree left;
AVLTree right;
int height;
};
int GetHeight(AVLTreeNode *tree)
{
if (tree == NULL)
return -1; //空樹返回-1
else
return tree->height;
}
int Max(int a,int b)
{
if (a > b)
return a;
else
return b;
}
AVLTree SingleLeftRotation(AVLTree A)
{ /* 注意：A 必須有一個左子結(jié)點 B */
/* 將 A 與 B 做如圖 4.35 所示的左單旋，更新 A 與 B 的高度，返回新的根結(jié)點 B */
AVLTree B = A->left;
A->left = B->right;
B->right = A;
A->height = Max(GetHeight(A->left), GetHeight(A->right)) + 1;
B->height = Max(GetHeight(B->left), A->height) + 1;
return B;
}
AVLTree SingleRightRotation(AVLTree A)
{ /* 注意：A 必須有一個左子結(jié)點 B */
/* 將 A 與 B 做如圖 4.35 所示的右單旋，更新 A 與 B 的高度，返回新的根結(jié)點 B */
AVLTree B = A->right;
A->right = B->left;
B->left = A;
A->height = Max(GetHeight(A->right), GetHeight(A->left)) + 1;
B->height = Max(GetHeight(B->right), A->height) + 1;
return B;
}
AVLTree DoubleLeftRightRotation(AVLTree A)
{ /* 注意：A 必須有一個左子結(jié)點 B，且 B 必須有一個右子結(jié)點 C */
/* 將 A、B 與 C 做如圖 4.38 所示的兩次單旋，返回新的根結(jié)點 C */
A->left = SingleRightRotation(A->left); /*將 B 與 C 做右單旋，C 被返回*/
return SingleLeftRotation(A); /*將 A 與 C 做左單旋，C 被返回*/
}
AVLTree DoubleRightLeftRotation(AVLTree A)
{ /* 注意：A 必須有一個左子結(jié)點 B，且 B 必須有一個右子結(jié)點 C */
/* 將 A、B 與 C 做如圖 4.38 所示的兩次單旋，返回新的根結(jié)點 C */
A->right = SingleLeftRotation(A->right); /*將 B 與 C 做右單旋，C 被返回*/
return SingleRightRotation(A); /*將 A 與 C 做左單旋，C 被返回*/
}
AVLTree AVL_Insertion(ElemType X, AVLTree T)
{
/* 將 X 插入 AVL 樹 T 中，并且返回調(diào)整后的 AVL 樹 */
if (!T)
{
/* 若插入空樹，則新建包含一個結(jié)點的樹 */
T = (AVLTree)malloc(sizeof(struct AVLTreeNode));
T->data = X;
T->height = 0;
T->left = T->right = NULL;
}
/* if (插入空樹) 結(jié)束 */
else if (X < T->data)
{
/* 插入 T 的左子樹 */
T->left = AVL_Insertion(X, T->left);
if (GetHeight(T->left) - GetHeight(T->right) == 2)
/* 需要左旋 */
if (X < T->left->data)
T = SingleLeftRotation(T); /* 左單旋 */
else
T = DoubleLeftRightRotation(T); /* 左-右雙旋 */
}
/* else if (插入左子樹) 結(jié)束 */
else if (X > T->data)
{ /* 插入 T 的右子樹 */
T->right = AVL_Insertion(X, T->right);
if (GetHeight(T->left) - GetHeight(T->right) == -2) /* 需要右旋 */
if (X > T->right->data)
T = SingleRightRotation(T); /* 右單旋 */
else
T = DoubleRightLeftRotation(T); /* 右-左雙旋 */
}
/* else if (插入右子樹) 結(jié)束 */
/* else X == T->Data，無須插入 */
T->height = Max(GetHeight(T->left), GetHeight(T->right)) + 1; /*更新樹高*/
return T;
}
int main()
{
int n;
cin >> n;
AVLTree root = NULL;
int x;
for (int i = 0; i < n; i++)
{
cin >> x;
root = AVL_Insertion(x, root);
}
cout << root->data;
return 0;
}
提交結(jié)果
5 堆中的路徑
題目
將一系列給定數(shù)字插入一個初始為空的小頂堆H[]。隨后對任意給定的下標i，打印從H[i]到根結(jié)點的路徑。
輸入格式:
每組測試第1行包含2個正整數(shù)N和M(≤1000)，分別是插入元素的個數(shù)、以及需要打印的路徑條數(shù)。下一行給出區(qū)間[-10000, 10000]內(nèi)的N個要被插入一個初始為空的小頂堆的整數(shù)。最后一行給出M個下標。
輸出格式:
對輸入中給出的每個下標i，在一行中輸出從H[i]到根結(jié)點的路徑上的數(shù)據(jù)。數(shù)字間以1個空格分隔，行末不得有多余空格。
輸入樣例:
5 3
46 23 26 24 10
5 4 3
輸出樣例:
24 23 10
46 23 10
26 10
解讀題目
本題實際上是一個最小堆查詢問題，在輸入樣例中給定5個數(shù)據(jù)構(gòu)成一個最小堆，查詢3次。第二行的5個數(shù)據(jù)就構(gòu)成了一個最小堆，第三行的5 4 3分別代表最小堆中的下標。
實現(xiàn)代碼
#include
using namespace std;
class MinHeap{
private :
int* data;
int capacity;
int size;
public:
MinHeap(int N){
this->capacity = N;
this->size = 0;
this->data = new int[10000];
this->data[0] = -10000;
}
int GetSize(){
return this->size;
}
bool IsFull(){
return this->size == this->capacity;
}
bool IsEmpty(){
return this->size == 0;
}
void Insert(int data){
if ( this->IsFull()){
return ;
}
int i = ++this->size;
for ( ; this->data[i/2] > data ; i /= 2){
this->data[i] = this->data[i/2];
}
this->data[i] = data;
}
void Find_Path(int index){
if (index > this->size){
return;
}
bool flag = false;
for ( int i = index ; i >= 1 ; i /= 2){
if (!flag){
cout<data[i];
flag = true;
}else{
cout<<" "<data[i];
}
}
}
};
int main()
{
int N,L;
cin>>N>>L;
MinHeap minheap(N);
for ( int i = 1 ; i <= N ; i++){
int data;
cin>>data;
minheap.Insert(data);
}
for ( int i = 0 ; i < L ; i++){
int index;
cin>>index;
minheap.Find_Path(index);
cout<<"
";
}
return 0;
}
提交結(jié)果
參考鏈接：
03-樹1 樹的同構(gòu) (25分)
PTA List Leaves
04-樹4 是否同一棵二叉搜索樹 (25分)
Root of AVL Tree
05-樹7 堆中的路徑 (25分)
不足之處，歡迎指正。
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/44784.html
