二叉树递归实现与二重指针


二叉树的诸多操作往往是通过递归调用来实现的，这就决定，不能只通过main函数实现全部过程，其中还需要调用main外定义的函数。也因此，对main调用外定义的函数的参数传递，就有了严格的要求。在网上查找很多关于二叉树建立的程序，但直接拷贝在自己计算机上运行却发现不少错误，无法编译通过。以下有关代码在VS2010上编译通过，不涉及二叉树的全部操作，本文着重通过二叉树的创建过程说明递归实现与二重指针的相关问题。

1、二叉树的定义

二叉树的定义结构通常为如下形式：

typedef struct Node
{
 char ch;
 struct Node *lchild,*rchild;
}Node,*BTree;

Node一般可用来定义二叉树节点，而*BTree可用来定义指向二叉树（根节点）的指针。

2、内存动态分配

采用内存动态分配需要用到malloc函数。值得注意的是，该函数在成功开辟新的内存时，默认返回void*指针（即未指定指针），因此需要强制转换成Node*形式，其调用形式如：(Node*)malloc(sizeof(Node))

3、递归调用

因为递归调用的需要，二叉树的一些操作需要独立作为一个函数。但是，这些函数是在main中调用，因此传递的参数和返回的值的处理是非常重要的。另外注意，对二叉树的操作，首先就需要知道二叉树的入口，即指向二叉树的指针，也即指向二叉树根节点的指针。因此，所传递的参数，则为指向根节点的指针。又因为涉及分配内存的操作，必须传递二级指针才能将实参指向所分配的内存，否则是形参指向了内存块，当函数调用结束时，不复存在，这在有递归调用的函数里，采用返回值也是不起作用，同样在一轮调用结束后被销毁。因此子函数的参数形式为二重指针。

如下程序，CreateTree函数可以是由返回值，也可以不具有返回值（因为传递的是地址）。在main函数中作了测试，返回的值为二叉树根节点的值。

Node* CreateTree(Node** pTree)
{
    char chr;
    scanf("%c",&chr);
    if(chr=='#')
    {
        (*pTree)=NULL;
    }
    else
    {
        if(!((*pTree)=(Node*)malloc(sizeof(Node))))
        {
            exit(OVERFLOW);
//#define OVERFLOW -2
        }
        (*pTree)->ch=chr;
  CreateTree(&((*pTree)->lchild));
  CreateTree(&((*pTree)->rchild));
    }
return *pTree;
}

void main()
{
 Node *pRoot;
 Node *test;
 char ch;
 printf("现在开始创建二叉树...输入N结束\n");
   test=CreateTree(&pRoot);
//传递指针的地址
 //printf("所创建的二叉树为：\n");
 //PrintBinaryTree(test);
 //while(1);
}

附注：测试程序

#include <stdio.h>
#include <stdlib.h>
#define OVERFLOW -2
//定义二叉树节点
typedef struct Node
{
 char ch;
 struct Node *lchild,*rchild;
}Node,*BTree;
//Node *pRoot=NULL;
//输出二叉树函数
void PrintBinaryTree(Node *Tree)
{
 if(Tree==NULL)
    return;
 
  //printf("%c-->",Tree->ch);
  PrintBinaryTree(Tree->lchild);
  printf("%c-->",Tree->ch);
  PrintBinaryTree(Tree->rchild);

}

//创建二叉树

Node* CreateTree(Node** pTree)
{
    char chr;
    scanf("%c",&chr);
    if(chr=='#')
    {
        (*pTree)=NULL;
    }
    else
    {
        if(!((*pTree)=(Node*)malloc(sizeof(Node))))
        {
            exit(OVERFLOW);
        }
        (*pTree)->ch=chr;
  CreateTree(&((*pTree)->lchild));//(*pTree)->lchild为Node *变量，而参数则是Node **变量，则需要&取址，否则形参无法保留*lchild值
  CreateTree(&((*pTree)->rchild));
    }
return *pTree;
}

void main()
{
 Node *treehead;
 Node *test;
 //Node  *bitree=NULL;
 char ch;
 printf("现在开始创建二叉树...输入N结束\n");
   test=CreateTree(&treehead);
 printf("所创建的二叉树为：\n");
 PrintBinaryTree(test);
 while(1);
}

二叉树的常见问题及其解决程序

【递归】二叉树的先序建立及遍历

在JAVA中实现的二叉树结构

【非递归】二叉树的建立及遍历

相关内容