目录

递归创建二叉树

二叉树遍历

先序遍历递归算法

中序遍历递归算法

后序遍历递归算法

先序遍历非递归算法

中序遍历非递归算法

层序遍历

递归创建二叉树

//二叉树结构体类型
typedef struct BiTnode
{
	char data;
	struct BiTnode* lchild, * rchild;//左孩子右孩子指针
}BiTnode;

//创建二叉树
void CreateBiTree(BiTnode* T)
{	
	char ch;
	scanf("%c", &ch);
	if (ch == '#')
	{
		T = NULL;
	}
	else
	{
		T = (BiTnode*)malloc(sizeof(BiTnode));
		T->data = ch;
		CreateBiTree(T->lchild);
		CreateBiTree(T->rchild);
	}
}

二叉树遍历

先序遍历：DLR的顺序

中序遍历：LRD的顺序

后序遍历：LRD的顺序

层序遍历：逐层从左往右遍历

例如：

先序遍历：-+a*b-cd/ef

中序遍历：a+b*c-d-e/f

后序遍历：abcd-*+ef/-

层序遍历：-+/a*efb-cd

先序遍历递归算法

//递归先序遍历
void HouOrderTraverse(BiTnode* t)
{
	if (t == NULL)
	{
		return;
	}
    printf("%c", t->data);
	HouOrderTraverse(t->lchild);
	HouOrderTraverse(t->rchild);
	
}

中序遍历递归算法

//递归中序遍历
void HouOrderTraverse(BiTnode* t)
{
	if (t == NULL)
	{
		return;
	}
	HouOrderTraverse(t->lchild);
	printf("%c", t->data);
	HouOrderTraverse(t->rchild);

}

后序遍历递归算法

//递归后序遍历
void HouOrderTraverse(BiTnode* t)
{
	if (t == NULL)
	{
		return;
	}
	HouOrderTraverse(t->lchild);
	HouOrderTraverse(t->rchild);
	printf("%c", t->data);
}

先序遍历非递归算法

#include<stdio.h>
#include<stdlib.h>
#define MAX_size 10



//栈结构体
typedef struct {
	BiTnode** base;//二级指针，指向结点指针
	BiTnode** top;
	int size;
}Stack;



//初始化栈
void InitStack(Stack* s)
{
	s->base = (BiTnode**)malloc(MAX_size * sizeof(BiTnode*));
	s->top = s->base;
	s->size = MAX_size;
}



//销毁栈
void DstroyStack(Stack* s)
{
	while (s->size)
	{
		free(s->base);
		s->size--;
	}
}



//判断栈空
int IsEmpty(Stack s)
{
	if (s.top == s.base)
	{
		return 1;
	}
	return 0;
}




//入栈
void Push(Stack* s, BiTnode* x)
{
	//判断栈满
	if (s->top - s->base >= s->size)
	{
		//栈满，返回
		return;
	}
	*s->top = x;
	s->top++;
}




//出栈
void Pop(Stack* s, BiTnode* p)
{
	if (s->top == s->base)
	{
		//栈空
		exit(0);
	}
	s->top--;
	p = *s->top;
}




//非递归先序遍历
void InOderTraverse(BiTnode*t)
{
	Stack p;
	InitStack(&p);
	
	while (t || !IsEmpty(p))
	{
		if (t)
		{
			printf("%c", t->data);
			Push(&p, t);

			t = t->lchild;
		}
		else {
			Pop(&p,t);

			t = t->rchild;
		}
	}
	DstroyStack(&p);
}

中序遍历非递归算法

#include<stdio.h>
#include<stdlib.h>
#define MAX_size 10



//栈结构体
typedef struct {
	BiTnode** base;//二级指针，指向结点指针
	BiTnode** top;
	int size;
}Stack;



//初始化栈
void InitStack(Stack* s)
{
	s->base = (BiTnode**)malloc(MAX_size * sizeof(BiTnode*));
	s->top = s->base;
	s->size = MAX_size;
}



//销毁栈
void DstroyStack(Stack* s)
{
	while (s->size)
	{
		free(s->base);
		s->size--;
	}
}



//判断栈空
int IsEmpty(Stack s)
{
	if (s.top == s.base)
	{
		return 1;
	}
	return 0;
}




//入栈
void Push(Stack* s, BiTnode* x)
{
	//判断栈满
	if (s->top - s->base >= s->size)
	{
		//栈满，返回
		return;
	}
	*s->top = x;
	s->top++;
}




//出栈
void Pop(Stack* s, BiTnode* p)
{
	if (s->top == s->base)
	{
		//栈空
		exit(0);
	}
	s->top--;
	p = *s->top;
}




//非递归先序遍历
void InOderTraverse(BiTnode*t)
{
	Stack p;
	InitStack(&p);
	
	while (t || !IsEmpty(p))
	{
		if (t)
		{

			Push(&p, t);
			t = t->lchild;
		}
		else {
			Pop(&p,t);
			printf("%c", t->data);
			t = t->rchild;
		}
	}
	DstroyStack(&p);
}

层序遍历

typedef struct Queue
{
	BiTnode** base;
	int front;
	int rear;
}Queue;


//初始化队列
void TnitQueue(Queue& p)
{
	p.base = (BiTnode**)malloc(MAX_size * sizeof(BiTnode*));
	p.front = 0;
	p.rear = 0;
}



//入列
void InQueue(Queue& p, BiTnode* e)
{
	if ((p.rear + 1) % MAX_size == p.front)
	{
		printf("队列满了，无法入列");
		return;
	}//队满
	p.base[p.rear] = e;
	p.rear = (p.rear + 1) % MAX_size;
}
//出列
void DeQueue(Queue& p, BiTnode* &e)
{
	//判断栈空
	if (p.front == p.rear)
	{
		printf("队列为空，无法出列");
		return;
	}
	e = p.base[p.front];
	p.front = (p.front + 1) % MAX_size;
}


//层序遍历
void LeveOrder(BiTnode* t)
{
	Queue q;
	BiTnode* p;
	if (t)
	{
		TnitQueue(q);
		InQueue(q, t);//根结点入队
		while (q.rear != q.front)//队列不为空
		{
			DeQueue(q, p);
			printf("%c", p->data);//出队访问
			if(p->lchild)
				InQueue(q, p->lchild);//左孩子入队
			if(p->rchild)
				InQueue(q, p->rchild);//右孩子入队
		}
	}
}