软件设计师2006年11月下午试题5(C语言 树及其孩子-兄弟表示)

简介: [说明]  一般的树结构常采用孩子-兄弟表示法表示,即用二叉链表作树的存储结构,链表中结点的两个链域分别指向该结点的第一个孩子结点和下一个兄弟结点。例如,图 5-1(a) 所示的树的孩子-兄弟表示如图 5-1(b)所示。

[说明]
  一般的树结构常采用孩子-兄弟表示法表示,即用二叉链表作树的存储结构,链表中结点的两个链域分别指向该结点的第一个孩子结点和下一个兄弟结点。例如,图 5-1(a) 所示的树的孩子-兄弟表示如图 5-1(b)所示。

图 5-1 树及其孩子-兄弟表示示意图


  函数 LevelTraverse()的功能是对给定树进行层序遍历。例如,对图 5-1 所示的树进 行层序遍历时,结点的访问次序为:D B A E F P C 。
  对树进行层序遍历时使用了队列结构,实现队列基本操作的函数原型如下表所示:

 

函数原型

说明

void InitQueue(Queue *Q)

初始化队列

Bool IsEmpty(Queue Q)

判断队列是否为空,若是则返回 TRUE,否则返回 FALSE

void EnQueue(Queue *Q,TreeNode p)

元素入队列

void DeQueue(Queue *Q,TreeNode *p)

元素出队列

Bool、Status 类型定义如下:
   typedef enum {FALSE = 0,TRUE = 1} Bool;
   typedef enum {OVERFLOW = -2,UNDERFLOW = -1,ERROR = 0,OK = 1} Status;

  树的二叉链表结点定义如下:
   typedef struct Node {
    char data;
    struct Node *firstchild,*nextbrother;
   }Node,*TreeNode;

[函数]
  Status LevelTraverse(TreeNode root)
  { /*层序遍历树,树采用孩子-兄弟表示法,root 是树根结点的指针*/
   Queue tempQ;
   TreeNode ptr,brotherptr;
   if (!root)
    return ERROR;
   InitQueue(&tempQ);
   EnQueue(&tempQ,root) ;
   brotherptr = root -> nextbrother;
   while (brotherptr){ EnQueue(&tempQ,brotherptr);
     brotherptr=brotherptr->nextbrother;
   } /*end-while*/
   while ( !IsEmpty(tempQ) ) {
     DeQueue(&temp,&ptr);
    printf("%c\t",ptr->data);
    if (!ptr->firstchild) continue;
     EnQueue(&tempQ,ptr->firstchild);
    brotherptr = ptr->firstchild->nextbrother;
    while (brotherptr){ EnQueue(&tempQ,brotherptr);
      brotherptr=brotherptr->nextbrother;
    } /*end-while*/
   } /*end-while*/
   return OK;
  }/*LevelTraverse*/

相关文章
|
3月前
|
存储 算法 C语言
"揭秘C语言中的王者之树——红黑树:一场数据结构与算法的华丽舞蹈,让你的程序效率飙升,直击性能巅峰!"
【8月更文挑战第20天】红黑树是自平衡二叉查找树,通过旋转和重着色保持平衡,确保高效执行插入、删除和查找操作,时间复杂度为O(log n)。本文介绍红黑树的基本属性、存储结构及其C语言实现。红黑树遵循五项基本规则以保持平衡状态。在C语言中,节点包含数据、颜色、父节点和子节点指针。文章提供了一个示例代码框架,用于创建节点、插入节点并执行必要的修复操作以维护红黑树的特性。
92 1
|
2月前
|
C语言
数据结构基础详解(C语言):图的基本概念_无向图_有向图_子图_生成树_生成森林_完全图
本文介绍了图的基本概念,包括图的定义、无向图与有向图、简单图与多重图等,并解释了顶点度、路径、连通性等相关术语。此外还讨论了子图、生成树、带权图及几种特殊形态的图,如完全图和树等。通过这些概念,读者可以更好地理解图论的基础知识。
|
2月前
|
存储 算法 C语言
数据结构基础详解(C语言): 二叉树的遍历_线索二叉树_树的存储结构_树与森林详解
本文从二叉树遍历入手,详细介绍了先序、中序和后序遍历方法,并探讨了如何构建二叉树及线索二叉树的概念。接着,文章讲解了树和森林的存储结构,特别是如何将树与森林转换为二叉树形式,以便利用二叉树的遍历方法。最后,讨论了树和森林的遍历算法,包括先根、后根和层次遍历。通过这些内容,读者可以全面了解二叉树及其相关概念。
|
2月前
|
存储 机器学习/深度学习 C语言
数据结构基础详解(C语言): 树与二叉树的基本类型与存储结构详解
本文介绍了树和二叉树的基本概念及性质。树是由节点组成的层次结构,其中节点的度为其分支数量,树的度为树中最大节点度数。二叉树是一种特殊的树,其节点最多有两个子节点,具有多种性质,如叶子节点数与度为2的节点数之间的关系。此外,还介绍了二叉树的不同形态,包括满二叉树、完全二叉树、二叉排序树和平衡二叉树,并探讨了二叉树的顺序存储和链式存储结构。
|
2月前
|
存储 C语言
数据结构基础详解(C语言): 树与二叉树的应用_哈夫曼树与哈夫曼曼编码_并查集_二叉排序树_平衡二叉树
本文详细介绍了树与二叉树的应用,涵盖哈夫曼树与哈夫曼编码、并查集以及二叉排序树等内容。首先讲解了哈夫曼树的构造方法及其在数据压缩中的应用;接着介绍了并查集的基本概念、存储结构及优化方法;随后探讨了二叉排序树的定义、查找、插入和删除操作;最后阐述了平衡二叉树的概念及其在保证树平衡状态下的插入和删除操作。通过本文,读者可以全面了解树与二叉树在实际问题中的应用技巧和优化策略。
|
5月前
|
测试技术 C语言
数据结构学习记录——树习题—Tree Traversals Again(题目描述、输入输出示例、解题思路、解题方法C语言、解析)
数据结构学习记录——树习题—Tree Traversals Again(题目描述、输入输出示例、解题思路、解题方法C语言、解析)
43 1
|
6月前
|
C语言 容器
从C语言到C++_27(AVL树)概念+插入接口实现(四种旋转)(上)
从C语言到C++_27(AVL树)概念+插入接口实现(四种旋转)
44 4
|
5月前
|
存储 C语言
详细解读AVL树(查找、插入、删除)——C语言
详细解读AVL树(查找、插入、删除)——C语言
22 0
|
5月前
|
存储 C语言
详细解读AVL树(查找、插入、删除)——C语言
详细解读AVL树(查找、插入、删除)——C语言
24 0
|
6月前
|
C语言 C++
从C语言到C++_27(AVL树)概念+插入接口实现(四种旋转)(下)
从C语言到C++_27(AVL树)概念+插入接口实现(四种旋转)
42 2