树的定义
树是n个节点的有限集。当n=0时称为空树。在任意一棵非空树中应满足:
有且只有一个特定的称为根的结点。
当n>1时有m个互不相交的优先集,称为根的子树。
节点结构
数据,左孩子和右孩子(分支标识)
编写笔记
建树需要辅助队列-判断节点左右是否满了,满了移动到下一个节点处。建树过程中插入新节点时也要给辅助队列插入。
calloc
可使结构体变量中的成员置NULL。
代码
结构体
需要辅助队列,如下:
typedef char ElemType;
typedef struct TreeNode{
ElemType data;
struct TreeNode *Lchild;
struct TreeNode *Rchild;
}TreeNode,*TreeP;
//tag给辅助队列用
typedef struct tag{
TreeP p;
struct tag *next;
}tag,*tagP;
初始化
声明两个树状结构体变量,分别用作新节点和树根。再声明辅助队列头尾,现在位置以及队列新节点.
插入节点
如果是树的第一个节点,则把辅助队列指向listpnew
,Tree
指向pnew
作为树根。
插入时先在辅助队列尾插,后用辅助队列的pur
判断树中需要插入的节点位置,判断左右孩子是否有空,先左后右,插满后前进到下一个节点。
TreeP pnew; //创建新节点
TreeP tree=NULL; //创建树根
char c;
tagP phead=NULL,ptail=NULL,listpnew=NULL,pcur;
while(scanf("%c",&c)){
if(c=='\n'){
break;
}
//calloc申请的空间大小时两个参数直接相乘,且对空间初始化置0.
pnew=(TreeP)calloc(1,sizeof(TreeNode));
pnew->data=c;
listpnew=(tagP)calloc(1,sizeof(tag)); //给队列节点申请空间
listpnew->p=pnew;
//如果是树的第一个节点
if(tree==NULL){
tree=pnew;
phead=listpnew;
ptail=listpnew;
pcur=listpnew;
}else{
//先入队列
ptail->next=listpnew;
ptail=listpnew;
if(pcur->p->Lchild==NULL){
pcur->p->Lchild=pnew; //左孩子为空
}else if(pcur->p->Rchild==NULL){
pcur->p->Rchild=pnew; //右孩子为空
pcur=pcur->next; //满了pcur指向下一个
}
}
}
输入abcdefgh后得到结果部分如下:
评论