二叉树及指针相关问题，求指点typedef struct Node{char datastruct Node *lchild,*rchild}BTNode,*pBTNo
二叉树及指针相关问题，求指点
typedef struct Node{
char data;
struct Node *lchild,*rchild;
}BTNode,*pBTNode;
void Creat(BTNode *&pRoot) //创建二叉树
{
char c;
scanf("%c",&c);
if('#'==c)
pRoot=NULL;
else
{
pRoot=(BTNode *)malloc(sizeof(BTNode));
pRoot->data=c;
Creat(pRoot->lchild);
Creat(pRoot->rchild);
}
}
int BTNodeCount( BTNode *root ) //求二叉树中节点个数
{
int num, num1, num2;
if( root==NULL )
{
return 0;
}
else
{
num1 = BTNodeCount( root->lchild );
num2 = BTNodeCount( root->rchild );
num = num1 + num2 + 1;
return num;
}
}
int _tmain(int argc, _TCHAR* argv[])
{
BTNode *T;
int num;
Creat(T);
num=BTNodeCount(T);
printf("%d\n",num);
getchar();
getchar();
return 0;
}
我有这几个问题，求指点，本人水平很菜：
1、BTNodeCount( BTNode *root )函数怎样实现计算二叉树中节点的啊？我知道节点为空的话，返回零，但节点不为空时，num是不是应该num++，就是有一个非空节点num值加一，这样计数才对啊？这个计算节点个数的算法是什么，怎么看不懂啊？
2. 我把创建二叉树Creat(BTNode *&pRoot)函数接口改为Creat(BTNode *pRoot)，就是把引用改为指针时，发生运行错误，test.cpp(46): error C4700: 使用了未初始化的局部变量“T”，我很奇怪，T不是在Creat函数中申请动态空间了吗？为什么说没初始化呢？但加上引用，就是Creat(BTNode *&pRoot)这样这样的函数接口就成功了，这是为什么呢？
3.我把主函数main中的BTNode *T改为BTNode T，然后调函数是改为加上取地址符，即main改为：
BTNode T;
int num;
Creat(&T);
num=BTNodeCount(&T);
我感觉这也对啊，可一运行就报错，scanf输入能够执行，但执行下一步时就出错了，错误信息如下：
0x00373D7D 处的第一机会异常(在 test.exe 中): 0xC0000005: 读取位置 0xCCCCCCD0 时发生访问冲突。
0x00373D7D 处有未经处理的异常(在 test.exe 中): 0xC0000005: 读取位置 0xCCCCCCD0 时发生访问冲突。
-root0xcccccccc {data=??? lchild=??? rchild=??? }Node *
data<无法读取内存>
lchild<无法读取内存>
rchild<无法读取内存>
这是为什么啊？我感觉对啊？怎么就错了？
想了很长时间，解决不了，求大侠指点！！万分感激
[解决办法]void Creat(BTNode *&pRoot)
如果这样写，不知道LZ能否更清楚一些？
void Creat(BTNode* &pRoot)
调用者定义了 BTNode* p，然后将p的引用传入到函数
[解决办法]这个当然不行，函数定义参数规定是传递一个引用，而不是指针，编译就通不过
其次，即使你在函数体中改写成指针的逻辑，编译能过，但是你也将得不到pRoot返回值，因为函数体中，pRoot内存是函数的栈中，函数返回后，就没有了；
但你可以这样定义：
void Creat(BTNode **pRoot)
调用的时候传递地址(&)
[解决办法]1. 你说的那个是循环的计数方法，这里用的递归实现，num = num1 + num2 + 1; 中的 +1 就相当于点了当前节点。
2. c++ 默认使用值语意，Creat(BTNode*) 函数修改的是 main 中 T 的副本，因此函数内分配的值并没有反映到 T 本身上，所以后面 BTNodeCount(T); 的时候使用的并不是 Creat 中创建的值。
3. 这个只是编译过的去，逻辑上不行。&T 的时候该地址上有一个完整的对象，Creat 中对该地值强行写入一个 BTNode* 会破坏本来存在的对象的完整性，导致未定义行为。这里必须用 BTNode* 类型的变量才可以。
[解决办法]int BTNodeCount( BTNode *root ) //求二叉树中节点个数
int num, num1, num2;
if( root==NULL )
{ return 0;
}
else
{ num1 = BTNodeCount( root->lchild );//左节点数，通过调用函数本身计算下层节点
num2 = BTNodeCount( root->rchild );//右节点数，同上
num = num1 + num2 + 1;//加上本身
return num; } }
递归计算
[解决办法]
问题1:
因为是递归的, 所以需要统计左右节点和本身,所以有num = num1 + num2 + 1;
问题2:
如果Create的参数不是指针的引用,
main中 Create(T)是把指针T指向的地址传进去了. 注意,只是地址.
然后你在Create函数内部申请内存时, 把这个地址给改变了, 但是因为你传的是一个地址, 这个地址本身跟T无关,T仅仅是指向了这个地址而以. 所以Create(T)之后, T还是指向原来的地址,并未改变, 后面的操作当然就是崩溃了(因为T未初始化,是一个野指针).
这个问题说明了你对函数参数的传值与传址还没有理解清楚.
传值: 函数内部修改不会对原值内容进行改变.
传址: 函数内部修改会影响原值.
可能你认为值的指针就是传址了.
如果你对汇编有一定理解的话, 就会很明白.
如果是传值, 函数入栈的时候就是把这个变量的值压栈,如果是传址, 就是把指针压栈,但压栈的时候,本身实际也是写一个数值而以.
你传的是指针的情况下, 如果修改指针指向的内容, 那么函数外部会同步修改.
但是你传入的是指针, 但是又修改的是指针本身, 而不是其内容, 那么你这就相当于传值.
当你要修改指针本身的时候, 你可以这样理解.
比如有
void Creat(BTNode *pRoot);
可以修改成以下形式
typedef BTNode* PNODE;
void Creat(PNODE pRoot);
这时你可能就看出来了, 原来这是一个传值调用.
想要修改pRoot的值, 那么就要
void Creat(PNODE &pRoot); ====还原就是 void Creat(BTNode* &pRoot);
或者
void Creat(PNODE *pRoot); ====还原就是 void Creat(BTNode* *pRoot);
反正注意区分传址还是传值的区分不是看参数是否是指针, 而是要看你在函数内部是如何操作参数的.
如果你操作的是参数本身, 那么就是传值.
如果你是把参数当成一个地址, 操作的是那个地址上的内容,那就是传址.
如有错误, 请大家指正.
[解决办法]
参考二叉树遍历及C语言实现
[解决办法]
指针是最方便的，而不是必须的。
你可以开个比较大的数组，用于树的操作；
因为树操作一般不做节点计数，如果开小了，可能就不够用。
其实，树就是一个比链表，更复杂的表。
其实排序里的堆排序，就是把普通数组当作树来用。
堆就是一种特殊的二叉树。
另外，如果树的数据结构还是类似指针的结构，只是开数组处理，就比较像静态链表了。
据说，一个比较好的哈夫曼编码的压缩算法，就是用数组表示二叉树的。
树用指针做，最方便，最直观，最简单。
所以通常，都用指针来做。
至少节点，多半都用指针。
