二元三阶访问类的线性算法

Question

我必须用C写一个算法，接受输入二叉查找树。该练习将从子树根开始并尽可能长时间向左的访问定义为“向左访问”。同样，它定义了“正确的访问”。该练习要求打印三个键，其中左访问严格大于右访问。它还要求按升序打印这个密钥，算法必须在线性时间内工作，所以我必须实现一个类似于按顺序访问的算法。现在，我已经写了一个算法，可以在线性时间内工作，但在某些情况下，它不能按顺序访问，所以打印的密钥不是按升序排列的，但我不知道如何克服这个障碍。如果不首先在左边和右边实现递归，我如何比较左边和右边的访问呢？

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


typedef struct _node {
        int dato;
    struct _node *left;
        struct _node *right;
}node;


typedef struct _ret {
        int sin;
        int des;
        }res;


node *inserisci(node *root, int insert)
{
 if(root==NULL) {
        node * new=(node*)malloc(sizeof(node));
        new->left=NULL;
        new->right=NULL;
        new->dato=insert;
        return new;
}
 if(root->dato < insert) root->right =inserisci(root->right,insert);
 else root->left = inserisci(root->left,insert);
 return root;
}


res somma(node * u)
{
res ret; res ciao_sx; res ciao_dx;

if(u==NULL) return;

if(u->left==NULL && u->right==NULL)
        {
        ret.sin=0;
        ret.des=0;
        return ret;
        }

if(u->left!=NULL && u->right!=NULL)
        {
        ciao_sx=somma(u->left);
        ret.sin= ciao_sx.sin+1;
        ciao_dx=somma(u->right);
        ret.des= ciao_dx.des+1;

        if(ret.sin > ret.des )
                {
                printf("%d\n",u->dato);
                }
        return ret;
        }

if(u->left!=NULL && u->right==NULL)
        {
        ciao_sx=somma(u->left);
        ret.sin= ciao_sx.sin+1;
        ret.des= 0;
        printf("%d\n",u->dato);

        return ret;
        }

if(u->left==NULL && u->right !=NULL)
        {
        ciao_dx=somma(u->right);
        ret.des= ciao_dx.des +1;
        ret.sin=0;
        return ret;

        }
}





int main()
{
int n,i,x;
scanf("%d",&n);
node *root=NULL;
for(i=0;i<n;i++) {
        scanf("%d",&x);
        root=inserisci(root,x);
}

somma(root);

return 0;
}

Answer 1

这个问题可以在线性时间内解决。

诀窍是以底部向上的方式计算左访问和右访问值，以便我们可以执行以下操作：

left_visit of node = left_visit of its left child + 1

和

right_visit of node = right_visit of its right child + 1

条件是:

if(node is null)
 left_vist is 0 as well as right_visit is also 0.

由于我们可以很容易地使用inorder遍历以自下而上的方式跟踪此路径，因此我们将使用它计算left_visit和right_visit的值。

主要理念

我们知道我们可以很容易地编写递归无序遍历。

我们知道，当我们遇到一个没有左子节点的节点时，我们已经到达了底部，所以这是我们开始使用上面指定的规则计算值的地方。

这样做的原因是，当对一个节点的左子节点的顺序遍历的递归调用完成时，它的左子节点将计算它的left_visit，我们所要做的就是加1来计算当前节点的left_visit值，同样的逻辑也适用于right vist。

时间复杂度是O(N)，这是线性的，因为顺序遍历是在线性时间内完成的。

使用上面的算法，这里是C代码：

#include <stdio.h>
#include <stdlib.h>
typedef struct tree tree;
struct tree{
   int value;
   tree *left;
   tree *right;       
   int lv;
   int rv;
};
tree *insert(tree *ptr,int x)
{
    if(ptr==NULL)
    {
        ptr=(tree *)malloc(sizeof(tree));
        ptr->left=NULL;
        ptr->right=NULL;
        ptr->value=x;            
        return ptr;
    }
    else if(ptr->value>x)
        {ptr->left=insert(ptr->left,x);return ptr;}
    else { ptr->right=insert(ptr->right,x);return ptr;}
}
void compute_values(tree *ptr)
{
    if(ptr==NULL)
    return;
    compute_values(ptr->left);
    if(ptr->left==NULL)
     ptr->lv=0;
    else ptr->lv=ptr->left->lv+1;    
    compute_values(ptr->right);
    if(ptr->right==NULL)
     ptr->rv=0;
    else ptr->rv=ptr->right->rv+1;   
}
void iot(tree *ptr)
{
    if(ptr==NULL)
     return;
    iot(ptr->left);  
      if(ptr->lv > ptr->rv)
       printf("%d ",ptr->value);
    iot(ptr->right);
}
int main()
{
    tree *root=NULL;
    int i;
    /*insert 6  elements*/        
     root=insert(root,4);
     root=insert(root,5);
     root=insert(root,3);
     root=insert(root,1);
     root=insert(root,2);
     root=insert(root,0);
     root=insert(root,6);
     compute_values(root);/*compute the left and right visit.*/
     printf("the nodes which have left visit strictly > than right visit\n");
     iot(root);/*inorder traversal*/   
}