|
数据结构与算法—复习：树 父指针表示法 采用父指针表示法实现的树在进行周游的时候，似乎应该将根节点下标也传入函数中。也可以写一个访问树根的方法，这里不再赘述。 /**
* 程序说明：复习 树的父指针表实现方式 树的周游
*/
#include
#include
/**
* 树 结点类型
*/
struct ParTreeNode{
char info; //结点信息
int parent; //父结点位置
};
/**
* 树类型
*/
struct ParTree{
int MAXNUM; //当前可存放最大结点数
int n; //当前存放结点数
struct ParTreeNode* nodelist; //结点表
};
typedef struct ParTree* PParTree;
/**
* 父指针表示法实现 树
* 树 创建空树
* @param m
* @return
*/
PParTree createNullParTree(int m){
PParTree parTree = (PParTree)malloc(sizeof(struct ParTree));
if(parTree != NULL){
parTree->nodelist = (struct ParTreeNode*)malloc(sizeof(struct ParTree)*m);
if(parTree->nodelist){
parTree->n = 0;
parTree->MAXNUM = m;
return parTree;
}
printf("为结点表分配空间时出错\n");
return parTree;
}
printf("为树结构类型分配空间时出错\n");
}
/**
* 父指针表示法 数据初始化
* @param parTree
*/
void initParTree(PParTree parTree){
char info[] = {'a','b','d','e','h','i','j','c','f','g'};
int parents[]={-1,0,1,1,3,3,3,0,7,7};
int size = sizeof(parents) / sizeof(int);
for (int i = 0; i < size; ++i) {
parTree->nodelist[i].info = info[i];
parTree->nodelist[i].parent = parents[i];
parTree->n++;
}
}
/**
* 父指针表示法 规格化打印
* @param parTree
*/
void printParTree(PParTree parTree){
for (int i = 0; i < parTree->n; ++i) {
printf("[%c,%d]\n",parTree->nodelist[i].info,parTree->nodelist[i].parent);
}
}
/**
* 父指针表示法
* 求某结点的右兄弟结点的下标
* @param parTree
* @param p
* @return
*/
int rightSibling_partree(PParTree parTree,int p){
int i;
if(p>=0 && pn){
for (i = p+1; i < parTree->n; ++i) {
if(parTree->nodelist[i].parent == parTree->nodelist[p].parent) return (i);
}
}
return (-1);
}
/**
* 父指针表示法
* 求某结点的最左子结点的下标
* @param parTree
* @param p
* @return
*/
int leftChild_parTree(PParTree parTree,int p){
if(parTree->nodelist[p+1].parent == p) return p+1;
else return -1;
}
/**
* 父指针表示法
* 先根序列周游，虽然直接按顺序打印也是
* @param parTree
* @param start
*/
void preOrder(PParTree parTree,int start){
if(parTree == NULL || start == -1) return;
printf("%c,",parTree->nodelist[start].info);
preOrder(parTree,leftChild_parTree(parTree,start));
preOrder(parTree,rightSibling_partree(parTree,start));
}
void postOrder(PParTree parTree,int start){
if(parTree == NULL || start == -1) return;
postOrder(parTree,leftChild_parTree(parTree,start));
printf("%c,",parTree->nodelist[start].info);
postOrder(parTree,rightSibling_partree(parTree,start));
}
int main() {
PParTree parTree = createNullParTree(100);
initParTree(parTree);
printParTree(parTree);
printf("F结点的下标为8,他的右兄弟结点位置为：%d\n",rightSibling_partree(parTree,8));
printf("C结点的下标为7,他的最左兄弟结点位置为：%d\n",leftChild_parTree(parTree,7));
preOrder(parTree,0);
printf("\n");
postOrder(parTree,0);
}
|