|
一:树的创建
void CreatBitree2(BiTree *T) //读边按层次创建二叉树
{
LinkQueue Q;
InitQueue(&Q);
BiTree p,s;
char fa,ch;
int lrflag;
setbuf(stdin,NULL); //清空键盘输入
scanf("%c%c%d",&fa,&ch,&lrflag);
while(ch != '#')
{
p = (BiTree)malloc(sizeof(BiNode)); //二叉树结点p用来记录新数据
p->data = ch;
p->lchild = p->rchild = NULL; //置空
EnQueue(&Q,p); //父结点入队列
if(fa == '#')
{
*T = p; //如果fa为# 则p为总的根结点T
}
else
{
GetHead(Q,&s);
while(s->data != fa) //找到插入结点的父结点的位置
{
DeQueue(&Q,&s);
GetHead(Q,&s);
}
// 此时s为父结点
if(lrflag == 0) //如果子结点标记为0，将新结点p与父节点lchild连接
{
s->lchild = p;
}
else if(lrflag == 1)
{
s->rchild = p; //同理，p连上父结点rchild
}
else
{
free(p);
printf("输入错误！按任意键重新输入...."); //标志输入错误，新结点释放重新输入
getch();
}
}
setbuf(stdin,NULL); //清空键盘输入
scanf("%c%c%d",&fa,&ch,&lrflag);
}
}第二种方法就是直接输入树中结点，通过代码的处理转化为二叉树结构，与第一种方法的处理顺序是相反的。 void CreateCSTree(CSTree *T)//树的按边层次创建
{
LinkQueue Q;
InitQueue(&Q);
CSTree p,s,sign;
char fa,data;
printf("请输入新建结点的父元素和子元素的数据：");
scanf("%c %c",&fa,&data); //scanf(" %c") 一个空格在加上%c：表示读取遇到的第一个非空格字符
getchar();
while(data != '#')
{
s = (CSTree)malloc(sizeof(CSNode));
s->data = data;
s->firstchild = s->nextsibling = NULL;
EnQueue(&Q,s);
if(fa == '#')
{
*T = s;
}
else
{
GetHead(Q,&p);
while(p->data != fa)
{
DeQueue(&Q,&p);
GetHead(Q,&p);
}
//此时p为父元素结点地址
if(p->firstchild == NULL)//父元素的firstchild连接
{
p->firstchild = s;
sign = s; //父元素firstchild已被连接，用sign记住s；
}
else //父元素其他孩子连在sign的nextsibling上
{
sign->nextsibling = s;
sign = s; //依然记住，便于下一个结点连接
}
}
printf("请输入新建结点的父元素和子元素的数据：");
scanf("%c %c",&fa,&data);
getchar();
}
}
三:根结点到叶子结点所有的路径 void DispPath(BiTree T,SqStack *s) //输出所有的根到叶子结点的路径
{
Bitree p;
if(T)
{
Push(s,p);
if(T->lchild == NULL && T->rchild == NULL)
{
PrintStack(*s);
printf("\n");
}
else
{
DispPath(T->lchild,s);
DispPath(T->rchild,s);
}
Pop(s),&p);
}
}
void DispPath(CSTree T,SqStack *s)//输出树从根结点到叶子结点的所有路径
{
CSTree temp = T;
if(T)
{
Push(s,temp);
if(T->firstchild == NULL) //第一个孩子结点为空说明当前结点为叶子结点
{
PrintStack(*s);
printf("\n");
}
else //一直向左遍历
{
DispPath(T->firstchild,s);
}
Pop(s,&temp);
if(T->nextsibling) //必须保证firstchild出栈后，才能向兄弟结点遍历
{
DispPath(T->nextsibling,s);
}
}
}
void SearchCST(CSTree T,char keyword,CSTree *p)//查找插入位置
{
if(T)
{
if(T->data == keyword)
{
*p = T;
}
if(p)
{
SearchCST(T->firstchild,keyword,p);
SearchCST(T->nextsibling,keyword,p);
}
}
}
int Insert(CSTree T,char fa,char data)//数据插入
{
CSTree pos = NULL,s; //pos记录新结点插入地址
if(T == NULL)
{
return 0;
}
SearchCST(T,fa,&pos);
if(pos) //在树中找到插入结点地址
{
s = (CSTree)malloc(sizeof(CSNode));
s->firstchild = s->nextsibling = NULL;
s->data = data;
if(pos->firstchild == NULL)//根的第一个孩子不存在则连上firstchild指针
{
pos->firstchild = s;
}
else //根的第一个孩子存在，连上nextsibling末尾
{
pos = pos->firstchild;
while(pos->nextsibling)
{
pos = pos->nextsibling;
}
pos->nextsibling = s;
}
return 1;
}
else
{
printf("父结点数据输入错误，在树中找不到此结点数据\n");
return 0;
}
}
int DeletePoint(CSTree *T,char fa,char data) //删除一个结点 因为删除结点可能是树根，所以*T
{
CSTree p = NULL,s;
SearchCST(*T,fa,&p); //找父结点位置
if(fa == '#') //删除结点是树根的情况
{
CleanCSTree(*T);
*T = NULL;
return 1;
}
if(p == NULL)
{
return 0;
}
else //父结点找到，继续对子结点情况分类
{
if(p->firstchild->data == data) //删除结点是firstchild的情况
{
s = p->firstchild; //记住删除结点地址
p->firstchild = s->nextsibling; //连接上后面的结点
s->nextsibling = NULL;
CleanCSTree(s); //清空以删除结点为树根的树
}
else //删除结点是兄弟结点时
{
p = p->firstchild; //p指向第一个孩子结点
while(p->nextsibling && p->nextsibling->data != data) //用循环找到要删除的结点
{
p = p->nextsibling;
}
if(p->nextsibling->data == data) //此时p状态：p指向删除结点的前一个结点
{
s = p->nextsibling;
p->nextsibling = s->nextsibling; //将p的nextsibling连接到删除结点的后面一个结点
s->nextsibling = NULL;
CleanCSTree(s); //清空以删除结点为树根的树
return 1;
}
else //没有找到结点,删除失败
{
return 0;
}
}
}
return 1;
}数据结构与算法 树与二叉树 我们这篇博文介绍非线性结构—树与二叉树，我先介绍树的一些基本概念，树的遍历，再介绍二叉树相关概念和特性，以及二叉树的遍历，最后再树与二叉树的对比，总结。
1、结点的度
1、前序遍历
学习二叉树的特性几乎可以帮助我们解决所有的二叉树问题，在学习二叉树特性一定要通过上面给出的二叉树进行实践，实践出真理，同时，印象也会更深刻。 1、前序遍历（与树的前序遍历一样） |
