数据结构 ——树状存储的实现

1、树的遍历
按层遍历：从树的根节点开始，逐层遍历树中的所有节点。这种遍历方式也称为广度优先遍历。

先序遍历（前序遍历）：先访问根节点，然后递归地先序遍历左子树，最后递归地先序遍历右子树。

中序遍历：先递归地中序遍历左子树，然后访问根节点，最后递归地中序遍历右子树。

后序遍历：先递归地后序遍历左子树，然后递归地后序遍历右子树，最后访问根节点。

先序和中序 /中序和后序 能确定一颗树

下面为各种遍历示意图

2、代码实现
下面是以递归的思想来构建和遍历一颗二叉树

#include<stdio.h>
#include<stdlib.h>
#define NAMESIZE 32
//以无头节点的链表构建二叉树
struct score_st
{int id;char name[NAMESIZE];int math;int chinese;
};
struct node_st
{struct score_st data;struct node_st *l,*r;
};
void print_s1(struct score_st *d)
{printf("%d %s %d %d\n",d->id,d->name,d->math,d->chinese);
}
//插入原则：比当前节点小的插入左子树，比节点大的插入右子树 
int insert(struct node_st **root,struct score_st *data)
{struct node_st *node;//走到空节点或叶子节点if(*root==NULL){node=(struct node_st*)malloc(sizeof(struct node_st));if(node==NULL)return -1;node->data=*data;node->l=NULL;//防止野指针的出现node->r=NULL;*root=node;//根节点指向创建出来的新节点，后面递归时root为传入的左或右子树的指针return 0; }//比当前节点小的插入左子树，比节点大的插入右子树,递归遍历if(data->id<=(*root)->data.id)return insert(&(*root)->l,data);return insert(&(*root)->r,data);
}
struct score_st *find(struct node_st *root,int id)
{//传过来的节点为叶子节点空的左或右孩子，说明走到了一个不存在的分支if(root==NULL)return NULL;if(id==root->data.id)return &(root->data);//传进来的id比当前节点小，往左子树找if(id<root->data.id)return find(root->l,id);//传进来的id比当前节点大，往右子树找return find(root->r,id);
}
void draw_(struct node_st *root,int level)
{/*往左边倒，画出树的结构，先画当前节点的右子树，再跟节点，最后root->rrootroot->l*/if(root==NULL)return; //空节点或空的叶子结点//先画右子树，右子树不止一层，所以递归调用，画右子树的右子树（当前层的下一层）draw_(root->r,level+1);//画空格,即当前节点前面的空格for(int i=0;i<level;i++)printf("  ");//画根节点print_s1(&root->data);//画左子树draw_(root->l,level+1);}
void draw(struct node_st *root)
{//根据层数画出树和空格draw_(root,0);
}
int main()
{int arr[]={1,2,3,7,6,5,9,8,4};int i;struct node_st *tree=NULL;struct score_st tmp,*datap;for(i=0;i<sizeof(arr)/sizeof(arr[0]);i++){tmp.id=arr[i];snprintf(tmp.name,NAMESIZE,"stu%d",arr[i]);tmp.math=rand()%100;tmp.chinese=rand()%100;//无头节点要改变指针的指向，传二级指针insert(&tree,&tmp);}draw(tree);#if 0//查找测试int tmpid=1;datap=find(tree,tmpid);if(datap==NULL)printf("Can not find the id %d!\n",tmpid);else print_s1(datap);#endifreturn 0;
}