网站建设验收方案,摄影婚纱网站建设,企业年金交了有好处吗,网站建设小故事目录 树和森林树的存储结构一、树的双亲表示法#xff1a;二、树的孩子表示法方法一#xff1a;定长结点的多重链表方法二#xff1a;不定长结点的多重链表方法三#xff1a;孩子单链表表示法 三、树的二叉链表(孩子-兄弟)存储表示法 森林与二叉树的转换树和森林的遍历先根… 目录 树和森林树的存储结构一、树的双亲表示法二、树的孩子表示法方法一定长结点的多重链表方法二不定长结点的多重链表方法三孩子单链表表示法 三、树的二叉链表(孩子-兄弟)存储表示法 森林与二叉树的转换树和森林的遍历先根(次序)遍历后根(次序)遍历待补充按层次遍历(待补充 树与二叉树知识点文章: 【数据结构】树与二叉树递归法先序、中序、后序、层次遍历二叉树、二叉树的建立以及求树高的方法二叉树遍历算法的应用: 【数据结构】树与二叉树遍历算法的应用求叶子节点个数、求树高、复制二叉树、创建二叉树、二叉树存放表达式、交换二叉树每个结点的左右孩子
树和森林
树的非顺序存储映像
双亲表示法孩子表示法树的二叉链表(孩子-兄弟)存储表示法
树的存储结构
一、树的双亲表示法
祖先双亲 定义用一维数组存放树中的每一结点的值(data)和双亲位置parent,逻辑关系
特点找祖先易找子孙难 典型用例并查集
//树的双亲表示法
#define MAX_TREE_SIZE 100
typedef struct PTNode {int data;int parent; // 双亲位置
} PTNode;typedef struct {PTNode nodes[MAX_TREE_SIZE];int r,n;//r为根节点的位置,n为树中结点的个数
} PTree;说明结点存放无顺序要求根结点不一定存在第一个位置每个数组元素对应树中一个结点存放结点的值和双亲位置r—根结点位置n—树中结点个数。 二、树的孩子表示法
树的孩子表示法:存放树中每个结点的信息、直接后继的地址。
根据结点直接后继的存放方式分为
定长结点的多重链表每个结点按照树的度设置孩子指针的数量不定长结点的多重链表每个结点按照结点自身的度设置孩子指针的数量孩子单链表每个结点的孩子结点直接后继建一个单链表
方法一定长结点的多重链表
树的孩子表示法定长结点的多重链表 (典型实现树的层次遍历)
定义链表存放树中的每一结点的值(data)和孩子结点位置(child[i]第i个孩子指针表示逻辑关系)每个结点的孩子指针的个数树中孩子最多的结点的孩子个数树的度. 1. 特点结点的结构统一若树的度为d则点包含一个数据域d个孩子指针域. 2. 缺点空指针多浪费空间 方法二不定长结点的多重链表
树的孩子表示法–不定长结点的多重链表
定义链表存放树中的每一结点的值(data)和孩子结点位置child[i]逻辑关系每个结点的孩子指针的个数该结点的孩子个数结点的度 树的度为d,该树的不定长结点的多重链表中结点结构有几种 树的度为d3,该树的不定长结点的多重链表中结点结构有4种 总结树的度为d,该树的不定长结点的多重链表中结点结构有d1种. 特点结点的结构不统一包含一个数据域结点的度d d个孩子指针域 缺点操作较复杂
方法三孩子单链表表示法
将每个结点的孩子结点拉成一个单链表 情况一 结点C在孩子表示法中存了2次 一次出现在下标为2的数组元素中该数组元素同时保存了C的孩子单链表的头指针。 一次出现在结点A的孩子单链表中。 数据元素存放多次更新操作比较麻烦更新一个数据元素所有保存该数据元素的地方均要更新否则信息不一致 情况二 为节省存储空间、方便更新操作和数据维护每个数据元素只在数组中存放一次 在孩子单链表中只存放这个孩子在数组中的位置。 如下图所示 结点A的孩子单链表中第一个孩子结点是下标为1的数组元素B第二个孩子是下标为2的数组元素C第三个孩子是下标为3的数组元素D。
若既要找子孙又要找祖先可将孩子单链表和双亲表示法结合在一起每个数组元素的data域存放数据元素的值pa域存放双亲结点在数组中的位置firstchild存其孩子单链表的头指针。
typedef struct CTNode{ int child;struct CTNode *next;} *ChildPtr;//数组元素类型
typedef struct{ ElemType data; ChildPtr firstchild;
//孩子单链表的头指针
} CTBox;//树
typedef struct{CTBox nodes[MAX_TREE_SIZE]; int n,r;
// 树的结点数和根结点的位置
} CTree;
三、树的二叉链表(孩子-兄弟)存储表示法
[fc,data,nb]
typedef structCSNode{ElemType data;structCSNode*fc, *nb;
}CSNode, *CSTree;树中每个结点三部分 数据域data长子指针域(fc) 右邻兄弟指针域(nb)
树和二叉树的转换 • 树以孩子兄弟表示法存相当于将树转换成二叉树但此二叉树根结点无右子树 • 好处借助二叉树的操作实现树的操作
森林与二叉树的转换
⮚ 树采用二叉链表(孩子-兄弟)存储表示法转换成二叉树 ⮚ 森林由多棵树组成 F ( T 1 , T 2 , … , T n ) F ( T1, T2, …, Tn ) F(T1,T2,…,Tn); 将其每棵树转换成二叉树 B T 1 , B T 2 , … , B T n BT₁, BT₂, …, BTn BT1,BT2,…,BTn; ⮚ 每棵二叉树BT的根的右子树皆为空树从BTn开始依次将其根结点链为前一棵二叉树的根的右孩子 ⮚ 将森林转换成一棵二叉树森林的操作可借助二叉树的操作完成
森林和二叉树的转换 • 森林以孩子兄弟表示法存相当于将森林转换成二叉树 • 好处借助二叉树的操作实现森林的操作
树和森林的遍历
■ 树的遍历可有三条搜索路径: ⮚ 先根(次序)遍历:若树不空则先访问根结点然后依次先根遍历各棵子树。 ⮚ 后根(次序)遍历:若树不空则先依次后根遍历各棵子树然后访问根结点。 ⮚ 按层次遍历:若树不空则自上而下自左至右访问树中每个结点。
[fc,data,nb]
typedef structCSNode{int data;structCSNode*fc, *nb;
}CSNode, *CSTree;树中每个结点三部分数据域data长子指针域(fc)右邻兄弟指针域(nb)
先根(次序)遍历
对应二叉树的先序
//树的孩子兄弟表示法
typedef structCSNode{ElemType data;structCSNode*fc, *nb;
}CSNode, *CSTree;//二叉树的二叉链表表示法
typedef struct BiTNode {ElemType data;struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;void PreorderTraverse(CSTree T){SeqStack s ; s.top-1; p T;while(p){while(p){printf(“%c”,p-data);if(p-nb)if(s.topMAX-1) exit (0);else s.data[s.top]p-nb;p p-fc;}if (s.top!-1) ps.data[s.top--];}
}后根(次序)遍历待补充
对应二叉树的中序
按层次遍历(待补充
叶子结点 判断是否为子孩子 fc是否为空 p-fc NULL
森林由三部分构成 1森林中第一棵树的根结点 2森林中第一棵树的子树森林 3森林中其它树构成的森林。 后根(次序)遍历与对应的二叉树的中序遍历相同先根(次序)遍历与对应的二叉树的先序遍历相同森林的先序遍历—对应二叉树的先序遍历森林的中序遍历—对应二叉树的中序遍历 感谢阅读
树与二叉树知识点文章: 【数据结构】树与二叉树递归法先序、中序、后序、层次遍历二叉树、二叉树的建立以及求树高的方法二叉树遍历算法的应用: 【数据结构】树与二叉树遍历算法的应用求叶子节点个数、求树高、复制二叉树、创建二叉树、二叉树存放表达式、交换二叉树每个结点的左右孩子
