数据结构基础：树与二叉树定义及遍历算法 | 极客日志

数据结构基础：树与二叉树定义及遍历算法 | 极客日志

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; }

//函数 最终返回后，返回的是根节点 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; }

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; }

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; }

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

 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; }