二叉查找树

关于传参的两种方式 传值与传址 的深入理解 (附 hdu3999

真的真的真的真的好久没码了………………

最近因为要复习数据结构所以才兴起想要码一些跟考试相关的

于是找了一下 BST 和 AVL 的题做做 结果一下搜就找到了 hdu3999

解法很简单 只要建立一个 BST 再对其先序遍历即可
然而…………

问题出在这个代码上

int main()
{
    int tmp;
    while(scanf("%d",&n)!=EOF)
    {
        root=NULL;
        for(int i=0; i<n; i++)
        {
            scanf("%d",&tmp);
            InsertNode(root,tmp);
            if(root==NULL)
                cout<<1111<<endl;
        }
        FirstOrderSearch(root);
        puts("");
    }
    return 0;
}

插入函数如下

void InsertNode(node* now,int value)
{
    if(now==NULL)
    {
        now = new node;
        now -> value = value;
        return ;
    }
    else if(value < now -> value)
        InsertNode(now->left,value);
    else if(value > now -> value)
        InsertNode(now -> right, value);
}

咋看下真的没什么问题 然而实际上还是会输出n个 1111
这就说明 root 它一直都没有变化

“纳尼不是只要传地址 , 那么这个变量就一定会随之改变的不是么。。。”

想了一下才想通 传参在本质上来说完全只有一种方法 就是传值

传址传址 也只是把指针这个变量的值 给传了过去 而如果我们对这个地址取值那么自然而然的就可以改变这个变量的值

以这里的代码为例 我在主函数中的 root变量初始化为 NULL 传给 InsertNode 变量now拥有了 NULL 但是在这里now的所有变化将根本不会影响到main中的root

换言之 对于指针的传参 只有 *指针(指针所指的值)才会能在全局变化

所以如果要继续我以上的写法 解法有二:

  1. 只要将这个root 这个指针的地址传给函数处理即可
  2. 当然 我也可以在最开始的时候就先把根节点给定义了 再对根节点传参也可

综上

传参在本质上只有将实参的值传给形参 而所谓的传址 我们只能理解成一个小技巧 否则会带来很多习惯性误导

AC Code

法 1 :(因为第一次这么写 运算符的等级忘了 所以保险点就都加了括号…………)

#include <iostream>
#include <cstdio>
#include <queue>
#include <algorithm>
#include <cstring>
#include <cmath>

using namespace std;
int n;

struct node
{
    int value;
    node *left;
    node *right;
    node():left(NULL),right(NULL) {}
};

void InsertNode(node** now,int value)
{
    if(*now==NULL)
    {
        *now=new node;
        (*now)->value=value;
        return ;
    }
    if(value < (*now) -> value)
        InsertNode(&((*now)->left),value);
    else if(value > (*now) -> value)
        InsertNode(&((*now) -> right), value);
}

void FirstOrderSearch(node* now,node* root)
{
    if(now==root)
        printf("%d",now->value);
    else printf(" %d",now->value);
    if(now->left)
        FirstOrderSearch(now->left,root);
    if(now->right)
        FirstOrderSearch(now->right,root);
    delete now;
}

int main()
{
    int tmp;
    while(scanf("%d",&n)!=EOF)
    {
        node* root=NULL;
        for(int i=0; i<n; i++)
        {
            scanf("%d",&tmp);
            InsertNode(&root,tmp);
        }
        FirstOrderSearch(root,root);
        puts("");
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注