浙江大学MOOC数据结构-陈越、何钦铭编程练习题（第三讲）

编程题目
在这里插入图片描述
编程说明

编程环境：平台运行
编程语言：C

第一题代码

#include <stdio.h>
#include <stdlib.h>
#include<string.h>

#define MaxTree 10
#define ElementType char
#define Tree int
#define Null -1
struct TreeNode
{
    ElementType Element;
    Tree Left;
    Tree Right;
} T1[MaxTree], T2[MaxTree];

int Isomorphic(Tree,Tree);
Tree BuildTree(struct TreeNode T[]);

int main()
{
    Tree R1, R2;
    R1 = BuildTree(T1);
    R2 = BuildTree(T2);

    if (Isomorphic(R1, R2))
        printf("Yes\n");
    else
        printf("No\n");

    return 0;
}

int Isomorphic(Tree R1,Tree R2)
{
    if ( (R1==Null )&& (R2==Null) ) /* both empty */
        return 1;

    if ( ((R1==Null)&&(R2!=Null)) || ((R1!=Null)&&(R2==Null)) )
        return 0; /* one of them is empty */

    if ( T1[R1].Element != T2[R2].Element )
        return 0; /* roots are different */

    if ( ( T1[R1].Left == Null )&&( T2[R2].Left == Null ) )
        // both have no left subtree
        return Isomorphic( T1[R1].Right, T2[R2].Right );

    if ( ((T1[R1].Left!=Null)&&(T2[R2].Left!=Null))&&((T1[T1[R1].Left].Element)==(T2[T2[R2].Left].Element)) )
        // no need to swap the left and the right
        return ( Isomorphic( T1[R1].Left, T2[R2].Left ) && Isomorphic( T1[R1].Right, T2[R2].Right ) );
    else /* need to swap the left and the right */
        return ( Isomorphic( T1[R1].Left, T2[R2].Right) && Isomorphic( T1[R1].Right, T2[R2].Left ) );
}

Tree BuildTree(struct TreeNode T[])
{
    int N=0;
    int Root=Null;
    char cl,cr;
    int check[10]={0};
    scanf("%d",&N);
    if(N)
    {
        for(int i=0; i<N; i++)
            check[i] = 0;
        for(int i=0; i<N; i++)
        {
            scanf("\n%c %c %c",&T[i].Element,&cl,&cr);
            if(cl!='-')
            {
                T[i].Left=cl-'0';
                check[T[i].Left]=1;
            }
            else
                T[i].Left=Null;

            if(cr!='-')
            {
                T[i].Right=cr-'0';
                check[cr-'0']=1;
            }
            else
                T[i].Right=Null;
        }

        for(int i=0; i<N; i++)
        {
            if(check[i]==0)
            {
                Root=i;
                break;
            }
        }
    }
    return Root;
}

第二题代码

第一种方法: 实际上是一种迭代思想，一直不断往下挖，一直遇到叶子节点就打印，然后开始考虑其兄弟节点，有点像回溯算法。
第二种方法: 层次遍历，就是利用了队列的先进先出，子节点从左到右从上到下进入队列。

从左到右打印叶子节点，没有符合题目要求，具体看第二种做法。

#include <stdio.h>
#include <stdlib.h>

#define MaxTree 10
#define Tree int
#define Null -1
struct TreeNode
{
    Tree Left;
    Tree Right;
} T[MaxTree];
int Flag=0;
Tree BuildTree(struct TreeNode T[]);
void LeaveFind(Tree R);

int main()
{
    Tree R;
    R=BuildTree(T);
    LeaveFind(R);
    return 0;
}

Tree BuildTree(struct TreeNode T[])
{
    int N;
    Tree Root=Null;
    int check[10];
    char cl,cr;

    scanf("%d",&N);
    if(N)
    {
        for(int i=0;i<N;i++)
        {
            check[i]=0;
        }

        for(int i=0;i<N;i++)
        {
            scanf("\n%c %c",&cl,&cr);
            if(cl!='-')
            {
                T[i].Left=cl-'0';
                check[T[i].Left]=1;
            }
            else
                T[i].Left=Null;

            if(cr!='-')
            {
                T[i].Right=cr-'0';
                check[T[i].Right]=1;
            }
            else
                T[i].Right=Null;
        }

        for(int i=0;i<N;i++)
        {
            if(!check[i])
            {
                Root=i;
                break;
            }
        }
    }
//    //数据输入打印
//    for(int i=0; i<N; i++)
//    {
//        printf("%d %d %d\n",i,T[i].Left,T[i].Right);
//    }
    return Root;
}

//此函数适用于深度优先
void LeaveFind(Tree R)
{
    //此节点是否是叶子节点
    if(T[R].Left==Null && T[R].Right==Null)//左右子树都空，终止条件
    {
        //printf("1 ");
        if(!Flag)
            printf("%d",R);
        else
            printf(" %d",R);

        Flag++;
    }
    else if(T[R].Left==Null && T[R].Right!=Null)//左子树空，右子树继续迭代
    {
        //printf("2 ");
        LeaveFind(T[R].Right);
    }
    else if(T[R].Left!=Null && T[R].Right==Null)//右子树空，左子树继续迭代
    {
        //printf("3 ");
        LeaveFind(T[R].Left);
    }
    else//左右子树都不空，继续迭代
    {
        //printf("4 ");
        LeaveFind(T[R].Left);
        LeaveFind(T[R].Right);
    }
}

第二种方法，符合题目要求。

参考自： https://blog.csdn.net/Authur520/article/details/84863847

#include <stdio.h>
#include <stdlib.h>

#define MaxTree 10
#define MaxSize 10
#define Tree int
#define Null -1
//树节点从上到下从左到右进入队列，依次判断是否是叶子节点。不是叶子节点，则把其子节点加入队列，否则输出。
struct TreeNode
{
    Tree Left;
    Tree Right;
} T[MaxTree];

int Flag=0;
Tree BuildTree(struct TreeNode T[]);
void LeaveFind(Tree R);
int IsLeaves(Tree R);

int main()
{
    Tree R;
    R=BuildTree(T);
    LeaveFind(R);
    return 0;
}

//树的建立
Tree BuildTree(struct TreeNode T[])
{
    int N;
    Tree Root=Null;
    int check[10];
    char cl,cr;

    scanf("%d",&N);
    if(N)
    {
        for(int i=0;i<N;i++)
        {
            check[i]=0;
        }

        for(int i=0;i<N;i++)
        {
            scanf("\n%c %c",&cl,&cr);
            if(cl!='-')
            {
                T[i].Left=cl-'0';
                check[T[i].Left]=1;
            }
            else
                T[i].Left=Null;

            if(cr!='-')
            {
                T[i].Right=cr-'0';
                check[T[i].Right]=1;
            }
            else
                T[i].Right=Null;
        }

        for(int i=0;i<N;i++)
        {
            if(!check[i])
            {
                Root=i;
                break;
            }
        }
    }
    return Root;
}

//树节点从上到下从左到右进入队列，依次判断是否是叶子节点。不是叶子节点，则把其子节点加入队列，否则输出。
//Queue[]，数组模拟队列，非真正队列
LeaveFind(Tree R)
{
    int flag=0;
    int Queue[MaxSize];
    int head=0;//队列头下标
    int rear=0;//队列尾下标
    Queue[rear++]=R;//根节点放入队列
    while(rear-head)
    {
        if(IsLeaves(Queue[head]))
        {
            if(flag)
                printf(" ");
            printf("%d",Queue[head]);
            flag=1;
        }
        else
        {
            if(T[Queue[head]].Left!=Null)
                Queue[rear++]=T[Queue[head]].Left;
            if(T[Queue[head]].Right!=Null)
                Queue[rear++]=T[Queue[head]].Right;
        }
        head++;
    }
}

//判断是否是叶子节点
int IsLeaves(Tree R)
{
    if(T[R].Left==Null && T[R].Right==Null)
        return 1;
    else
        return 0;
}

第三题代码

参考自 https://blog.csdn.net/Authur520/article/details/84865461

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MaxSize 35
#define ElementType int

typedef struct SNode *Stack;
struct SNode{
    ElementType Data;
    struct SNode *Next;
};
Stack CreateStack();
int IsEmpty(Stack S);
void Push( ElementType item, Stack S);
ElementType Pop(Stack S);
void Array_Build();
void Post_Array(int preL,int inL,int postL,int n);
void Post_Print(int N);
int pre[MaxSize],in[MaxSize],pos[MaxSize];

int main()
{
    int N;
    scanf("%d",&N);
    Array_Build(N);
    Post_Array(0,0,0,N);
    Post_Print(N);
    return 0;
}

void Array_Build(int N)
{
    char str[10];
    int j=0,k=0;
    int x;
    Stack s=CreateStack();
    for(int i=0;i<2*N;i++)
    {
        scanf("%s",str);
        if(strcmp(str,"Push")==0)
        {
            scanf("%d",&x);
            pre[j++]=x;
            Push(x,s);
        }
        else
            in[k++]=Pop(s);
    }
}
Stack CreateStack()
{ /* 构建一个堆栈的头结点，返回指针 */
    Stack S;
    S =(Stack)malloc(sizeof(struct SNode));
    S->Next = NULL;
    return S;
}

int IsEmpty(Stack S)
{ /*判断堆栈S是否为空， 若为空函数返回整数1， 否则返回0 */
    return ( S->Next == NULL );
}

void Push( ElementType item, Stack S)
{ /* 将元素item压入堆栈S */
    Stack TmpCell;
    TmpCell=(Stack)malloc(sizeof(struct SNode));
    TmpCell->Data = item;
    TmpCell->Next = S->Next;
    S->Next = TmpCell;
}

ElementType Pop(Stack S)
{ /* 删除并返回堆栈S的栈顶元素 */
    Stack FirstCell;
    ElementType TopElem;
    if( IsEmpty( S ) ) {
        printf("堆栈空");
        return NULL;
    }
    else {
        FirstCell = S->Next;
        S->Next = FirstCell->Next;
        TopElem = FirstCell ->Data;
        free(FirstCell);
        return TopElem;
    }
}

void Post_Array(int preL,int inL,int postL,int n)
{
    int i,root,Left,Right;
    if(n==0)
        return;
    if(n==1)
        pos[postL]=pre[preL];

    {
        root=pre[preL];
        pos[postL+n-1]=root;
        for(i=0;i<n;i++)
        {
            if(root==in[inL+i])
                break;
        }
        Left=i;
        Right=n-1-Left;
        Post_Array(preL+1,inL,postL,Left);//左子树后序遍历
        Post_Array(preL+1+Left,inL+Left+1,postL+Left,Right);//右子树后序遍历
    }
}

void Post_Print(int N)
{
    int first=1;
	for(int i=0; i<N; i++)
    {
		if(first)
		{
			first = 0;
			printf("%d",pos[i]);
		}
        else
        {
			printf(" %d",pos[i]);
		}
	}
}

原文链接：https://blog.csdn.net/qq_39309050/article/details/106187065

浙江大学MOOC数据结构-陈越、何钦铭 编程练习题（第三讲）

浙江大学MOOC数据结构-陈越、何钦铭编程练习题（第三讲）