赞
踩
树和森林
树的三种表示方法:1:双亲表示法,2:孩子表示法 ,3:孩子兄弟表示法
森林的先根遍历=树的先序遍历,森林的后根遍历=树的中序遍历
1:给定一棵树,可以找到唯一的一棵二叉树与之对应
2:双亲表示法:小蝌蚪找妈妈
#define MAX_Tree_Size 100
#define TElemtype int
typedef struct PTNode{
TElemtype data;
int parent;
}PTNode;
typedef struct{
PTNode nodes[MAX_Tree_Size ];
int r,c;//根的位置和结点数
}PTree;
树转化成二叉树:孩子兄弟描述法,该树结点的孩子1放于对应二叉树该结点的左子树,该树结点的孩子2…n放于对应二叉树该结点的左子树的右子树(一直右下去)
#define MaxSize 100//队列用 #define Status int #define Error -1 #define ok 0 #define True 1 typedef struct CSNode{ Elemtype data; struct CSNode *firstchild,*nextsibling;//孩子--兄弟 }CSNode,*CSTree; //遍历左孩右兄结构的辅助-->队列 typedef struct QNode{//队列所使用 CSTree data; }QNode,*QueuePtr;//数据结点 typedef struct QHeadNode{//队列所使用 QNode *front; QNode *rear; }QHeadNode,*LinkQueue; //头结点// 头指针 Status Init_queue(LinkQueue *Q){ (*Q)=(LinkQueue)malloc(sizeof(QHeadNode)); (*Q)->front=(*Q)->rear=(QueuePtr)malloc(sizeof(QNode)*MaxSize);//有容量限制的Queue if(!(*Q)->front) return Error; return ok; } Status CSTEnQueue(LinkQueue *Q,CSTree T){ if((*Q)->rear-(*Q)->front==MaxSize-1) return Error; (*Q)->rear++; (*Q)->rear->data=T; return ok; } Status CSTDeQueue(LinkQueue *Q,CSTree *T){ if((*Q)->rear==(*Q)->front) return Error; (*Q)->front++; *T=(*Q)->front->data; return ok; } Status IsCSTqueueEmpty(LinkQueue *Q){ if((*Q)->front==(*Q)->rear) return True; else return ok; } CSTree GoFarsibling(CSTree T,LinkQueue *Q){ while(T){//走到最后一个兄弟 printf("%-2c- ",T->data); //在这里面打印 if(T->firstchild) CSTEnQueue(Q,T); //有孩子保存入队列先 if(T->nextsibling==NULL) break; T=T->nextsibling; } return T;//返回最后一个兄弟 } //------------遍历左孩右兄树---类似于树的层次遍历--------------/ //思想:遍历该结点的兄弟那一支,若遇到有孩子的结点,则该结点入队列,遍历完这支后,再从第一个//入队的结点的孩子开始,遍历其兄弟,输出结点的函数其实是GoFarsibling() Status SiblingchildTraverse(CSTree T){ LinkQueue Q;Init_queue(&Q); CSTree t=NULL; t=(CSTree)malloc(sizeof(CSNode)); t= GoFarsibling(T,&Q); while(t){ CSTDeQueue(&Q,&t); if(t->firstchild) GoFarsibling(t->firstchild,&Q);//有左孩,从左孩遍历其兄弟 else if(!IsCSTqueueEmpty(&Q)) CSTDeQueue(&Q,&t);//队不空,退队 else break; } return ok; } //--------------------递归建左孩右兄树------------------// void CreateCSTree(CSTree *T){ int data; printf("输入元素\n"); scanf("%c",&data); getchar(); if(data=='#') *T=NULL; else{ *T=(CSTree)malloc(sizeof(CSNode)); (*T)->data=data; CreateCSTree(&(*T)->nextsibling);//Important顺序 CreateCSTree(&(*T)->firstchild); } } void CSTreetest(){//相当于main() CSTree T; T=(CSTree)malloc(sizeof(CSNode)); CreateCSTree(&T); printf("见证奇迹的时候到了\n"); SiblingchildTraverse(T); }
输入:A B C # F # G H K # # # # # D E # # # 跟建树函数的递归顺序有关
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。