c - 类有序访问二叉树上的线性算法

Question

我必须用 C 语言编写一个算法，将二叉搜索树作为输入。练习将从子树的根开始并尽可能向左走的访问定义为“左访问”。同样，它定义了“正确的访问”。练习要求打印左访问严格大于右访问的三个键。它还要求按升序打印此 key ，并且该算法必须在线性时间内运行，因此我必须实现一个类似按顺序访问的算法。现在，我已经编写了一个在线性时间内工作的算法，但在某些情况下它不能按顺序访问工作，因此打印的 key 不是按升序排列的，但我不知道如何管理超越这个障碍。如果不首先在左侧和右侧实现递归，我如何比较左侧访问和右侧访问？

#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.

由于我们可以很容易地使用中序遍历以自下而上的方式追踪这条路径，我们将使用它来计算 left_visit 和 right_visit 的值。

主要思想

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

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

之所以可行，是因为当对节点左子节点的中序遍历的递归调用完成时，它的左子节点将计算其 left_visit 而我们所要做的就是加 1 来计算当前节点的 left_visit 值和相同的逻辑适用于右访问。

时间复杂度为 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*/   
}