怎样给一个树初始化
怎样把一个树用二叉链表的存储方式存储
typedef Node{
char data;
char*firstcild,*nextsibling;
}
问题点数：20、回复次数：10Top
1 楼llmsn（"若虚"即"虚怀若谷"!!!）回复于 2005-04-22 12:31:30 得分 0
初始化啊,就找到你要初始化那个结点给它赋值就是了,要建立二叉树,你用插入函数就行了.Top
2 楼useresu（俗人)(灌水是我无言的抗议）回复于 2005-04-22 12:31:57 得分 0
就是把树拆成二叉森林,然后赋值,数据结构的书上都有讲的.Top
3 楼llmsn（"若虚"即"虚怀若谷"!!!）回复于 2005-04-22 12:34:01 得分 20
#include <stdio.h>
#include <stdlib.h>
#define NULL 0
struct btnode
{int d;
struct btnode *lchild;
struct btnode *rchild;
};
typedef struct btnode* bt;
void main()
{int b, k;
struct btnode *p,*t;
printf("input b:");
scanf("%d",&b);
if(b!=0)
{p=(struct btnode * )malloc(sizeof(struct btnode));
p->d=b;p->lchild=NULL;p->rchild=NULL;
if(k==0) t=p;
if(k==1) bt->lchild=p;
if(k==2) bt->rchild=p;
creatbt(p,1);
creatbt(p,2);
}
}
我想大家一定和我一样看的一头雾水吧，部分函数根本就没有定义，怎么能够进行调用呢？
其实，在C语言中，基本上函数的功能都是我们自己去实现的，这个就要靠我们的基本功了。
-----------------------------下面是我更正的程序源代码和附加的说明部分-------------------------
#include <stdio.h>
#include <stdlib.h>
#define NULL 0 /*若在Visual C++6.0中，可能要求其为空指针类型，即*/
#define DataType int /*#define NULL ((void *)0) */
typedef struct BinTreeNode *PBinTreeNode; /*定义指向二叉树节点的指针类型*/
typedef PBinTreeNode *PBinTree; /*定义一个保存根节点的指针类型*/
struct BinTreeNode
{ DataType info;
PBinTreeNode llink;
PBinTreeNode rlink;
};
PBinTreeNode Create_BinTree(void); /*声明Create_BinTree()函数，后面的Create_BinTreeeNode()要调用到它，不然的话会报错*/
PBinTree Create_BinTreeRoot(void) /*/创建一个指向二叉树根节点的指针*/
{PBinTree pbtree;
pbtree=(PBinTree)malloc(sizeof(PBinTreeNode));
if(pbtree==NULL) pbtree=(PBinTree)realloc(pbtree,sizeof(PBinTreeNode));
*pbtree=Create_BinTree(); /*为根节点赋值*/
return (pbtree);
}
PBinTreeNode Create_BinTreeNode(void) /*/创建一个二叉树的节点*/
{PBinTreeNode pbnode;
pbnode=(PBinTreeNode)malloc(sizeof(PBinTreeNode));
if(pbnode==NULL) pbnode=(PBinTreeNode)realloc(pbnode,sizeof(PBinTreeNode));
else pbnode->llink=pbnode->rlink=(PBinTreeNode)NULL;
return (pbnode);
}
PBinTreeNode Create_BinTree(void)
{PBinTreeNode pbnode ;
DataType i;
printf("Please input number to the binatree: 0 to exit:\n");
scanf("%d", &i);
if(i==0) pbnode= NULL;
else
{
pbnode = (PBinTreeNode)malloc(sizeof(struct BinTreeNode));
if(pbnode == NULL)
{
printf("Out of space!\n");
return pbnode ;
}
pbnode->info=i;
pbnode->llink=Create_BinTree(); /*左递归调用Create_BinTree()*/
pbnode->rlink=Create_BinTree(); /*右递归调用Create_BinTree()*/
}
return pbnode;
}
void outputTree(PBinTreeNode pbnode,int totalSpace) /*输出我们的二叉树*/
{int i;
if(pbnode!=NULL) {totalSpace+=5; /*右子树与根节点相距5个空格*/
outputTree(pbnode->rlink,totalSpace);
for(i=0;i<totalSpace;i++) printf(" ");
printf("%d\n",pbnode->info);
outputTree(pbnode->llink,totalSpace); /*递归调用左子树*/
}
}
int main()
{PBinTree pbtree;
int totalSpace = 0;
pbtree = Create_BinTreeRoot(); /*Create_BinTreeRoot()函数中调用了Create_BinTree() */
outputTree(*pbtree,totalSpace);
return 0;
}
----------------------------------------程序的调试部分-------------------------
假设我们输入的数值是: 1 2 0 0 3 0 0
我们得到的输出结果为：
3
1
2
Top
4 楼useresu（俗人)(灌水是我无言的抗议）回复于 2005-04-22 12:52:50 得分 0
7．2．2 树的存储结构
在计算机中，树的存储有多种方式，既可以采用顺序存储结构，也可以采用链式存储结构，但无论采用何种存储方式，都要求存储结构不但能存储各结点本身的数据信息，还要能唯一地反映树中各结点之间的逻辑关系。下面介绍几种基本的树的存储方式。
1．双亲表示法
由树的定义可以知道，树中的每个结点都有唯一的一个双亲结点，根据这一特性，可用一组连续的存储空间（一维数组）存储树中的各个结点，数组中的一个元素表示树中的一个结点，数组元素为结构体类型，其中包括结点本身的信息以及结点的双亲结点在数组中的序号，树的这种存储方法称为双亲表示法。其存储表示可描述为：
#define MAXNODE <树中结点的最大个数>
typedef struct {
elemtype data;
int parent;
}NodeType;
NodeType t[MAXNODE];
图7.1(a)所示的树的双亲表示如图7.3所示。图中用parent域的值为-1表示该结点无双亲结点，即该结点是一个根结点。
树的双亲表示法对于实现Parent（t，x）操作和Root（x）操作很方便，但若求某结点的孩子结点，即实现Child（t，x，i）操作时，则需要查询整个数组。此外，这种存储方式不能反映各兄弟结点之间的关系，所以实现RightSibling（t，x）操作也比较困难。在实际中，如果需要实现这些操作，可在结点结构中增设存放第一个孩子的域和存放第一个右兄弟的域，就能较方便地实现上述操作了。
序号 data parent
A -1
B 0
C 0
D 1
E 1
F 1
G 2
H 4
I 4
图7.3 图7.1(a)所示树的双亲表示法示意
2．孩子表示法
（1）多重链表法
由于树中每个结点都有零个或多个孩子结点，因此，可以令每个结点包括一个结点信息域和多个指针域，每个指针域指向该结点的一个孩子结点，通过各个指针域值反映出树中各结点之间的逻辑关系。在这种表示法中，树中每个结点有多个指针域，形成了多条链表，所以这种方法又常称为多重链表法。
在一棵树中，各结点的度数各异，因此结点的指针域个数的设置有两种方法：
① 每个结点指针域的个数等于该结点的度数；
② 每个结点指针域的个数等于树的度数。
对于方法①，它虽然在一定程度上节约了存储空间，但由于树中各结点是不同构的，各种操作不容易实现，所以这种方法很少采用；方法②中各结点是同构的，各种操作相对容易实现，但为此付出的代价是存储空间的浪费。图7.4是图7.1(a)所示的树采用这种方法的存储结构示意图。显然，方法②适用于各结点的度数相差不大的情况。
树中结点的存储表示可描述为：
#define MAXSON <树的度数>
typedef struct TreeNode {
elemtype data;
struct TreeNode *son[MAXSON];
}NodeType;
对于任意一棵树t，可以定义：NodeType *t;使变量t为指向树的根结点的指针。
图7.4 图7.1(a)所示树的孩子表示法示意
（2）孩子链表表示法
孩子链表法是将树按如图7.5所示的形式存储。其主体是一个与结点个数一样大小的一维数组，数组的每一个元素有两个域组成，一个域用来存放结点信息，另一个用来存放指针，该指针指向由该结点孩子组成的单链表的首位置。单链表的结构也由两个域组成，一个存放孩子结点在一维数组中的序号，另一个是指针域，指向下一个孩子。
序号 data firstchild
A
B
C
D ∧
E
F ∧
G ∧
H ∧
I ∧
图7.5 图7.1(a)所示树的孩子链表表示法示意
在孩子表示法中查找双亲比较困难，查找孩子却十分方便，故适用于对孩子操作多的应用。
这种存储表示可描述为：
#define MAXNODE <树中结点的最大个数>
typedef struct ChildNode{
int childcode;
struct ChildNode *nextchild;
}
typedef struct {
elemtype data;
struct ChildNode *firstchild;
}NodeType;
NodeType t[MAXNODE];
3．双亲孩子表示法
双亲表示法是将双亲表示法和孩子表示法相结合的结果。其仍将各结点的孩子结点分别组成单链表，同时用一维数组顺序存储树中的各结点，数组元素除了包括结点本身的信息和该结点的孩子结点链表的头指针之外，还增设一个域，存储该结点双亲结点在数组中的序号。图7.6所示图7.1(a)的树采用这种方法的存储示意图。
序号 data parent firstchild
A -1
B 0
C 0
D 1 ∧
E 1
F 1 ∧
G 2 ∧
H 4 ∧
I 4 ∧
图7.6 图7.1(a)所示树的双亲孩子表示法示意
4．孩子兄弟表示法
这是一种常用的存储结构。其方法是这样的：在树中，每个结点除其信息域外，再增加两个分别指向该结点的第一个孩子结点和下一个兄弟结点的指针。在这种存储结构下，树中结点的存储表示可描述为：
typedef struct TreeNode {
elemtype data;
struct TreeNode *son;
struct TreeNode *next;
}NodeType;
这是树的几种存储方法,
初始化就是具体的链表或数组操作了.Top
5 楼ratzip（小小）回复于 2005-04-22 12:57:12 得分 0
呵呵 一起学习吧 我们正好讲到这里啦！Top
6 楼hanweizhouricher（牛）回复于 2005-04-22 13:11:52 得分 0
我们也是到这里Top
7 楼zfeidiyard（菲迪亚特）回复于 2005-04-22 13:12:56 得分 0
从书上copy下来的吧？Top
8 楼willianzhong（我要Linux）回复于 2005-04-22 19:28:14 得分 0
sTop
9 楼du51（郁郁思扬）回复于 2005-04-22 19:48:50 得分 0
二叉树不就是二叉链表吗?
初始化不就是 NodeType *root;
不就行了.
Top
10 楼zdy_8212（zdy_8212）回复于 2005-04-22 19:49:08 得分 0
定义好一个结构后,你就可以进行这么些步骤:开辟内存.
p=(tree)malloc(sizeof(struct tree));
那么p就可以用来使用了.
当然也可以在定义结构的时候直接用指针指向,那么在使用时.用->指向.如果没有办法赋值,用strcpy函数.基本操作就想象下吧.Top
