数据结构基础：树与二叉树定义及遍历算法

先访问根结点，再递归遍历左子树，最后右子树

b.中序遍历：

左 → 根 → 右

简易方法：把这个二叉树展平，把字母放在一条线上，然后从左到右依次写出来就是 GDHBAEICF

注意：写算法的时候还是得知道它的原理是先递归遍历左子树，再访问根，最后右子树

c.后序遍历

左 → 右 → 根

先递归遍历左右子树，最后访问根结点

d.层序遍历

从上到下、从左到右

按层次逐层访问，通常借助队列实现

三、二叉树的算法实现

二叉树的结构体：

相关算法：

主要是利用递归实现

1.创建二叉树：

和操作数组差不多

char tree_seq[] = "ABDG##H###CE#I##F##"; int idx = 0; //索引 // 常见操作函数 btree_t * create_btree() // 创建二叉树 { //1.获取数据 char data = tree_seq[idx]; idx++; if (data == '#') { return NULL;//NULL 表示结束 } //2.创建新节点 malloc btree_t *new = malloc(sizeof(btree_t)); if (new == NULL) { printf("%s: malloc fail!\n",__func__); return NULL; } new->data = data;//tree_seq[idx]; //根 new->pl = create_btree(); //左 new->pr = create_btree(); //右 return new; }

2.前序遍历：

原理：根左右，递归即可

//函数 最终返回后，返回的是根节点 int pre_order_traverse(btree_t *t) //传根节点的地址 { //结束条件 t == NULL if (t == NULL) { return 0; } printf("%c ",t->data);//根 pre_order_traverse(t->pl); //左子树 //左 pre_order_traverse(t->pr);// 右子树 //右 return 0; }

3.中序遍历：

左根右

注意：递归函数名一定得和写的一致

int in_order_traverse(btree_t *t) // 中序遍历 { //结束条件 t == NULL if (t == NULL) { return 0; } in_order_traverse(t->pl); //左子树 //左 printf("%c ",t->data);//根 in_order_traverse(t->pr);// 右子树 //右 return 0; }

4.后序遍历：

左右根

int post_order_traverse(btree_t *t) // 后序遍历 { //结束条件 t == NULL if (t == NULL) { return 0; } post_order_traverse(t->pl); //左子树 //左 post_order_traverse(t->pr);// 右子树 //右 printf("%c ",t->data);//根 return 0; } 

5.销毁二叉树：

后续遍历，然后销毁

int btree_destroy(btree_t *t) // 销毁二叉树 { if (t == NULL) { return -1; } //递归 --- 后序方式 //左右根 btree_destroy(t->pl);//左 btree_destroy(t->pr);//右边 free(t); return 0; }

6.层序遍历：

需要用到链式队列，把队列那那一篇的结构体和函数拿来用

注意：队列结构体的数据域是二叉树的结构体地址

即： typedef struct btree data_t;//队列处理的数据类型是地址*

难点在于这个循环能否理解，只要队列不为空就持续循环：拿节点出队打印

 int layer_order_traverse(btree_t *t) { if(t == NULL) { return -1; } //创建队列 qnode_t *pque = create_queue(); //拿节点，入队 enqueue(pque,t); while(pque->next !=NULL)//一直循环，直到队列没有数据 { //出队打印 btree_t *p = dequeue(pque); printf("%c",p->data); //如果有左右孩子，就入队 if(p->pl != NULL) { enqueue(pque,p->pl); } if(p->pr != NULL) { enqueue(pque,p->pr); } } putchar('\n'); queue_destroy(&pque);//销毁队列 return 0; }