辽宁省建设银行招聘网站,榆次住房和城乡建设局网站,长沙微信网站制作,网站主色怎么选择5.4 树和森林
5.4.1 树的存储结构
树的存储1#xff1a;双亲表示法 用数组顺序存储各结点#xff0c;每个结点中保存数据元素、指向双亲结点(父结点)的“指针”
#define MAX_TREE_SIZE 100// 树的结点
typedef struct{ElemType data;int parent;
}PTNode;// 树的类型
type…5.4 树和森林
5.4.1 树的存储结构
树的存储1双亲表示法 用数组顺序存储各结点每个结点中保存数据元素、指向双亲结点(父结点)的“指针”
#define MAX_TREE_SIZE 100// 树的结点
typedef struct{ElemType data;int parent;
}PTNode;// 树的类型
typedef struct{PTNode nodes[MAX_TREE_SIZE];int n; //结点数量
}PTree;优点找双亲(父结点)很方便 缺点找孩子不方便只能从头到尾遍历整个数组
树的存储2孩子表示法顺序链式存储) #define MAX_TREE_SIZE 100struct CTNode{int child; //孩子结点在数组中的位置struct CTNode *next; //下一个孩子
}typedef struct{ElemType data;struct CTNode *firstChild; //第一个孩子
}CTBox;typedef struct{CTBox node[MAX_TREE_SIZE];int n,r; //结点数和根的位置
}CTree;优点:找孩子很方便 缺点:找双亲(父结点)不方便只能遍历每个链表
树的存储3孩子兄弟表示法 树的孩子兄弟表示法与二叉树类似采用二叉链表实现每个结点内保存数据元素和两个指针但两个指针的含义和二叉树结点不同
//孩子兄弟表示法结点
typedef struct CSNode{ElemType data;struct CSNode *firstchild, *nextsibling; //第一个孩子和右兄弟结点
}CSNode, *CSTree;5.4.2 树、森林与二叉树的转换
树到二叉树的转换 ①先在二叉树中画一个根节点。 ②按“树的层序”依次处理每个结点。 处理一个结点的方法是如果当前处理的结点在树中有孩子就把所有孩子结点 “用右指针串成糖葫芦”并在二叉树中把第一个孩子挂在当前结点的左指针下方
森林到二叉树的转换 ①先把所有树的根结点画出来在二叉树中用右指针串成糖葫芦。 ②按“森林的层序”依次处理每个结点。 处理一个结点的方法是如果当前处理的结点在树中有孩子就把所有孩子结点“用右 指针串成糖葫芦”并在二叉树中把第一个孩子挂在当前结点的左指针下方
注意森林中各棵树的根节点视为平级的兄弟关系
二叉树到树的转换 ①先画出树的根节点 ②从树的根节点开始按“树的层序”恢复每个结点的孩子 如何恢复一个结点的孩子在二叉树中如果当前处理的结点有左孩子就把左孩 子和“一整串右指针糖葫芦” 拆下来按顺序挂在当前结点的下方二叉树到森林的转换 ①先把二叉树的根节点和“一整串右指针糖葫芦”拆下来作为多棵树的根节点 ②按“森林的层序”恢复每个结点的孩子 如何恢复一个结点的孩子在二叉树中如果当前处理的结点有左孩子就把左孩子和“一整串右指针糖葫 芦” 拆下来按顺序挂在当前结点的下方
5.4.3 树和森林的遍历
树的先根遍历。若树非空先访问根结点 再依次对每棵子树进行先根遍历。深度优先遍历 void PreOrder(TreeNode *R){if(R!NULL){visit(R);while(R还有下一个子树T)PreOrder(T);}
}树的先根遍历序列与这棵树相应二叉树的先序序列相同
树的后根遍历。若树非空先依次对每棵子树进行后根遍历最后再访问根结点。深度优先遍历树的后根遍历序列与这棵树相应二叉树的中序序列相同。
树的层次遍历用队列实现广度优先遍历 ①若树非空则根节点入队 ②若队列非空队头元素出队并访问同时将该元素的孩子依次入队 ③重复②直到队列为空
森林的先序遍历 森林。森林是m (m0棵互不相交的树的集合。每棵树去掉根节点后其各个子树又组成森林。
若森林为非空则按如下规则进行遍历:
访问森林中第一棵树的根结点。先序遍历第一棵树中根结点的子树森林。先序遍历除去第一棵树之后剩余的树构成的森林。
效果等同于依次对各个树进行先根遍历等同于对二叉树的先序遍历。
森林的中序遍历
中序遍历森林中第一棵树的根结点的子树森林。访问第一棵树的根结点。中序遍历除去第一棵树之后剩余的树构成的森林
效果等同于依次对各个树进行后根遍历等同于对二叉树的中序遍历。
