郑州网站推广招聘,网站制作 那种语言好,怎样建立自己网站难吗,抄袭网站怎么办一、树的存储结构
1#xff09;双亲表示法实现#xff1a;
定义结构数组存放树的结点#xff0c;每个结点含两个域:
数据域#xff1a;存放结点本身信息。双亲域#xff1a;指示本结点的双亲结点在数组中的位置。 特点#xff1a;找双亲简单#xff0c;找孩子难
C语…一、树的存储结构
1双亲表示法实现
定义结构数组存放树的结点每个结点含两个域:
数据域存放结点本身信息。双亲域指示本结点的双亲结点在数组中的位置。 特点找双亲简单找孩子难
C语言描述 结点结构
dataparent
typedef struct PTNode {TElemType data; int parent; // 双亲位置域
} PTNode;// 树的存储结构
#define MAX_TREE_SIZE 100
typedef struct {PTNode nodes[MAX_TREE_SIZE];int r n; // 根结点的位置和结点个数
} PTree;2孩子链表
把每个结点的孩子结点排列起来看成是一个线性表用单链表存储则 n 个结点有 n 个孩子链表叶子的孩子链表为空表而 n 个头指针又组成一个线性表用顺序表含 n 个元素的结构数组存储。 特点找孩子容易找双亲难
C语言描述
孩子结点结构
childnext
typedef struct CTNode {int child;struct CTNode* next;
}*ChildPtr;双亲结点结构
datafirstchild
typedef struct {TElemType data;ChildPtr firstchild;// 孩子链表头指针
}CTBox;树结构
typedef struct {CTBox nodes[MAX_TREE_SIZE];int n, r; // 结点数和根结点的位置
} CTree;3孩子兄弟表示法二叉树表示法二叉链表表示法
实现用二叉链表作树的存储结构链表中每个结点的两个指针域分别指向第一个孩子结点和下一个兄弟节点。 typedef struct CSNode {ElemType data; struct CSNode * firstchild, * nextsibling;
}CSNode, *CSTree;二、树与二叉树的转换
将树转化为二又树进行处理利用二又树的算法来实现对树的操作。
由于树和二又树都可以用二叉链表作存储结构则以二又链表作媒介可以导出树与二又树之间的一个对应关系。 1将树转换成二叉树
加线在兄弟之间加一连线。抹线对每个结点除了其左孩子外去除其与其余孩子之间的关系。旋转以树的根结点为轴心将整树顺时针转45度。
口诀
树变二叉树兄弟相连留长子 2将二叉树转换为树
加线若 p 结点是双亲结点的左孩子则将 p 的右孩子右孩子的右孩子.……沿分支找到的所有右孩子都与p的双亲用线连起来。抹线抹掉原二叉树中双亲与右孩子之间的连线。调整将结点按层次排列形成树结构。
口诀
二叉树变树左孩右右连双亲去掉原来右孩线。 三、森林与二叉树的转换
1森林转换成二叉树二又树与多棵树之间的关系
将各棵树分别转换成二叉树将每棵树的根结点用线相连以第一棵树根结点为二叉树的根再以根结点为轴心顺时针旋转构成二叉树型结构
口诀
森林变二叉树树变二叉根相连 2二叉树转换成森林
抹线将二叉树中根结点与其右孩子连线及沿右分支搜索到的所有右孩子间连线全部抹掉使之变成孤立的二又树还原将孤立的二又树还原成树
口诀
二叉树变森林去掉全部右孩线孤立二叉再还原 四、树的遍历三种方式 五、森林的遍历 1先序遍历
若森林不空则
1、访问森林中第一棵树的根结点。
2、无序遍历森林中第一棵树的子树森林。
3、先序遍历森林中除第一棵树之外其余树构成的森林。
即依次从左至右对森林中的每一个树进行先根遍历。
2中序遍历
若森林不空则
1、中序遍历森林中第一棵树的子树森林。
2、访问森林中第一棵树的根结点。
3、中序遍历森林中除第一棵树之外其余树构成的森林。
即依次从左至右对森林中的每一个树进行后根遍历。
