插入部分有序树

Question

我试图在偏序树中插入一个元素，但是当我试图显示作为数组实现的树时，它不会显示元素。

这是堆结构。我只是暂时把它简化了。

typedef struct{
    int Elem[SIZE];
    int last;
}Heap;

这是我为插入内容所做的。

void insertHeap(Heap *HH, int given)
{
    int parent, child, temp;

    if(HH->last < SIZE){
        HH->Elem[HH->last] = given;
        parent = (HH->last - 1) / 2;
        for(child = HH->last ; child >= 0 && HH->Elem[child] <= HH->Elem[parent] ;  child = parent, parent = parent - 1 / 2 ){
            temp = HH->Elem[parent];
            HH->Elem[parent] = HH->Elem[child];
            HH->Elem[child] = temp;
        }
        HH->last++;
    }
}

Answer 1

我刚刚更改了 for 循环的第一个条件语句 child > 0

Answer 2

您的代码进入无限循环。你应该解决两件事：

在for循环控制的更新部分计算新父代时，(parent - 1)两边应该有括号；
您的条件 parent >= 0 将始终为真，因为即使对于 parent == 0，(parent - 1) / 2 也会得出 0，因为根据 C 的整数除法规则 -1 / 2 为零。

所以：

void insertHeap(Heap *HH, int given)
{
    int parent, child, temp;

    if(HH->last < SIZE){
        HH->Elem[HH->last] = given;
        parent = (HH->last - 1) / 2;
        for (child = HH->last; 
             child > 0 && HH->Elem[child] <= HH->Elem[parent];
             child = parent, parent = (parent - 1) / 2)
        {
            temp = HH->Elem[parent];
            HH->Elem[parent] = HH->Elem[child];
            HH->Elem[child] = temp;
        }
        HH->last++;
    }
}

三个长段的for循环看起来有点笨拙。您还可以将变量声明移到更靠近需要变量的地方并立即初始化它们。下面的代码做同样的事情，但在我看来更具可读性，但这当然是个人风格的问题。

void insertHeap(Heap *HH, int given)
{    
    if(HH->last < SIZE){        
        int parent = (HH->last - 1) / 2;
        int child = HH->last;

        HH->Elem[HH->last] = given;

        while (child > 0 && HH->Elem[child] <= HH->Elem[parent]) {
            int temp = HH->Elem[parent];

            HH->Elem[parent] = HH->Elem[child];
            HH->Elem[child] = temp;

            child = parent;
            parent = (parent - 1) / 2;
        }

        HH->last++;
    }
}

插入部分有序树

Inserting in a Partially Ordered Tree

c

arrays

tree