RX0_UNICORN 的學生作業(yè)：
// linkstack.h
#ifndef __LINKSTACK_H__
#define __LINKSTACK_H__
#include
#include
#include
#include "bitree.h"
typedef bitree_t *datatype_t;
// 節(jié)點類型
typedef struct node
{
datatype_t data;
struct node *next;
}linknode_t;
// 棧頭類型
typedef struct
{
linknode_t *top; // 棧頂指針
int n; // 記錄當前棧中元素的個數(shù)
}linkstack_t;
extern linkstack_t *create_empty_linkstack();
extern int is_empty_linkstack(linkstack_t *ls);
extern void push_linkstack(linkstack_t *ls, datatype_t data);
extern datatype_t pop_linkstack(linkstack_t *ls);
extern datatype_t get_top_data(linkstack_t *ls);
#endif
// linkstack.c
#include "linkstack.h"
linkstack_t *create_empty_linkstack()
{
linkstack_t *ls = NULL;
ls = (linkstack_t *)malloc(sizeof(linkstack_t));
if(NULL == ls)
{
printf("malloc linkstack_t *ls is fail!\n");
return NULL;
}
memset(ls, 0, sizeof(linkstack_t));
return ls;
}
// 判空
int is_empty_linkstack(linkstack_t *ls)
{
return ls->top == NULL ? 1 : 0;
}
// 入棧
void push_linkstack(linkstack_t *ls, datatype_t data)
{
linknode_t *temp = NULL;
temp = (linknode_t *)malloc(sizeof(linknode_t));
if(NULL == temp)
{
printf("malloc linknode_t *temp is fail!\n");
return;
}
temp->data = data;
// 將節(jié)點數(shù)據(jù)插入棧中
temp->next = ls->top;
ls->top = temp;
// 更新n 的值
ls->n++;
return;
}
datatype_t pop_linkstack(linkstack_t *ls)
{
linknode_t *temp = NULL;
datatype_t data;
// 保存要刪除的節(jié)點地址
temp = ls->top;
// 取出數(shù)據(jù)
data = temp->data;
// 更新頭部指針
ls->top = temp->next;
// 釋放 temp
free(temp);
temp = NULL;
// 更新 n 的值
ls->n--;
return data;
}
// 輸出棧頂元素
datatype_t get_top_data(linkstack_t *ls)
{
return ls->top->data;
}
// bitree.h
#ifndef __BITREE_H__
#define __BITREE_H__
#include
#include
#include
#define N 6
typedef char data_t;
typedef struct bitree
{
int n;
data_t data;
struct bitree *lchild;
struct bitree *rchild;
}bitree_t;
extern bitree_t *create_empty_bitree(int n);
extern void pre_order(bitree_t *bt);
extern void in_order(bitree_t *bt);
extern void post_order(bitree_t *bt);
#endif
// bitree.c
#include "bitree.h"
#include "linkstack.h"
bitree_t *create_empty_bitree(int n)
{
bitree_t *bt = NULL;
bt = (bitree_t *)malloc(sizeof(bitree_t));
if(NULL == bt)
{
printf("malloc bitree_t *bt is fail!\n");
return NULL;
}
memset(bt, 0, sizeof(bitree_t));
bt->n = n;
bt->lchild = bt->rchild = NULL;
printf("input %d node data : ", n);
scanf("%c", &(bt->data));
// 清除緩存區(qū)數(shù)據(jù)
while(getchar() != '\n');
// 左子節(jié)點存在條件
if(2 * n lchild = create_empty_bitree(2 * n);
}
// 右子節(jié)點存在條件
if(2 * n + 1 rchild = create_empty_bitree(2 * n + 1);
}
return bt;
}
// 前序非遞歸遍歷
void pre_order(bitree_t *bt)
{
if(bt == NULL) return;
linkstack_t *ls = create_empty_linkstack();
bitree_t *temp = bt;
while(temp != NULL || !is_empty_linkstack(ls))
{
while(temp != NULL)
{
printf("(%c : %d)", temp->data, temp->n);
push_linkstack(ls, temp);
temp = temp->lchild;
}
if(!is_empty_linkstack(ls))
{
temp = pop_linkstack(ls);
temp = temp->rchild;
}
}
free(ls);
return;
}
//中序遍歷
void in_order(bitree_t *root)
{
if(NULL == root) return ;
linkstack_t *ls = create_empty_linkstack();
bitree_t *temp = root;
while(temp != NULL || !is_empty_linkstack(ls))
{
if(temp != NULL)
{
push_linkstack(ls, temp);
temp = temp->lchild;
} else {
temp = pop_linkstack(ls);
printf("(%c : %d)",temp->data,temp->n);
temp = temp->rchild;
}
}
free(ls);
}
//后序遍歷
void post_order(bitree_t *root)
{
if(NULL == root)
return ;
linkstack_t *ls = create_empty_linkstack();
bitree_t *pre = NULL;
bitree_t *cur = NULL;
push_linkstack(ls, root);
while(!is_empty_linkstack(ls))
{
cur = get_top_data(ls);
// 以下情況，可以直接輸出值
// 左右孩子都為空
// 左右孩子存在，并且左孩子或右孩子都被訪問過
if((cur->lchild == NULL && cur->rchild == NULL) || (pre != NULL &&
(pre == cur->lchild || pre == cur->rchild)))
{
printf("(%c : %d) ",cur->data,cur->n);
pop_linkstack(ls);
pre = cur;
} else {
if(cur->rchild != NULL)
{
push_linkstack(ls, cur->rchild);
}
if(cur->lchild != NULL)
{
push_linkstack(ls, cur->lchild);
}
}
}
free(ls);
return;
}
// main.c
#include "bitree.h"
int main(int argc, const char *argv[])
{
bitree_t *bt = create_empty_bitree(1);
printf("pre_order : ");
pre_order(bt);
printf("\n");
printf("in_order : ");
in_order(bt);
printf("\n");
printf("post_order : ");
post_order(bt);
printf("\n");
return 0;
}
【圖片】
