二叉树创建时有些疑问和不解的问题想向各位前辈请教。。。。
问题 1 :
        用递归的方法创建的函数createtree1(Bitree * tr);来运行程序时，程序没有问题。但用嵌套字符创建二叉树函数createtree2(Bitree  * tr,char str[]);运行时会显示说  “0x0041009d”指令引用的“0x00000000”内存不能为 read .

问题 2 ：
        createtree1(Bitree * tr)函数要用二级指针，有一点弄明白了。递归调用函数时传递的是形参的地址，而形参本身就是地址，所以要用地址的地址。就是二级指针要不就改变不了形参的内容。因为要想改变参数的内容只有传递地址。（不知道这么说是对还是错！）但为什么用createtree2(Bitree  * tr,char str[])时也要用二级指针，我把 * tr 改为 tr 程序就报错。createtree2(Bitree  * tr,char str[])并没有像上面createtree1(Bitree * tr)那样重复调用函数自身啊，所以只用二叉树自身地址不就行了吗。为什么还要用二级指针呢？

请各位多指教。帮我排难解惑。。。谢谢！！！



#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
#include<conio.h>
#define maxsize 50
typedef char typedate ;


typedef struct node
{
    typedate treedate;
    struct node * lchild;
    struct node * rchild;
} * Bitree ,  Bitnode;

void inittree(Bitree * tr);//初始化二叉树

void createtree1(Bitree * tr);//创建二叉树,通过递归和输入字符的方法。数据域为空时要用 # 号代替。

void createtree2(Bitree  * tr,char str[]);//创建二叉树，通过非递归的办法，用广义表输入创建二叉树。

void showtree1(Bitree tr);//二叉树的先序遍历,递归算法。

void showtree2(Bitree tr);//二叉树的先序遍历，非递归算法。

void showtree3(Bitree tr);//二叉树的中序遍历，递归算法。

void showtree4(Bitree tr);//二叉树的中序遍历，非递归算法。

void showtree5(Bitree tr);//二叉树的后序遍历，递归算法。

void showtree6(Bitree tr);//二叉树的后序遍历，非递归算法。

void showtree7(Bitree tr);//二叉树的层次遍历。

void printtree(Bitree tr,int level);//二叉树的树状输出。

int leafnum(Bitree tr);//输出二叉树叶子节点个数。

int notleafnum(Bitree tr);//输出二叉树非叶子结点个数。

int Bitreedepth(Bitree tr);//输出二叉树深度。


int main(void)
{
    Bitree tr;
    inittree(&tr);
    printf("请输入创建二叉树的字符: \n");
//    createtree1(&tr);//递归创建二叉树
    createtree2(&tr,"(a(b(c,d),e(f(,g),h(i)))");//广义表字符串创建二叉树
    printf("\n二叉树先序遍历算法: \n");
    printf("  递归算法 :   ");
    showtree1(tr);
    printf("\n非递归算法 :   ");
    showtree2(tr);
    printf("\n二叉树中序遍历算法: \n");
    printf("  递归算法 :   ");
    showtree3(tr);
    printf("\n非递归算法 :   ");
    showtree4(tr);
    printf("\n\n二叉树后序遍历算法: \n");
    printf("  递归算法 :   ");
    showtree5(tr);
    printf("\n非递归算法 :   ");
    showtree6(tr);
    printf("\n\n二叉树的层次遍历: \n");
    showtree7(tr);
    printf("\n\n二叉树的树状输出: \n");
    printtree(tr,0);
    printf("\n\n二叉树叶子节点个数:  %d  \n", leafnum(tr) );
    printf("\n\n二叉树非叶子结点个数:  %d \n",notleafnum(tr) );
    printf("\n\n二叉树深度:  %d \n",Bitreedepth(tr) );
   
    printf("\n");
    getch();
    return 0;
}

void inittree(Bitree * tr)//初始化二叉树
{
    tr = NULL;
}

void createtree1(Bitree * tr)//创建二叉树,通过递归和输入字符的方法。
{
    typedate ch;
    //    printf("请输入创建二叉树的字符: \n");
    scanf(" %c ",&ch);
    //    printf(" %c @\n",ch);
    if(ch == '#')//如果是#号则表示是空。
    {
        *tr = NULL;
        //        printf(".........!\n");
    }
    else
    {
        (*tr) = (Bitree)malloc(sizeof(Bitnode));
        if(!tr)
            exit(-1);
        (*tr)->treedate = ch;//如果非空，则将字符赋值给二叉树结点的数据域。
        //        printf("....%c\n",tr->treedate);
        createtree1(&((*tr)->lchild));//接着创建二叉树的左子树和右子树。
        createtree1(&((*tr)->rchild));//如果只是传递形参 (*tr)->rchild 那么函数结束时函数创建的内容也就会消失，要想改变传递的内容只有传递形参的地址，而这里形参本来就是地址，所以只能传递地址的地址 &((*tr)->rchild) 。即二级指针
    }
}

void createtree2(Bitree * tr,char str[])//用广义表的形式创建二叉树。
{
    char ch;
    Bitnode * p;
    Bitree stack[maxsize];
    int flat,k,top;
    top = -1;
    k = 0;
    tr = NULL;
    ch = str[k];
    while(ch != '\0')
    {
        switch(ch)
        {
        case '(':
            top++;
            stack[top] = p;
            flat = 1;
            break;
        case ')':
            top--;
            break;
        case ',':
            flat = 2;
            break;
        default :
            p = (Bitree)malloc(sizeof(Bitnode));
            p->treedate = ch;
            p->lchild = NULL;
            p->rchild = NULL;
        }
        if(*tr == NULL)
            *tr = p;
        else
        {
            switch(flat)
            {
            case '1':
                (*tr)->lchild = p;
                break;
            case '2':
                (*tr)->rchild = p;
                break;
            }
        }
    }
    k++;
    ch = str[k];
   
}

void showtree1(Bitree tr)//二叉树的先序遍历，递归算法。（先根节点，然后左子树，最后右子树）
{
    Bitree  p;
    p = tr;
    if(p)
    {
        printf(" %c ",p->treedate);//如果二叉树非空先输出跟结点数据
        showtree1(p->lchild);//接着遍历左子树
        showtree1(p->rchild);//最后遍历右子树
    }
}

void showtree2(Bitree tr)//二叉树的先序遍历，非递归算法。
{
    Bitree strack[maxsize];//定义一个二叉树的栈，用来存放二叉树的结点指针。
    Bitnode * p;//定义一个二叉树结点类型的指针
    int top ;
    top = 0;
    p = tr;//把传入的二叉树指针给 p 。既把指针p指向二叉树
    while(p != NULL || top > 0)//当p为非空或者二叉树指针栈非空时循环继续。（p != NULL 是为了查找左子树结点并输出。 top > 0 是为了查找右子树结点并输出。）
    {
        while(p != NULL)//如果指针指向的结点非空
        {
            printf(" %c ",p->treedate);//则输出结点数据
            top++;//栈顶指针后移一个
            strack[top] = p;//把结点指针入栈
            p = p->lchild;//把左子树地址给指针 p 。如果左子树指针非空，则循环继续（看二叉树是否有左子树，有的话继续。因为每个左子树都是小二叉树的根节点。而先序遍历跟结点时最先输出的。所以如果左子树非空就要循环回去把结点数据输出，并把结点指针入栈，以便后面查找树结点的右子树，并输出结点数据。）
        }
        if(top > 0)//当上面的p指针为空循环结束时，查看二叉树栈是否为空，如非空。则将栈顶指针给p。并将栈顶指针出栈。方便指针进行右子树操作。
        {
            p = strack[top];
            top--;
            p = p->rchild;
        }
    }
    printf("\n");
}

void showtree3(Bitree tr)//二叉树的中序遍历，递归算法。（先左子树结点，然后根节点，最后右子树结点）
{
    Bitnode * p;
    p = tr;
    if(p)//如果p非空，即二叉树非空。
    {
        showtree3(p->lchild);//先遍历左子树结点，直到结点为空。
        printf(" %c ",p->treedate);//输出结点数据。
        showtree3(p->rchild);//再遍历右子树结点
    }
}

void showtree4(Bitree tr)//二叉树的中序遍历，非递归算法。（先左子树结点，然后根节点，最后右子树结点）
{
    Bitree strack[maxsize];
    int top;   
    Bitnode * p;
    top = 0;
    p = tr;
    while(p != NULL || top > 0)//当二叉树非空或二叉树栈非空
    {
        while(p != NULL)//当二叉树非空，
        {
            top++;//栈顶指针后移
            strack[top] = p;//将二叉树指针入栈。
            p = p->lchild;//并将二叉树指针指向左子树。
        }
        if(top > 0)//如果二叉树栈非空
        {
            p = strack[top];//将栈顶指针给p
            top--;//既栈顶指针出栈
            printf(" %c ",p->treedate);//输出结点数据
            p = p->rchild;//将指针指向右子树结点
        }
    }
}

void showtree5(Bitree tr)//二叉树的后序遍历，递归算法。（先左子树结点，然后右子树结点，最后根节点）
{
    Bitnode * p;
    p = tr;
    if(p)
    {
        showtree5(p->lchild);
        showtree5(p->rchild);
        printf(" %c ",p->treedate);
    }
}

void showtree6(Bitree tr)//二叉树的后序遍历，非递归算法。（先左子树结点，然后右子树结点，最后根节点）
{
    Bitree strack[maxsize];
    int top;
    Bitnode * p,* q;
    top = 0;
    p = tr,q = NULL;
    while(p != NULL || top > 0)
    {
        while(p != NULL)
        {
            top++;
            strack[top] = p;
            p = p->lchild;
        }
        if(top > 0)//右子树有两种情况，一种是右子树结点为空的情况，一种是右子树结点非空。
        {
            p = strack[top];
            if(p->rchild == NULL || p->rchild == q)    //如果p 没有右子树，或者p 的右子树已经访问过了。
            {
                printf(" %c ",p->treedate);
                q = p;//为了防止访问已经访问过的结点而设立一个结点指针q 并把访问过的结点指针p 给q 。是记住已经访问过的结点避免重复访问而陷入死循环。
                p = NULL;//将p 置空是为了退到上一层，做准备。
                top--;//栈顶出栈
            }
            else//右子树非空的情况。
            {
                p = p->rchild;//将指针指向右子树，并继续重复循环（查找左右子树）
            }
        }
    }
}

void showtree7(Bitree tr)//二叉树的层次遍历(先定义个队列把二叉树根节点，左子树结点，右子树结点依次入队，并输出。)
{
    Bitree queue[maxsize];//定义一个二叉树类型的指针队列
    int front,rear;
    Bitnode * p;
    front = rear = -1;
    rear++;
    p = tr;
    queue[rear] = p;//先将二叉树跟结点入队
    while( front != rear )//如果队列非空
    {
        front = (front+1) % maxsize;//循环队列前指针出队
        p = queue[front];//将队头指针给 p 。
        printf(" %c ",p->treedate);//输出二叉树根节点
        if(p->lchild)//如果二叉树左子树结点非空将左子树结点指针入队
        {
            rear = (rear+1) % maxsize;//循环队列出队
            queue[rear] = p->lchild;//左子树结点指针入队
        }
        if(p->rchild)//如果二叉树右子树结点非空将右子树结点指针入队
        {
            rear = (rear+1) % maxsize;
            queue[rear] = p->rchild;
        }
    }
}

void printtree(Bitree tr,int level)//二叉树的树状输出（先右子树结点，再根节点，最后左子树结点，并按递归的层次打印空格）
{
    Bitnode * p;
    p = tr;
    int i;
    if(p == NULL)
        return ;//如果二叉树为空返回
    printtree(p->rchild,level+1);//遍历输出二叉树右子树结点
    for(i = 0;i < level;i++)//按二叉树的层次输出空格
        printf(" ");
    printf("%c\n",p->treedate);//输出结点数据
    printtree(p->lchild,level+1);//遍历输出二叉树左子树结点
}

int leafnum(Bitree tr)//输出叶子节点个数
{
    Bitnode * p;
    p = tr;
    if(!p)//如果二叉树结点为空，则叶子结点为0个
        return 0;//返回 0 。
    if( p->lchild == NULL && p->rchild == NULL )//如果左右子树为空，而结点非空。则二叉树叶子结点为 1个（既根节点）
        return 1;//返回 1 。
    else
        return ( leafnum(p->lchild) + leafnum(p->rchild) );//否则就继续算左右子树的叶子结点个数，既返回左右子树叶子结点的和。
   
}

int notleafnum(Bitree tr)//输出非叶子结点个数。
{
    Bitnode * p;
    p = tr;
    if(!p)
        return 0;//如果结点指针为空那么非叶子结点就是 0 。
    if(p->lchild == NULL && p->rchild == NULL)
        return 0;//如果结点非空，但左右子树为空，非叶子结点数也是 0 个。因为只有一个叶子结点即跟结点。
    else
        return ( notleafnum(p->lchild) + notleafnum(p->rchild) + 1 );//如果结点非空，左右结点非空。那么就递归计算左右结点的非叶子结点个数，并相加后再加 “1” 。再加的“1” 是根节点。
}

int Bitreedepth(Bitree tr)//输出二叉树深度。
{
    Bitnode * p;
    p = tr;
    if(!p)
        return 0;//如果二叉树结点为空那么深度自然就是 “0” 。
    if(p->lchild == NULL && p->rchild == NULL)
        return 1;//如果二叉树结点非空，但左右子树结点为空，那么就是只有根节点。深度自然是 “1” 。
    else//如果左右子树结点非空，那么就要比较左子树和右子树的深度，并取数大的那个，再加 “1”。1 是要加上根节点。
        return ( Bitreedepth(p->lchild) > Bitreedepth(p->rchild) ? Bitreedepth(p->lchild)+1 : Bitreedepth(p->rchild)+1 );
}

void createtree2(Bitree * tr,char str[])
{
  ...
  tr = NULL; /*tr=NULL，是否写错？*/
   [color=#0000FF]if(*tr == NULL)[/color]  /*此时tr为空*/
     *tr = p;
  ...
}

[此贴子已经被作者于2016-4-22 20:22编辑过]