“ Ctrl AC!一起 AC!”
目录
树有三种表示方法:
树的遍历有三种:
结点结构:
树的前序遍历递归版:
树的后序遍历递归版:
按前序遍历顺序建立一颗树:
树的层次遍历:
树有三种表示方法:
双亲表示法,孩子表示法和兄弟表示法。
这里我们使用指针式的孩子表示法。
树的遍历有三种:
前序遍历,后序遍历,层序遍历(二叉树还有中序遍历)
结点结构:
#define m 3 //m指树的度
typedef char datatype;
typedef struct node{
datatype data;
struct node *child[m];
}node, *tree;
tree root;
树的前序遍历递归版:
void preorder(tree p){
int i;
if(p!=NULL){
printf("%c",p->data);
for(i=0;i<m;i++){ //m为子节点的最大个数(即整个树的度)
preorder(p->child[i]);
}
}
}
树的后序遍历递归版:
void postorder(tree p){
int i;
if(p!=NULL){
for(i=0;i<m;i++){
postorder(p->child[i]);
}
printf("%c",p->data);
}
}
按前序遍历顺序建立一颗树:
tree createtree(){
int i;char ch;
tree t;
if((ch=getchar())=='#') t=NULL;
else{
t=(tree)malloc(sizeof(node));
t->data=ch;
for(i=0;i<m;i++){
t->child[i]=createtree();
}
}
return t;
}
树的层次遍历:
void levelorder(tree t){
tree queue[100]; //存放待输出的树的结点
int f,r,i; //f,r指头尾指针
tree p;
f=0; r=1; queue[0]=t; //先放入根节点
while(f<r){ //队列不为空
p=queue[f]; //取出头指针访问
f++; //头指针移动
printf("%c",p->data);
for(i=0;i<m;i++){ //遍历子节点
if(p->child[i]){ //如果存在
queue[r]=p->child[i]; //将他加入队列,等待输出
r++;
}
}
}
}
感谢阅读!!!
“ Ctrl AC!一起 AC!”