请求帮助，实现用数组形式存储二叉树！！！

。。

dps521

....过来瞧瞧哦。

jessica1

dps521 发表于 2015-11-19 11:19
....过来瞧瞧哦。

呵呵，谢谢哈，如果有实现代码就更好了

jessica1

jessica1 发表于 2015-11-19 11:22
呵呵，谢谢哈，如果有实现代码就更好了

dps521 发表于 2015-11-19 11:19
....过来瞧瞧哦。

呵呵，谢谢哈，如果有实现代码就更好了

dps521

过来看看  一起学习一起研究一下:smile:smile:smile:smile

ExiaGN001

如果二叉树的最大层次是n，那就开辟一个2^N大小的数组
约定
a[i]的子节点是a[2*i]和a[2*i+1]
a[i]的父节点是a[i/2]

小碎流星

我把我的哈夫曼编码建树的代码放下面你看一下大概就可以理解了~

typedef struct
{    char ch;
    int weight;
    int parent,lchild,rchild;
}HTNode,*HuffmanTree;
void CreatHuffmanTree(HuffmanTree & HT, int n)
{
        HT = (HuffmanTree)malloc(sizeof(HTNode) * (2*n+2));
        for (int i = 1; i <= n; i++)
    {
        cin >> (HT + i)->ch >> (HT + i)->weight;
        (HT + i)->parent = 0;
    }
    int i, j = 0, m1, n1, p;
    HuffmanTree s1=NULL, s2=NULL, P=NULL;
    while (j < n - 1)
    {
        int x = 0;
        for (i = 1; i <= n + j; i++)
        {
            if ((HT+i)->parent == 0)
            
            {
                if (x == 1)
                {
                    s2 = (HT+i);
                    n1 = i;
                    break;
                }
                if (x == 0)
                {
                    s1 = (HT + i),
                    x++;
                        m1 = i;
                }
            }
        }
        if (s2->weight < s1->weight)
        {
            P = s2, p = n1;
            s2 = s1, n1 = m1;
            s1 = P, m1 = p;
        }
        i++;
        for (i; i <= n + j; i++)   
        {
            if (HT[i].parent == 0)
            {
               if (HT[i].weight < s2->weight)
                   s2 = (HT + i), n1 = i;
               
               if (s2->weight < s1->weight)
               {
                   P = s2, p = n1;
                   s2 = s1, n1 = m1;
                   s1 = P, m1 = p;
               }
            }
        }

        HT[n + j+1].weight = HT[m1].weight + HT[n1].weight;
        HT[n + j+1].lchild = m1;
        HT[n + j+1].rchild = n1;
        HT[n + j+1].parent = 0;
        HT[m1].parent = HT[n1].parent = n + j+1;
        j++;
    }
}

小碎流星

小碎流星 发表于 2022-7-4 12:37
我把我的哈夫曼编码建树的代码放下面你看一下大概就可以理解了~

typedef struct

需要注释版的可以留言跟我说

ExiaGN001

有两种形式：
1.二维数组（宽度为三）存储，每行对应一个节点，三个数分别是左儿子下标，数据，右儿子下标
2.一维数组存储，每个元素对应一个节点
若该节点编号是n，则其父节点为n/2(向下取整)，子节点是2*n和2*n+1，数据是a[n]的值

ExiaGN001

小碎流星 发表于 2022-7-4 12:37
我把我的哈夫曼编码建树的代码放下面你看一下大概就可以理解了~

typedef struct

审题啊
他问的是数组存二叉树
不是指针节点存哈夫曼树