【数据结构_浙江大学MOOC】第三四五讲树

阅读量：5964 次

发布时间：2019-06-19

本文共 15447 字，大约阅读时间需要 51 分钟。

本篇为关于树的编程题，给出编译器 C++(g++)的解答。主要记录题意理解和代码学习过程。

1 树的同构

题目

给定两棵树T1和T2。如果T1可以通过若干次左右孩子互换就变成T2，则我们称两棵树是“同构”的。例如图1给出的两棵树就是同构的，因为我们把其中一棵树的结点A、B、G的左右孩子互换后，就得到另外一棵树。而图2就不是同构的。

现给定两棵树，请你判断它们是否是同构的。

输入格式：

输入给出2棵二叉树树的信息。对于每棵树，首先在一行中给出一个非负整数N (≤10)，即该树的结点数（此时假设结点从0到N−1编号）；随后N行，第i行对应编号第i个结点，给出该结点中存储的1个英文大写字母、其左孩子结点的编号、右孩子结点的编号。如果孩子结点为空，则在相应位置上给出“-”。给出的数据间用一个空格分隔。注意：题目保证每个结点中存储的字母是不同的。

输出格式：

如果两棵树是同构的，输出“Yes”，否则输出“No”。

输入样例1（对应图1）：

8A 1 2B 3 4C 5 -D - -E 6 -G 7 -F - -H - -8G - 4B 7 6F - -A 5 1H - -C 0 -D - -E 2 -

输出样例1:

Yes

输入样例2（对应图2）：

8B 5 7F - -A 0 3C 6 -H - -D - -G 4 -E 1 -8D 6 -B 5 -E - -H - -C 0 2G - 3F - -A 1 4

输出样例2:

No

解读题目

首先理解同构的意思，题目中的同构是指左右孩子相同即可。一种简单的判断两棵树是否同构的方法是看结点的儿子，如果都一样，则是同构。很明显，图1中的两棵树是同构的，而图2中的两棵树C下面的儿子就不同，因此它们不同构。

本题要求我们输入两棵树的信息，判断它们是否同构。这棵二叉树的信息表示如输入样例所示，第一个数是整数，告诉我们这棵树有几个结点，对每个结点来说有三个信息：结点本身，左儿子，右儿子。左右儿子通过编号来表示，若为空则用-来表示。但要注意的是这里没有规定一定要从根节点来开始编号，即能以任意的顺序进行编号。所以要解这道题我们还需要进行判别根结点在哪里。

我们需要的事情有三个：二叉树表示，建二叉树，同构判别。

实现代码

#include 
    
     #include 
     
       using namespace std; #define Max_Node 11#define END -1 typedef struct node{    char value;    int left;    int right;}Node;//获取树的输入，并将输入的字符合理转化成整型数字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';        }    }}//寻找树的树根：树根没有其它的结点指向它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) { //两结点相等，并都是叶子结点 if (Tree1[Root1].left==END && Tree1[Root1].right==END && Tree2[Root2].left==END && Tree2[Root2].right==END) { return true; } //以下四种情况：两个结点都是有一个孩子为空，另一个子树不空且这两个孩子相等的情形 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); } //以下两种：两个结点的孩子都相等的情形 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种情况表明这两棵树不同构 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); //判断是否同构 if (IsOmorphic(root1, root2, Tree1, Tree2)) { cout<<"Yes"; }else { cout<<"No"; } } } return 0;}

提交结果

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:

81 -- -0 -2 7- -- -5 -4 6

Sample Output:

4 1 5

实现代码

#include 
    
     #include 
     
      #include 
      
       int flag=0;//用于判断结果输出格式的struct NodeInf{//树的节点信息，左右儿子下标    int LeftIndex;    int RightIndex;};struct BinTreeNode{//树节点    int Element;//编号    struct BinTreeNode* Left;    struct BinTreeNode* Right;};int FindTreeHead(int book[],int n)//查找树根{    for(int i=0;i
       
        Element=treehead;    Queue[tail++]=BinTree;    while(head
        
         Element].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('\n');    return;}int main(){    int n;    char ch;    struct NodeInf nodeinf[10];//存储节点信息    int treehead;//树根    int book[10];//标记是别人儿子的节点，则未标记的就为树根    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;}

提交结果

3 是否同一棵二叉搜索树

题目

给定一个插入序列就可以唯一确定一棵二叉搜索树。然而，一棵给定的二叉搜索树却可以由多种不同的插入序列得到。例如分别按照序列{2, 1, 3}和{2, 3, 1}插入初始为空的二叉搜索树，都得到一样的结果。于是对于输入的各种插入序列，你需要判断它们是否能生成一样的二叉搜索树。

输入格式:

输入包含若干组测试数据。每组数据的第1行给出两个正整数N (≤10)和L，分别是每个序列插入元素的个数和需要检查的序列个数。第2行给出N个以空格分隔的正整数，作为初始插入序列。最后L行，每行给出N个插入的元素，属于L个需要检查的序列。

简单起见，我们保证每个插入序列都是1到N的一个排列。当读到N为0时，标志输入结束，这组数据不要处理。

输出格式:

对每一组需要检查的序列，如果其生成的二叉搜索树跟对应的初始序列生成的一样，输出“Yes”，否则输出“No”。

输入样例:

4 23 1 4 23 4 1 23 2 4 12 12 11 20

输出样例:

YesNoNo

解读题目

本题要求我们对于输入的各种插入序列，判断它们是否能生成一样的二叉搜索树。在输入样例中包含三部分内容。第一部分是第一行的两个整数：4表示插入序列所包含的个数，即二叉树的结点个数，2表示后面有两个序列需要取比较和前面是否一样；第二部分是输入的序列；第三部分就是后面输入的若干组序列，它们要和第一组序列做比较。

这道题实际上是两个序列是否对应相同搜索树的判别。

实现代码

#include 
    
     #include 
     
      using namespace std;typedef struct node Node;struct node{    int left;    int right;};//初始化二叉树函数 void Init_Tree(vector
      
        &Tree,int N){    for ( int i = 1 ; i <= N ; i++){        Tree[i].left = -1;        Tree[i].right = -1;    }}//建树函数 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){                //当前输入值比访问的上一个结点pre（pre最初为根结点）大，且pre有右孩子                  if (value > pre && Tree[pre].right != -1){                    pre = Tree[pre].right;                }                //当前输入值比访问的上一个结点pre（pre最初为根结点）大，且pre无右孩子                  if (value > pre && Tree[pre].right == -1){                    Tree[pre].right = value;                    pre = root;//下一次输入数字也从根结点开始比较                      break;                }                //当前输入值比访问的上一个结点pre（pre最初为根结点）小，且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<<"\n"<<"Yes";                }            }else{                if ( flag == 0){                    flag = 1;                    cout<<"No";                }else{                    cout<<"\n"<<"No";                 }            }        }    }    return 0;}

提交结果

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:

588 70 61 96 120

Sample Output 1:

Sample Input 2:

788 70 61 96 120 90 65

Sample Output 2:

实现代码

#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 必须有一个左子结点 B */    /* 将 A 与 B 做如图 4.35 所示的左单旋，更新 A 与 B 的高度，返回新的根结点 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 必须有一个左子结点 B */    /* 将 A 与 B 做如图 4.35 所示的右单旋，更新 A 与 B 的高度，返回新的根结点 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 必须有一个左子结点 B，且 B 必须有一个右子结点 C */       /* 将 A、B 与 C 做如图 4.38 所示的两次单旋，返回新的根结点 C */              A->left = SingleRightRotation(A->left); /*将 B 与 C 做右单旋，C 被返回*/    return SingleLeftRotation(A); /*将 A 与 C 做左单旋，C 被返回*/} AVLTree DoubleRightLeftRotation(AVLTree A){    /* 注意：A 必须有一个左子结点 B，且 B 必须有一个右子结点 C */    /* 将 A、B 与 C 做如图 4.38 所示的两次单旋，返回新的根结点 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 中，并且返回调整后的 AVL 树 */      if (!T)     {         /* 若插入空树，则新建包含一个结点的树 */           T = (AVLTree)malloc(sizeof(struct AVLTreeNode));           T->data = X;           T->height = 0;           T->left = T->right = NULL;     }     /* if (插入空树) 结束 */    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 (插入左子树) 结束 */           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 (插入右子树) 结束 */    /* 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;}

提交结果

5 堆中的路径

题目

将一系列给定数字插入一个初始为空的小顶堆H[]。随后对任意给定的下标i，打印从H[i]到根结点的路径。

输入格式:

每组测试第1行包含2个正整数N和M(≤1000)，分别是插入元素的个数、以及需要打印的路径条数。下一行给出区间[-10000, 10000]内的N个要被插入一个初始为空的小顶堆的整数。最后一行给出M个下标。

输出格式:

对输入中给出的每个下标i，在一行中输出从H[i]到根结点的路径上的数据。数字间以1个空格分隔，行末不得有多余空格。

输入样例:

5 346 23 26 24 105 4 3

输出样例:

24 23 1046 23 1026 10

解读题目

本题实际上是一个最小堆查询问题，在输入样例中给定5个数据构成一个最小堆，查询3次。第二行的5个数据就构成了一个最小堆，第三行的5 4 3分别代表最小堆中的下标。

实现代码

#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<<"\n";     }     return 0;}