首先来介绍一下二叉树的概念和某些性质：
- 非空二叉树第n层上至多有2^(n-1)个元素；
- 深度为h的二叉树至多有2^h-1个结点；
- 满二叉树：所有叶结点都在同一层，且非叶结点度数为2；在满二叉树中若其深度为h，则其所包含的结点数必为2^h-1；
- 完全二叉树：概念就不赘述了；对于完全二叉树，设一个结点为i，则其父结点为i/2,2i为左子结点，2i+1为右子结点。
存储结构：
顺序存储：
遍历速度快，但占空间大，是非主流二叉树，一般用链式存储。
#define LENGTH 100
typedef char datatype;
typedef struct node{
datatype data;
int lchild, rchild;
int parent;
} Node;
Node tree[LENGTH];
int length;
int root;
链式存储：
typedef char datatype;
typedef struct BinNode{
datatype data;
struct BinNode* lchild;
struct BinNode* rchild;
} BinNode;
typedef BinNode* bintree;
二叉树遍历
递归算法
void preorder(bintree t){
if(t){
printf("%c ",t->data);
preorder(t->lchild);
preorder(t->rchild);
}
}
非递归算法
因为遍历过根结点之后还要回来，所以必须将其存起来。考虑到后进先出的特点，选用栈存储。数量确定，以顺序栈存储。
#define SIZE 100
typedef struct stack{
bintree data[SIZE];
int tag[SIZE]; //为后续遍历准备
int top; //top为数组下标
} seqstack;
void push(stack* s, bintree t){
if(s->top == SIZE){
printf("the stack is full\n");
}else{
s->top++;
s->data[s->top]=t;
}
}
bintree pop(stack* s){
if(s->top == -1)
return NULL;
else{
s->top--;
return s->data[s->top+1];
}
}
前序遍历
void preorder(bintree t){
stack s;
s.top = -1;
if(!t){
printf("the tree is empty\n");
}else{
while(t || s.top != -1){
while(t){
printf("%c ", t->data);
push(&s,t);
t = t->lchild;
}
t=pop(&s);
t = t->rchild;
}
}
}
中序遍历
void midorder(bintree t){
stack s;
s.top = -1;
if(t){
while(t || s.top != -1){
while(t){
push(&s, t);
t = t->lchild;
}
t = pop(&s);
printf("%c ",t->data);
t = t->rchild;
}
}
}
后序遍历
后序遍历在最后要访问根结点，所以要访问根结点两次。因此在这里设定一个标志位。
void postorder(bintree t){
stack s; s.top = -1;
if(t){
while(t || s.top != -1){
while(t){
push(&s, t);
s.tag[s.top] = 0; //0为第一次访问，1为第二次访问
t = t->lchild;
}
if(s.tag[s.top]==0){
t=s.data[s.top];
s.tag[s.top] = 1;
t = t->rchild;
}else{
while(s.tag[s.top]==1){
t = pop(&s);
printf("%c ",t->data);
}
t = NULL; //需将t置为空，跳过向左走，直接向右走。
}
}
}
}
层次遍历
队列定义：
#define MAX 1000
typedef struct queue{
bintree data[MAX];
int front;
int rear;
}queue;
void enter(queue* q, bintree t){
if(q->rear == MAX){
printf("the queue is full\n");
}else{
q->data[q->rear] = t;
t->rear++;
}
}
bintree del(queue* q){
if(q->front == q->rear)
return NULL;
else{
q->front++;
return q->data[q->front-1];
}
}
层次遍历实现：
void level(bintree t){
queue q;
bintree temp;
q.front = q.rear = 0;
if(t){
enter(&q,t);
while(q.front != q.rear){
t = del(&q);
printf("%c ",t->data);
if(t->lchild)
enter(&q, t->lchild);
if(t->rchild)
enter(&q, t->rchild);
}
}
}