数据结构与算法·树和森林

一、树与森林的概念界定

1. 树 是由n(n≥0)个节点构成的有限集合；当n=0时，该结构被称为空树

若n>0，则满足以下条件：(1) 存在一个唯一确定的节点，该节点被定义为根

(2) 除根节点外，其余节点可划分为m(m≥0)个互不重叠的有限集合T1,T2,T3,...,Tm

2. 森林：是由m(m≥0)棵彼此之间无交集的树所组成的集合

二、树的存储结构

1.双亲表示法

达成: 设计结构化数组用于存储树的节点，每个节点包含两个部分

数据部分: 用于保存节点自身的相关信息

父节点部分: 标识当前节点的父节点在数组中的具体位置

特性: 查找父节点较为便捷，而查找子节点则较为困难

 #define SIZE 10

    
  
    
 typedef char Datatype;
    
 typedef struct PTNode
    
 {
    
 	Datatype ch;