【MOOC-浙大数据结构】第三周的编程作业——建树，树的遍历

小鱼儿 2021-11-29 23:40 254阅读 0赞

**第三周的编程作业：**

**1.[树的同构][Link 1]**

小白专场里讲解了找根节点的方法——没有一个指向他的结点，check一下~

#include<stdio.h>
    struct TreeNode
    {
    	char c;
    	int left,right;
    }t1[15],t2[15];
    int BuildTree(struct TreeNode t[])
    {
    	int check[15]={0};
    	int n,i,root=-1;
    	char cl,cr;
    	scanf("%d",&n);
    	for(i=0;i<n;i++)
    	{
    		getchar();
    		scanf("%c %c %c",&t[i].c,&cl,&cr);
    		if(cl!='-')
    		{
    			t[i].left=cl-'0';
    			check[t[i].left]=1;
    		}
    		else t[i].left=-1;
    		if(cr!='-')
    		{
    			t[i].right=cr-'0';
    			check[t[i].right]=1;
    		}
    		else t[i].right=-1;
    	}
    	for(i=0;i<n;i++)
    	{
    		if(check[i]==0)
    		{
    			root=i;
    			break;
    		}
    	}
    	return root;
    }
    int Isomorphic(int r1,int r2)
    {
    	if(r1==-1&&r2==-1)
    	return 1;//均为空树 
    	if(r1==-1||r2==-1)
    	return 0;//一空一不空 
    	if(t1[r1].c!=t2[r2].c)
    	return 0;//数据不同 
    	
    	if((t1[r1].left!=-1)&&(t2[r2].left!=-1)&&(t1[t1[r1].left].c==t2[t2[r2].left].c))
        return (Isomorphic(t1[r1].left,t2[r2].left)&&Isomorphic(t1[r1].right,t2[r2].right));
    	else //左右交换 
        return (Isomorphic(t1[r1].left,t2[r2].right)&&Isomorphic(t1[r1].right,t2[r2].left));
    }
    int main()
    {
    	int r1,r2;
    	r1=BuildTree(t1);
    	r2=BuildTree(t2);
    	if(Isomorphic(r1,r2))
    	printf("Yes\n");
    	else
    	printf("No\n");
    }

2.**[List Leaves][]**

树的构建和存储同上一题，然后用广搜模拟层次遍历，从上到下从左到右输出叶子结点。

PS:如果只要求从左到右的话，用深搜。

#include<stdio.h>
    #include<queue>
    #include<algorithm>
    #include<iostream>
    using namespace std;
    struct TreeNode
    {
    	int c;
    	int left,right;
    }tree[15];
    int BuildTree(struct TreeNode t[])
    {
    	int check[15]={0};
    	int n,i,root=-1;
    	char cl,cr;
    	scanf("%d",&n);
    	for(i=0;i<n;i++)
    	{
    		getchar();
    		t[i].c=i; 
    		scanf("%c %c",&cl,&cr);
    		if(cl!='-')
    		{
    			t[i].left=cl-'0';
    			check[t[i].left]=1;
    		}
    		else t[i].left=-1;
    		if(cr!='-')
    		{
    			t[i].right=cr-'0';
    			check[t[i].right]=1;
    		}
    		else t[i].right=-1;
    	}
    	for(i=0;i<n;i++)
    	{
    		if(check[i]==0)
    		{
    			root=i;
    			break;
    		}
    	}
    	return root;
    }
    int main()
    {
    	int root;
    	int k;//flag-空格
    	root=BuildTree(tree);
    	k=0; 
    	queue<TreeNode> q;
    	q.push(tree[root]);
    	while(!q.empty())
    	{
    		TreeNode cur=q.front();
    		q.pop();
    		if(cur.left!=-1)
    		q.push(tree[cur.left]);
    		if(cur.right!=-1)
    		q.push(tree[cur.right]);
    		if(cur.left==-1&&cur.right==-1)
    		{
    			if(k)printf(" ");
    			printf("%d",cur.c);
    			k++;
    		}		
    	}
    	printf("\n");
    }

3.**[Tree Traversals Again][]**

方法一：观察可知这道题实际上是已知前序中序遍历，求后序遍历。（push的数为前序序列，pop的数为中序序列）

#include<stdio.h>
    #include<string>
    #include<stack>
    #include<vector>
    #include<algorithm>
    #include<iostream>
    using namespace std;
    vector<int> pre,in,post;
    stack<int> st;
    void post_travel(int root,int start,int end)
    {
        if(start>end) return;
        int i=start;
        while(i<=end&&pre[root]!=in[i]) i++;
        post_travel(root+1,start,i-1);
        post_travel(root+1+i-start,i+1,end);
        post.push_back(pre[root]);
    }
    int main()
    {
        int n,i,x;
        string s;
        scanf("%d",&n);
        for(i=0;i<n*2;i++)
        {
            cin>>s;
            if(s=="Push")
            {
                scanf("%d",&x);
                pre.push_back(x);
                st.push(x);
            }
            else if(!st.empty())
            {
                in.push_back(st.top());
                st.pop();
            }
        }
        post_travel(0,0,n-1);
        for(i=0;i<n;i++)
        {
            if(i) printf(" ");
            printf("%d",post[i]);
        }
        printf("\n");
    }

方法二：参考来自：[https://www.cnblogs.com/clevercong/p/4177802.html][https_www.cnblogs.com_clevercong_p_4177802.html]

**题目分析：**借助“栈”进行树的后续遍历。栈工作记录中必须注明刚才是在左子树还是在右子树中。

每次push，times = 1；

每次pop检查栈顶记录的times：如果是1，弹出来变成2压回栈；

如果是2，则弹出，放入存放结果的vector中，重复这一过程，直到栈顶times为1。

所有push与pop操作执行完毕时，输出vector内的数据和stack中的数据即可。

#include<stdio.h>
    #include<string>
    #include<stack>
    #include<vector>
    #include<algorithm>
    #include<iostream>
    using namespace std;
    struct node
    {
        int data;
        int times;
    }Node;
    int main()
    {
        int n,x,i;
        string cmd; 
        stack<node> st; 
        vector<int> vec; 
        scanf("%d",&n);
        for(i=0;i<2*n;i++)
        {
            cin>>cmd;
            if(cmd=="Push")
            {
                scanf("%d",&x);
                Node.data=x;
                Node.times=1;
                st.push(Node);
            }
            if(cmd=="Pop")
            {
                Node=st.top();
                st.pop();
                if(Node.times==1)  
                {
                    Node.times=2;
                    st.push(Node);
                }
                else if(Node.times==2)  
                {
                    vec.push_back(Node.data);
                    while(st.top().times==2)  
                    {
                        vec.push_back(st.top().data);
                        st.pop();
                    }
                    if(st.size()!=0) 
                    st.top().times=2;                    
                }
            }
        }
        for(i=0;i<vec.size();i++)
        printf("%d ",vec[i]);
        while(st.size()!=0)  
        {
            printf("%d",st.top().data);
            st.pop();
            if(st.size()!=0)
            printf(" ");
        }
        printf("\n");
    }

[Link 1]: https://pintia.cn/problem-sets/1134360184290500608/problems/1141327288327692288
[List Leaves]: https://pintia.cn/problem-sets/1134360184290500608/problems/1141327288327692289
[Tree Traversals Again]: https://pintia.cn/problem-sets/1134360184290500608/problems/1141327288327692290
[https_www.cnblogs.com_clevercong_p_4177802.html]: https://www.cnblogs.com/clevercong/p/4177802.html