| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 3163 人关注过本帖
标题:关于二叉树建立(递归)不明白啊。
只看楼主 加入收藏
ctw888
Rank: 1
等 级:新手上路
帖 子:18
专家分:0
注 册:2007-5-22
收藏
得分:0 
如果getchar()为空了,令T=NULL,就不执行else语句了。也就是程序结束了。

程序是怎么转回来执行CreateBinTree(&(*T)->rchild); //构造右子树??
2008-11-27 16:07
wefgod
Rank: 1
等 级:新手上路
帖 子:9
专家分:0
注 册:2008-11-27
收藏
得分:0 
以下是引用ctw888在2008-11-27 16:07的发言:

如果getchar()为空了,令T=NULL,就不执行else语句了。也就是程序结束了。

程序是怎么转回来执行CreateBinTree(&(*T)->rchild); //构造右子树??

我看看我应该怎么表达
比如
我输入a@c@@   @代表空格
意思就是我根节点是a,a的左子树为空,a右孩子节点为c
你看看程序如何执行呢?
接收了a,然后执行左子树的建立,递归
然后函数中,因为遇到了@所以就结束了子树的建立,然后返回到a的那个函数内,继续执行建立右子树
这中间有一个层次的关系
2008-11-27 16:52
盆中线
Rank: 1
等 级:新手上路
帖 子:48
专家分:0
注 册:2008-11-6
收藏
得分:0 
主要就是输入。。。上次也是做这个试验,写出了,可是没注意输入,直接死循环。。
2008-11-30 13:25
jdshaoheyi
Rank: 1
等 级:新手上路
帖 子:133
专家分:5
注 册:2008-11-6
收藏
得分:0 
我以一个例子说明一下:
先序创建,读入字符的顺序如下:A B C * * D E * G * * F * * *
首先输入一个字符为A,判断不是空格,分配存储空间并且使其数据为A,下面执行到了 CreateBinTree(&(*T)->lchild);,构造左子树,A的右子树等待创建,!注意此时为递归调CreateBinTree函数,又再次要求输入数据,此时输入B,然后创建B的左子树,B的右子树等待创建(注意了A此时仍在等待创建他的右子树),
创建B的左子树时用户输入了C,此时再次进入调用,先创建左子树,右子树等待创建,此后用户输入了*,即左子树为空,然后创建右子树,用户输入*,此时应该有些明白了,C这一棵"局部的树"创建完毕,但是你要知道B和A都在等待创建自己的右子树,递归过程有了回退的过程,退到创建B的右子树,创建B的右子树的过程我不必再赘述了...
可能有些罗嗦,但是如果认真看,其实帮助不小.....
2008-11-30 14:54
geninsf009
Rank: 3Rank: 3
等 级:论坛游民
威 望:8
帖 子:613
专家分:95
注 册:2008-8-16
收藏
得分:0 
我刚写了递归算法,和教材上不一样的是,采用了较多的参数,s是前序序列的描述字符串,用了一个start的含义是开始创建的位置,返回的是子树创建结束后字符串指针的位置,代码如下,测试已通过了:

PS:我写的思想是通过函数的返回值,即创建完字符串指针停留的位置,
这样可以分割左右子树前序序列,而这样更便于递归的实现。
/////////////////////////////////////////////////
//PreOrderCreate()公有成员函数
//递归通过前序序列创建一棵二叉树,前序序列中
//空子树用符号'#'来代替,s是前序序列描述字符串
//返回的是创建结束后字符串停留的当前位置
/////////////////////////////////////////////////
template<class T>
int BinaryTree<T>::PreOrderCreate(
            char* s,int start,BinTreeNode<T>*& subTree)
{
    if(s[start]!='#')          //如果当前读入的不是空子树
    {
        BinTreeNode<T>* newNode//创建新结点
            =new BinTreeNode<T>(s[start]);
        subTree=newNode;       //新建立的根结点
  
        int k=PreOrderCreate(s,//从start+1位置开始递归创建左子树
            start+1,subTree->leftChild);
        PreOrderCreate(s,k+1,  //递归创建右子树
            subTree->rightChild);
    }
    else
    {
        subTree=NULL;          //创建空子树
        return start;          //当前子树最后一个'#'
    };
};
/////////////////////////PreOrderCreate()函数结束

[[it] 本帖最后由 geninsf009 于 2008-12-3 20:02 编辑 [/it]]
2008-12-03 19:56
geninsf009
Rank: 3Rank: 3
等 级:论坛游民
威 望:8
帖 子:613
专家分:95
注 册:2008-8-16
收藏
得分:0 
测试输入的二叉树前序描述字符串是:
"ABC##DE#G##F###"
运行结果是:A(B(C,D(E(,G),F)),)
2008-12-03 19:59
ctw888
Rank: 1
等 级:新手上路
帖 子:18
专家分:0
注 册:2007-5-22
收藏
得分:0 
第14楼还是比较好理解的.像我这样的初学者适用.
2008-12-09 11:39
快速回复:关于二叉树建立(递归)不明白啊。
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.044629 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved