欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

树的插入(创建)为什么要使用指针的指针

程序员文章站 2022-03-12 10:13:06
一个二叉排序树的例子 首先看一个常见的二叉排序树的操作,下面的代码包括插入、创建和中序遍历。摘自 "这里" 。 我一直很纳闷为什么插入(创建)操作需要传递指针的指针,不是指针就可以操作被指向的内容吗?为解决这个疑惑,首先看一下C语言的函数传参。 C语言函数传参 一个经典的例子就是交换两个数的值, , ......

一个二叉排序树的例子

首先看一个常见的二叉排序树的操作,下面的代码包括插入、创建和中序遍历。摘自。

#include<stdio.h>
#include<stdlib.h>

typedef int elemtype;
struct btreenode
{
    elemtype data;
    struct btreenode* left;
    struct btreenode* right;
};

//递归方式插入
void insert(struct btreenode** bst, elemtype x)
{
    if (*bst == null) //在为空指针的位置链接新结点
    {
        struct btreenode* p = (btreenode*)malloc(sizeof(struct btreenode));
        p->data = x;
        p->left = p->right = null;
        *bst = p;
    }
    else if (x < (*bst)->data) //向左子树中完成插入运算
        insert(&((*bst)->left), x);
    else
        insert(&((*bst)->right), x); //向右子树中完成插入运算
}

//创建二叉搜索树,根据二叉搜索树的插入算法可以很容易实现
void createbstree(struct btreenode** bst, elemtype a[], int n)
{
    int i;
    *bst = null;
    for (i = 0; i < n; i++)
        insert(bst, a[i]);
}

void inorder_int(struct btreenode* bt)//中序遍历,元素类型为int
{
    if (bt != null)
    {
        inorder_int(bt->left);
        printf("%d,", bt->data);
        inorder_int(bt->right);
    }
}

//主函数
void main()
{
    int x, *px;
    elemtype a[10] = { 30,50,20,40,25,70,54,23,80,92 };
    struct btreenode* bst = null;
    createbstree(&bst, a, 10); //利用数组a建立一棵树根指针为bst的二叉搜索树

    printf("进行相应操作后的中序遍历为:\n");
    inorder_int(bst);
    printf("\n");

    printf("输入待插入元素值:");
    scanf(" %d", &x);
    insert(&bst, x);

    printf("进行相应操作后的中序遍历为:\n");
    inorder_int(bst);
    printf("\n");
}

我一直很纳闷为什么插入(创建)操作需要传递指针的指针,不是指针就可以操作被指向的内容吗?为解决这个疑惑,首先看一下c语言的函数传参。

c语言函数传参

一个经典的例子就是交换两个数的值,swap(int a,int b),大家都知道这样做a和b的值不会被交换,需要swap(int *a,int *b)。从函数调用的形式看,传参分为传值和传指针两种(c++中还有传引用)。实际上在c语言中,值传递是唯一可用的参数传递机制,函数参数压栈的是参数的副本。传指针时压栈的是指针变量的副本,但当你对指针解指针操作时,其值是指向原来的那个变量,所以可以对原来变量操作。

分析

再看一下前面的二叉树插入的例子。

btreenode *root=null; // step 1
insert(&root,x);      // step 2

void insert(struct btreenode** bst, elemtype x)
{
    if (*bst == null) 
    {
        struct btreenode* p = (btreenode*)malloc(sizeof(struct btreenode));   // step  3
        p->data = x;
        p->left = p->right = null;
        *bst = p;     // step  4
    }

    ...

}

函数递归调用,每次真正产生变化的时候传递进去的都是空指针。当树根为空时,我们图解看一下函数调用的值拷贝。

树的插入(创建)为什么要使用指针的指针

  • step 1 定义一个空指针root,&root为指针root的地址,图中的箭头表示指针的指向。

  • step 2 调用insert,产生一个&root的拷贝bst,即bst指向root。

  • step 3 生成一个新的节点为node,由指针p指向node。

  • step 4 (*bst)=p,也就是root的值为p(node的地址),于是root指向了新生成的节点。

如果我们把函数与调用改成一级指针,看下面的代码:

btreenode *root=null; // step 1
insert(root,x);      // step 2

void insert(struct btreenode* bst, elemtype x)
{
    if (bst == null) 
    {
        struct btreenode* p = (btreenode*)malloc(sizeof(struct btreenode));   // step  3
        p->data = x;
        p->left = p->right = null;
        bst = p;     // step  4
    }

    ...

}

再图解一下调用过程。

树的插入(创建)为什么要使用指针的指针

  • step 1 定义一个空指针root。

  • step 2 调用insert,产生一个root的拷贝bst,bst与root的值一样都为空,所以都没有指向。

  • step 3 生成一个新的节点为node,由指针p指向node。

  • step 4 bst=p,也就是bst的值为p(node的地址),于是bst指向了新生成的节点。

执行结束后我们得到了一个根节点但是root并没有指向这个节点。

那么能不能通过一级的指针就得到正确结果呢?答案是可以,看两个图的区别,其实就是root最后要指向node,即root=bst。所以只需要给函数加一个返回值,就可以通过一级指针得到同样的结果,看下面的代码:

//调用
root = insert_1(root,x);

//递归一级指针
btreenode* insert_1(struct btreenode* bst, elemtype x)
{
    if (bst == null) 
    {
        struct btreenode* p = (btreenode*)malloc(sizeof(struct btreenode));
        p->data = x;
        p->left = p->right = null;
        bst = p;
    }
    else if (x < bst->data) //向左子树中完成插入运算
        bst->left = insert_1(bst->left, x);
    else
        bst->right = insert_1(bst->right, x); //向右子树中完成插入运算
    return bst;
}

结果正确:

树的插入(创建)为什么要使用指针的指针

但是从语义上看,一级指针的写法没有二级指针那么直观,遇到需要对树进行修改的操作时还是用二级指针更好一点。

原文地址