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

Question

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

#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

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

诀窍是以 BOTTOM-UP 方式计算左访问和右访问值，以便我们可以执行以下操作:

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，我们已经到达底部，所以这就是我们使用上面指定的规则开始计算值的地方。

之所以可行，是因为当对节点左 child 的中序遍历的递归调用完成时，其左 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*/   
}

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

linear algorithm on a binary three in-order-visit-like

c

algorithm

binary-search-tree