术语

节点的度 ：一个节点含有的子树的个数称为该节点的度；

树的度 ：一棵树中，最大的节点的度称为树的度；

叶节点 或 终端节点 ：度为零的节点；

非终端节点 或 分支节点 ：度不为零的节点；

父亲节点 或 父节点 ：若一个节点含有子节点，则这个节点称为其子节点的父节点；

孩子节点 或 子节点 ：一个节点含有的子树的根节点称为该节点的子节点；

兄弟节点 ：具有相同父节点的节点互称为兄弟节点；

节点的 层次 ：从根开始定义起，根为第1层，根的子节点为第2层，以此类推；

树的 高度 或 深度 ：树中节点的最大层次；

堂兄弟节点 ：父节点在同一层的节点互为堂兄弟；

节点的祖先 ：从根到该节点所经分支上的所有节点；

子孙 ：以某节点为根的子树中任一节点都称为该节点的子孙。

森林 ：由m（m>=0）棵互不相交的树的集合称为森林；

树的种类

无序树：树中任意节点的子节点之间没有顺序关系，这种树称为无序树，也称为自由树；

有序树：树中任意节点的子节点之间有顺序关系，这种树称为有序树；

存储

父节点表示法

存储结构

基本操作

设已有链队列类型LinkQueue的定义及基本操作（参见队列）。

构造空树

清空或销毁一个树也是同样的操作

voidClearTree(PTree*T){T->n=0;}

构造树

voidCreateTree(PTree*T){LinkQueueq;QElemTypep,qq;inti=1,j,l;charc[MAX_TREE_SIZE];/* 临时存放孩子节点数组 */InitQueue(&q);/* 初始化队列 */printf("请输入根节点(字符型，空格为空): ");scanf("%c%*c",&T->nodes[0].data);/* 根节点序号为0，%*c吃掉回车符 */if(T->nodes[0].data!=Nil)/* 非空树 */{T->nodes[0].parent=-1;/* 根节点无父节点 */qq.name=T->nodes[0].data;qq.num=0;EnQueue(&q,qq);/* 入队此节点 */while(i<MAX_TREE_SIZE&&!QueueEmpty(q))/* 数组未满且队不空 */{DeQueue(&q,&qq);/* 节点加入队列 */printf("请按长幼顺序输入节点%c的所有孩子: ",qq.name);gets(c);l=strlen(c);for(j=0;jnodes[i].data=c[j];T->nodes[i].parent=qq.num;p.name=c[j];p.num=i;EnQueue(&q,p);/* 入队此节点 */i++;}}if(i>MAX_TREE_SIZE){printf("节点数超过数组容量\n");exit(OVERFLOW);}T->n=i;}elseT->n=0;}

判断树是否为空

StatusTreeEmpty(PTree*T){/* 初始条件：树T存在。操作结果：若T为空树，则返回TRUE，否则返回FALSE */returnT->n==0;}

获取树的深度

intTreeDepth(PTree*T){/* 初始条件：树T存在。操作结果：返回T的深度 */intk,m,def,max=0;for(k=0;kn;++k){def=1;/* 初始化本节点的深度 */m=T->nodes[k].parent;while(m!=-1){m=T->nodes[m].parent;def++;}if(max<def)max=def;}returnmax;/* 最大深度 */}

获取根节点

TElemTypeRoot(PTree*T){/* 初始条件：树T存在。操作结果：返回T的根 */inti;for(i=0;in;i++)if(T->nodes[i].parentnodes[i].data;returnNil;}

获取第i个节点的值

TElemTypeValue(PTree*T,inti){/* 初始条件：树T存在，i是树T中节点的序号。操作结果：返回第i个节点的值 */if(in)returnT->nodes[i].data;elsereturnNil;}

改变节点的值

StatusAssign(PTree*T,TElemTypecur_e,TElemTypevalue){/* 初始条件：树T存在，cur_e是树T中节点的值。操作结果：改cur_e为value */intj;for(j=0;jn;j++){if(T->nodes[j].data==cur_e){T->nodes[j].data=value;returnOK;}}returnERROR;}

获取节点的父节点

TElemTypeParent(PTree*T,TElemTypecur_e){/* 初始条件：树T存在，cur_e是T中某个节点 *//* 操作结果：若cur_e是T的非根节点，则返回它的父节点，否则函数值为＂空＂*/intj;for(j=1;jn;j++)/* 根节点序号为0 */if(T->nodes[j].data==cur_e)returnT->nodes[T->nodes[j].parent].data;returnNil;}

获取节点的最左孩子节点

TElemTypeLeftChild(PTree*T,TElemTypecur_e){/* 初始条件：树T存在，cur_e是T中某个节点 *//* 操作结果：若cur_e是T的非叶子节点，则返回它的最左孩子，否则返回＂空＂*/inti,j;for(i=0;in;i++)if(T->nodes[i].data==cur_e)/* 找到cur_e，其序号为i */break;for(j=i+1;jn;j++)/* 根据树的构造函数，孩子的序号＞其父节点的序号 */if(T->nodes[j].parent==i)/* 根据树的构造函数，最左孩子(长子)的序号＜其它孩子的序号 */returnT->nodes[j].data;returnNil;}

获取节点的右兄弟节点

TElemTypeRightSibling(PTree*T,TElemTypecur_e){/* 初始条件：树T存在，cur_e是T中某个节点 *//* 操作结果：若cur_e有右(下一个)兄弟，则返回它的右兄弟，否则返回＂空＂*/inti;for(i=0;in;i++)if(T->nodes[i].data==cur_e)/* 找到cur_e，其序号为i */break;if(T->nodes[i+1].parent==T->nodes[i].parent)/* 根据树的构造函数，若cur_e有右兄弟的话则右兄弟紧接其后 */returnT->nodes[i+1].data;returnNil;}

输出树

voidPrint(PTree*T){/* 输出树T。加 */inti;printf("节点个数=%d\n",T->n);printf(" 节点 父节点\n");for(i=0;in;i++){printf(" %c",Value(T,i));/* 节点 */if(T->nodes[i].parent>=0)/* 有父节点 */printf(" %c",Value(T,T->nodes[i].parent));/* 父节点 */printf("\n");}}

向树中插入另一棵树

StatusInsertChild(PTree*T,TElemTypep,inti,PTreec){/* 初始条件：树T存在，p是T中某个节点，1≤i≤p所指节点的度+1，非空树c与T不相交 *//* 操作结果：插入c为T中p节点的第i棵子树 */intj,k,l,f=1,n=0;/* 设交换标志f的初值为1，p的孩子数n的初值为0 */PTNodet;if(!TreeEmpty(T))/* T不空 */{for(j=0;jn;j++)/* 在T中找p的序号 */if(T->nodes[j].data==p)/* p的序号为j */break;l=j+1;/* 如果c是p的第1棵子树，则插在j+1处 */if(i>1)/* c不是p的第1棵子树 */{for(k=j+1;kn;k++)/* 从j+1开始找p的前i-1个孩子 */if(T->nodes[k].parent==j)/* 当前节点是p的孩子 */{n++;/* 孩子数加1 */if(n==i-1)/* 找到p的第i-1个孩子，其序号为k1 */break;}l=k+1;/* c插在k+1处 */}/* p的序号为j，c插在l处 */if(ln)/* 插入点l不在最后 */for(k=T->n-1;k>=l;k--)/* 依次将序号l以后的节点向后移c.n个位置 */{T->nodes[k+c.n]=T->nodes[k];if(T->nodes[k].parent>=l)T->nodes[k+c.n].parent+=c.n;}for(k=0;knodes[l+k].data=c.nodes[k].data;/* 依次将树c的所有节点插于此处 */T->nodes[l+k].parent=c.nodes[k].parent+l;}T->nodes[l].parent=j;/* 树c的根节点的父节点为p */T->n+=c.n;/* 树T的节点数加c.n个 */while(f){/* 从插入点之后，将节点仍按层序排列 */f=0;/* 交换标志置0 */for(j=l;jn-1;j++)if(T->nodes[j].parent>T->nodes[j+1].parent){/* 如果节点j的父节点排在节点j+1的父节点之后（树没有按层序排列），交换两节点*/t=T->nodes[j];T->nodes[j]=T->nodes[j+1];T->nodes[j+1]=t;f=1;/* 交换标志置1 */for(k=j;kn;k++)/* 改变父节点序号 */if(T->nodes[k].parent==j)T->nodes[k].parent++;/* 父节点序号改为j+1 */elseif(T->nodes[k].parent==j+1)T->nodes[k].parent--;/* 父节点序号改为j */}}returnOK;}else/* 树T不存在 */returnERROR;}

删除子树

Statusdeleted[MAX_TREE_SIZE+1];/* 删除标志数组(全局量) */voidDeleteChild(PTree*T,TElemTypep,inti){/* 初始条件：树T存在，p是T中某个节点，1≤i≤p所指节点的度 *//* 操作结果：删除T中节点p的第i棵子树 */intj,k,n=0;LinkQueueq;QElemTypepq,qq;for(j=0;jn;j++)deleted[j]=0;/* 置初值为0(不删除标记) */pq.name="a";/* 此成员不用 */InitQueue(&q);/* 初始化队列 */for(j=0;jn;j++)if(T->nodes[j].data==p)break;/* j为节点p的序号 */for(k=j+1;kn;k++){if(T->nodes[k].parent==j)n++;if(n==i)break;/* k为p的第i棵子树节点的序号 */}if(kn)/* p的第i棵子树节点存在 */{n=0;pq.num=k;deleted[k]=1;/* 置删除标记 */n++;EnQueue(&q,pq);while(!QueueEmpty(q)){DeQueue(&q,&qq);for(j=qq.num+1;jn;j++)if(T->nodes[j].parent==qq.num){pq.num=j;deleted[j]=1;/* 置删除标记 */n++;EnQueue(&q,pq);}}for(j=0;jn;j++)if(deleted[j]==1){for(k=j+1;kn;k++){deleted[k-1]=deleted[k];T->nodes[k-1]=T->nodes[k];if(T->nodes[k].parent>j)T->nodes[k-1].parent--;}j--;}T->n-=n;/* n为待删除节点数 */}}

层序遍历树

voidTraverseTree(PTree*T,void(*Visit)(TElemType)){/* 初始条件：二叉树T存在,Visit是对节点操作的应用函数 *//* 操作结果：层序遍历树T,对每个节点调用函数Visit一次且仅一次 */inti;for(i=0;in;i++)Visit(T->nodes[i].data);printf("\n");}

孩子链表表示法

存储结构

/*树的孩子链表存储表示*/typedefstructCTNode{// 孩子节点intchild;structCTNode*next;}*ChildPtr;typedefstruct{ElemTypedata；// 节点的数据元素ChildPtrfirstchild；// 孩子链表头指针}CTBox;typedefstruct{CTBoxnodes[MAX_TREE_SIZE]；intn,r；// 节点数和根节点的位置}CTree;

森林、树与二叉树的转换

见二叉树相应章节

参考文献

免责声明：以上内容版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。感谢每一位辛勤著写的作者，感谢每一位的分享。