1.18 learning summary

Today's topic is about binary tree . The main concern is , According to the three traversal ways of binary tree . What have I done . The preorder and mesorder are known . also Known post order and middle order . Find another of the three sorting methods .

It also makes me more profound . I feel the effect of these three arrangements Some details .

I thought the two questions should not be far apart . But in fact, there are still many differences in details .

Let's start with the known sequence and the middle sequence .

The title is as follows .

The specific idea of this topic depends on the middle order Some characteristics . To judge . The number of left and right subtrees . The way is . Input the left and right boundaries of the two sorting methods into a function . And then because In the following sequence . The root node is on the far right . Then the root node is found . Then the root node can be found in the traversal sequence The position in the middle order . In this way, the element quantities of the left and right subtrees under the root node can be obtained . And then because , This question is about the first order . So every time you find the root node . You can output it directly . Then there are two criteria . Judge by the position of the current root node in the middle order . Determine the location of the root node . Whether it is a boundary if it is not a boundary , That means there are subtrees . Take the subtree as a new tree . , respectively, hold His left and right boundaries in the middle order . And the left and right boundaries in the following order . Input into the function for recursion . In this way, we can complete the traversal .

The specific code is as follows

#include<iostream>
#include<string.h>
#include<stdio.h>
using namespace std;
char s1[50];
char s2[50];
int l;
void f(int l1,int r1,int l2,int r2)
{
    int m ;
     for(int i=0;i<l;i++)
	    {
	        if(s1[i]==s2[r2]) m=i;
	    }
    printf("%c",s2[r2]);
    if(m>l1)  {
		f(l1,m-1,l2,r2-r1+m-1); }
    if(m<r1)  {
		f(m+1,r1,l2+m-l1,r2-1); 
		}
}
int main()
{
    cin>>s1;
    cin>>s2;
    l=strlen(s1);
    f(0,l-1,0,l-1);
}

And I did another question . It is the former order and the middle order to find the latter order .

I thought that the code of the two was just a little bit of data . After all, the idea is the same . But there is one small detail .  First of all, its function return method will . Dissimilarity .   In addition, its output should be in DFS After function . That is, you recurse and then output . The purpose of this is to put the subsequent output in front of the leaf .  Then you set   The end of recursion . Is to traverse to the leaf and then output   Put it in DFS After the function, he will . Output child nodes first   Then output the root node .  So as to achieve post order traversal .

The code is as follows ,  You can observe more . Of the two DFS function   

#include<iostream>
#include<string.h>
#include<stdio.h>
using namespace std;
char a[50],b[50];
void dfs(int l1,int l2,int r1,int r2){
	int m;
    if(l1>l2||r1>r2)return;
    for(int i=l1;i<=l2;i++)if(a[i]==b[r1]){
		m=i;
	} 
        dfs(l1,m-1,r1+1,r1+m-l1); 
        dfs(m+1,l2,r1+m-l1+1,r2); 
        printf("%c",a[m]); 
   
}
int main()
{
    cin>>a>>b;
    int l= strlen(a);
    dfs(0,l-1,0,l-1); 
    return 0;
}

 

One more . About front middle , I haven't done the problem of post order traversal yet .  Wait till tomorrow , Let's make a summary . That's all for today's summary .