二叉树的顺序存储与链式存储

来源：99网

二叉树的顺序存储

顺序存储

依据二叉树的性质，完全二叉树和满二叉树采用顺序存储比较合适，树中结点的序号可以唯一地反映结点之间的逻辑关系，这样既能最大地节省存储了空间，又能利用数组元素的下标值确定结点在二叉树中的位置，以及结点之间的关系。从数据存储来看，数组存储方式和树的存储方式可以相互转换，即数组可以转换成树，树可以转换成数组。

顺序存储二叉树的特点

下面以如图所示的满二叉树进行程序设计：

顺序二叉树的基本算法

初始化

char* create_space()
{
    char* p = (char*)malloc(N);
    if (NULL == p)
    {
        printf("p is null\n");
        return NULL;
    }

    return p;
}

int create_sqtree(char* T, int pos)
{
    char ch;
    scanf("%c", &ch);
    if (ch == '$')
        return 0;
    T[pos] = ch;  //给根节点赋值
    create_sqtree(T, pos * 2 + 1); //创建左子树
    create_sqtree(T, pos * 2 + 2);//创建右子树

    return 0;
}

根据上图的二叉树得出输入顺序应为：ABD$$E$$CF$$G$$

遍历算法：层次遍历、前序遍历、中方序遍历、后序遍历

因为本例的二叉树只有7个节点，故遍历结束条件均为大于等于7。

//层次遍历
int show_sqtree(char* T)
{
    printf("层次遍历：");
    int i;
    for (i = 0; i < 7; i++)
    {
        printf("%c ",T[i]);
    }
    printf("\n");
    return 1;
}
//前序遍历
void preOrder(char* T,int pos)
{
    if (pos >= 7)
        return;
    printf("%c ", T[pos]);
    preOrder(T,2*pos+1);
    preOrder(T, 2 * pos + 2);
}
//中序遍历
void inOrder(char* T, int pos)
{
    if (pos >= 7)
        return;
    inOrder(T, 2 * pos + 1);
    printf("%c ", T[pos]);
    inOrder(T, 2 * pos + 2);
}
//后续遍历
void postOrder(char* T, int pos)
{
    if (pos >= 7)
        return;
    postOrder(T, 2 * pos + 1);
    postOrder(T, 2 * pos + 2);
    printf("%c ", T[pos]);
}

下面是遍历结果：

int main(int argc, char* argv[])
{

    char* T = create_space();

    create_sqtree(T, 0);
    show_sqtree(T);
    printf("先序遍历：");
    preOrder(T,0);
    printf("\n");
    printf("中序遍历：");
    inOrder(T,0);
    printf("\n");
    printf("后序遍历：");
    postOrder(T,0);
    printf("\n");
    return 0;
}

输入：ABD$$E$$CF$$G$$
层次遍历：A B C D E F G
先序遍历：A B D E C F G
中序遍历：D B E A F C G
后序遍历：D E B F G C A

二叉树的链式存储

链式结构的设计思想

因为并不是每个二叉树都是，普通二叉树使用顺序表存储或多或少会存在空间浪费的现象。如下图所示，未使用的节点被置为0。

如上图，普通二叉树里只有三个元素，最好的存储方式当然是开辟相对应的空间，但是却无法实现这样的效果，也就是说我们此时必须花更多的空间去存储相对少的元素。

因此引入了链式存储结构：

如上图所示，若将其采用链式存储，则只需从树的根节点开始，将各个节点及其左右孩子使用存储，因此，上图对应的链式如下图所示：

采用链式存储二叉树时，其节点结构由 3 部分构成：

因此节点的定义如下：

typedef struct tree
{
	char data;
	struct tree* l;
	struct tree* r;
}*lpt;

链式二叉树的初始化

如上图所示的树，初始化时输入顺序为：AB$D$$CE$$FG$$$

lkt linktree_init()
{
	char ch;
	scanf("%c", &ch);
    if (ch== '$')
        return NULL;
    //创建根节点
    lkt R = malloc(sizeof(struct tree));
    if (NULL == R)
    {
        printf("malloc is default\n");
        return NULL;
    }
    R->c = ch;
    //创建左孩子
    R->l = linktree_init();
    //创建右孩子
    R->r = linktree_init();

    return R;
}

遍历算法：先序遍历、中序遍历、后序遍历、层次遍历

//先序
int Porder_linktree(lkt R)
{
    if (NULL == R)
        return 0;
    printf("%c ", R->c);
    Porder_linktree(R->l);
    Porder_linktree(R->r);
}
//中序
int Iorder_linktree(lkt R)
{
    if (NULL == R)
        return 0;
    Iorder_linktree(R->l);
    printf("%c ", R->c);
    Iorder_linktree(R->r);
}
//后序
int Lorder_linktree(lkt R)
{
    if (NULL == R)
        return 0;
   
    Lorder_linktree(R->l);
    Lorder_linktree(R->r);
    printf("%c ", R->c);
}

这里着重讲一下层次遍历的实现，层次遍历利用了队列来实现，算法步骤为：

1、根节点入队

2、进入循环，循环结束条件为队列为空

3、根节点出队，访问，分别判断其有没有左右孩子，有就入队，重复循环。

//层次
void leve_order(lkt R)
{
    //根节点入队
    LQ Q= linkQueue_init();
    push_linkQueue(Q, R);

    //循环当队列不为空
    while (!empty_linkQueue(Q))
    {
        //出队，访问
        lkt temp = pop_linkQueue(Q);
        printf("%c  ", temp->c);
        //判断有没有左右孩子，有就入队
        if (temp->l)
        {
            push_linkQueue(Q, temp->l);
           // printf("入队成功！\n");
        }
        if (temp->r)
        {
            push_linkQueue(Q, temp->r);
            //printf("入队成功！\n");
        }
    }
    printf("\n");
}

遍历结果

因篇幅问题不能全部显示，请点此查看更多更全内容

查看全文

全部频道

二叉树的顺序存储与链式存储