树的表示法—孩子兄弟表示法
2020-02-27 本文已影响0人
零岁的我
普通树示意图
孩子兄弟表示法，采用的是链式存储结构，其存储树的实现思想是：从树的根节点开始，依次用链表存储各个节点的孩子节点和兄弟节点。
节点结构示意图
孩子兄弟表示法示意图
C语言实现代码：
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#define overflow -2
typedef char Elemtype; //设置树节点的数据域数值类型为字符型
//树节点结构体
typedef struct Tnode{
Elemtype data;
struct Tnode *lchild; //节点的左孩子
struct Tnode *nextSibling; //节点的第一个兄弟节点
}Tnode,*Tree;
typedef Tree Qelem;
//队列节点结构体
typedef struct TQnode{
Qelem qnode;
struct TQnode *next;
}TQnode,*QueuePtr;
//队列结构体
typedef struct TQueue{
QueuePtr front; //队头指针
QueuePtr rear; //队尾指针
}TQueue;
//初始化队列，构造一个空队列
void initQueue(TQueue &Q)
{
Q.front=Q.rear=(QueuePtr)malloc(sizeof(TQnode));
if(!Q.front)
exit(overflow);
Q.front ->next=NULL;
}
bool EmptyQueue(TQueue Q)
{
if(Q.front==Q.rear)
return true;
return false;
}
//在队列的末尾插入一个新的节点
void EnQueue(TQueue &Q,Qelem e)
{
QueuePtr tmp=(QueuePtr)malloc(sizeof(TQueue));
if(!tmp)
exit(overflow);
tmp->qnode=e;
tmp->next=NULL;
Q.rear->next=tmp; //从队尾进队
Q.rear=tmp;
}
void DelQueue(TQueue &Q,Qelem &e)
{
if(EmptyQueue(Q))
{
printf("队列为空，出队操作错误");
//return false;
}
QueuePtr p=Q.front->next; //从对头出队
e=p->qnode;
Q.front->next=p->next;
if(Q.rear==p)
Q.rear=Q.front;
free(p);
}
//创建树
void CreateTree(Tree &T)
{
TQueue Q;
initQueue(Q); //构造一个空队列
char buffChild[20]; //用来缓存树节点数据域的存储值
printf("请输入根节点(字符，以#代表空):");
scanf("%c",&buffChild[0]);
getchar();
if(buffChild[0]!='#'){
T=(Tree)malloc(sizeof(Tnode)); //为根节点开辟一个空间
if(!T)
exit(overflow);
T->data=buffChild[0];
T->nextSibling=NULL; //根节点没有兄弟节点
EnQueue(Q,T); //根节点入队
while(!EmptyQueue(Q)){
Qelem e;
DelQueue(Q,e); //节点出列
printf("请按长幼顺序输入节点%c的孩子节点(以#结束)：",e->data);
scanf("%s",buffChild);
getchar();
if(buffChild[0]!='#'){
Tree child=(Tree)malloc(sizeof(Tnode));//开辟孩子节点的空间
if(!child)
exit(overflow);
child->data=buffChild[0];
e->lchild=child; //指向第一个孩子节点
EnQueue(Q,child);
Tree tmp=child;
for(size_t i=1;i<strlen(buffChild)-1;++i){ //有兄弟节点
child=(Tree)malloc(sizeof(Tnode));
if(!child)
exit(overflow);
child->data=buffChild[i];
tmp->nextSibling=child;
EnQueue(Q,child);
tmp=child;
}
tmp->nextSibling=NULL;
}
else{
e->lchild=NULL; //没有孩子节点
//printf("节点%c没有孩子节点\n",e->data);
}
}
}
else{
T=NULL;
}
}
//使用递归销毁树
void DestroyTree(Tree &T)
{
if(T){
if(T->lchild)
DestroyTree(T->lchild);
if(T->nextSibling)
DestroyTree(T->nextSibling);
free(T);
T=NULL;
}
}
void ClearTree(Tree &T)
{
DestroyTree(T);
}
bool EmptyTree(Tree T)
{
if(!T){
return true;
}
return false;
}
//返回树的深度
int DepthTree(Tree T)
{
if(EmptyTree(T))
return 0;
if(EmptyTree(T->lchild))
return 1;
int max=0;
int depth=0;
Tree p;
for(p=T->lchild;p;){
depth=DepthTree(p);
if(depth>max)
max=depth;
p=p->nextSibling;
}
return max+1;
}
Elemtype Root(Tree T)
{
if(T)
return T->data;
return 0;
}
Tnode *FindNode(Tree T,Elemtype cure)
{
if(EmptyTree(T))
{
printf("没有要查找的元素");
return NULL;
}
TQueue Q;
initQueue(Q);
EnQueue(Q,T);
while(!EmptyQueue(Q)){
Qelem e;
DelQueue(Q,e);
if(e->data==cure)
return e;
if(e->lchild)
EnQueue(Q,e->lchild);
if(e->nextSibling)
EnQueue(Q,e->nextSibling);
}
return NULL;
}
Tnode *parent(Tree T,Elemtype cure)
{
TQueue Q;
initQueue(Q);
if(T){
if(T->data==cure)
return NULL;
EnQueue(Q,T);
while(!EmptyQueue(Q)){
Qelem e;
DelQueue(Q,e);
Qelem tmp=e;
if(e->lchild){
if(e->lchild->data==cure)
return tmp;
EnQueue(Q,e->lchild);
Qelem sibling=e->lchild->nextSibling;
while(sibling){
if(sibling->data==cure)
return tmp;
EnQueue(Q,sibling);
sibling=sibling->nextSibling;
}
}
}
}
return NULL;
}
Elemtype leftChild(Tree T,Elemtype cure)
{
Tnode *findnode=FindNode(T,cure);
if(findnode){
if(findnode->lchild)
return findnode->lchild->data;
}
printf("没有孩子节点\n");
return NULL;
}
Elemtype rigthSibling(Tree T,Elemtype cure)
{
Tnode *findnode=FindNode(T,cure);
if(findnode){
if(findnode->nextSibling)
return findnode->nextSibling->data;
}
printf("没有兄弟节点");
return NULL;
}
//层次遍历树
void LevelTraverse(Tree T)
{
TQueue Q;
initQueue(Q);
if(T){
printf("%c ",T->data); //访问根节点
EnQueue(Q,T); //根节点入队
while(!EmptyQueue(Q)){
Qelem e,tmp;
DelQueue(Q,e);
tmp=e->lchild;
while(tmp){ //依次访问双亲节点的孩子节点及孩子节点的兄弟节点
printf("%c ",tmp->data);
EnQueue(Q,tmp);
tmp=tmp->nextSibling;
}
}
printf("\n");
}
else
printf("树为空\n");
}
int main(int argc,char **argv)
{
Tree T;
CreateTree(T);
printf("树的深度为：%d\n",DepthTree(T));
printf("层次遍历树的结果为：");
LevelTraverse(T);
printf("树的根节点为：%c\n",Root(T));
printf("请输入要查询的节点：");
Elemtype e;
scanf("%c",&e);
Tnode *findnode=FindNode(T,e);
if(findnode){
printf("查询结果为：元素%c存在\n",findnode->data);
}
findnode=parent(T,e);
if(findnode){
printf("节点%c的双亲是：%c\n",e,findnode->data);
}
else
printf("查询的节点不存在，或者节点%c的双亲不存在\n",e);
printf("节点%c的第一个孩子节点为：%c\n",e,leftChild(T,e));
printf("节点%c的第一个兄弟节点为：%c\n",e,rigthSibling(T,e));
printf("销毁树后，树的层次遍历结果为：");
DestroyTree(T);
LevelTraverse(T);
return 0;
}
运行结果
结论：可以发现，通过孩子兄弟表示法，任意一棵普通树都可以相应转化为一棵二叉树，换句话说，任意一棵普通树都有唯一的一棵二叉树于其对应。
因此，孩子兄弟表示法是将普通树转换为二叉树的最有效方法，通常又被称为“二叉树表示法”或“二叉链表表示法”。
参考链接：
