【C语言】【数据结构】二叉树、二叉排序树各种算法

1、二叉树的构建及遍历操作
构造二叉链表表示的二叉树：按先序次序输入二叉树中结点的值（一个字符），’#'字符表示空树。

#include <stdio.h>
#include <stdlib.h>
#define ERROR 0
#define OK 1

typedef int Status;
typedef char TElemType;
typedef struct BiTNode{
	TElemType data;
	struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;

//函数原型
Status CreateBiTree1(BiTree & );	//二叉树的构建(#表示空树)char
Status PrintElement1(TElemType );

int main()
{
	BiTree T;
	
	//二叉树
	printf("请按先序依次输入二叉树中各结点的值(#表示空树)：\n");
	if(!CreateBiTree1(T)) printf("Create Error!\n");
}

//二叉树的构建
Status CreateBiTree1(BiTree &T)
{
	TElemType ch;
	
	scanf("%c", &ch);
	if(ch == '#') T = NULL;
	else
	{
		T = (BiTNode *) malloc (sizeof(BiTNode));
		if(!T) return ERROR;
		T->data = ch;
		CreateBiTree1(T->lchild);
		CreateBiTree1(T->rchild);
	}
	return OK;
}

2、实现二叉排序树的各种算法
用函数实现如下二叉排序树算法：
（1） 插入新结点
（2） 前序、中序、后序遍历二叉树 （递归）

#include <stdio.h>
#include <stdlib.h>
#define ERROR 0
#define OK 1

typedef int Status;

typedef int TElemType;
typedef struct BiTNode{
	TElemType data;
	struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;

//函数原型（声明）
Status CreateBiTree(BiTree & );	//二叉排序树构建(输入二叉排序树结点个数)int
Status InsertBST(BiTree & , TElemType );//插入

Status PrintElement(TElemType );	//输出

//递归遍历 
Status PreOrderTraverse(BiTree , Status(* )(TElemType ));	//先序 
Status InOrderTraverse(BiTree , Status(* )(TElemType ));	//中序 
Status PostOrderTraverse(BiTree , Status(* )(TElemType ));	//后序 

int main()
{
	BiTree T;

	//二叉排序树
	if(!CreateBiTree(T)) printf("Create Error!\n");
	
	//递归遍历
	PreOrderTraverse(T, PrintElement);
	printf("\n");
	InOrderTraverse(T, PrintElement);
	printf("\n");
	PostOrderTraverse(T, PrintElement);
	printf("\n");

//二叉排序树构建 
Status CreateBiTree(BiTree &T)
{
	int n, i;
	TElemType e;
	
	T = NULL;												//注意！！！！ 
	printf("请输入二叉排序树结点个数：\n");
	scanf("%d", &n);
	printf("请输入%d个整数（用空格隔开）：\n", n);
	for(i=1; i<=n; i++)
	{
		scanf("%d", &e);
		if(!InsertBST(T, e)) return ERROR;
	}
	return OK;
}

Status InsertBST(BiTree &T, TElemType e)
{
	if(!T)
	{
		T = (BiTNode *) malloc (sizeof(BiTNode));
		if(!T) return ERROR;
		T->data = e;
		T->lchild = T->rchild = NULL;
		return OK;
	}
	else if(T->data == e) return ERROR;
	else if(T->data > e) InsertBST(T->lchild, e);
	else InsertBST(T->rchild, e);
}

//输出
Status PrintElement(TElemType e)
{
	printf("%d ", e);
	return OK;
}

//先序遍历（递归）
Status PreOrderTraverse(BiTree T, Status(*Visit)(TElemType e))
{
	if(T)
	{
		if(Visit(T->data))
			if(PreOrderTraverse(T->lchild, Visit))
				if(PreOrderTraverse(T->rchild, Visit)) return OK;
		return ERROR;
	}
	else return OK;
}

//中序遍历（递归）
Status InOrderTraverse(BiTree T, Status(*Visit)(TElemType e))
{
	if(T)
	{
		if(InOrderTraverse(T->lchild, Visit))
			if(Visit(T->data))
				if(InOrderTraverse(T->rchild, Visit)) return OK;
		return ERROR;
	}
	else return OK;
}

//后序遍历（递归）
Status PostOrderTraverse(BiTree T, Status(*Visit)(TElemType e))
{
	if(T)
	{
		if(PostOrderTraverse(T->lchild, Visit))
			if(PostOrderTraverse(T->rchild, Visit))
				if(Visit(T->data)) return OK;
		return ERROR;
	}
	else return OK;
}

（3） 中序遍历的非递归算法

#include <stdio.h>
#include <stdlib.h>
#define ERROR 0
#define OK 1

#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10

typedef int Status;

typedef int TElemType;
typedef struct BiTNode{
	TElemType data;
	struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;

//栈
typedef BiTree SElemType;
typedef struct SqStack{
	SElemType *base, *top;
	int stacksize;
}SqStack;

//函数上面有不重复
Status CreateBiTree(BiTree & );	//二叉排序树构建(输入二叉排序树结点个数)int
Status InsertBST(BiTree & , TElemType );//插入
Status PrintElement(TElemType );	//输出

//中序遍历非递归 函数原型（声明）
Status InitStack(SqStack &);
Status Push(SqStack &, SElemType );
Status Pop(SqStack &, SElemType &);
Status InOrderTraverse1(BiTree , Status(* )(TElemType ));

int main()
{
	BiTree T;

	//二叉排序树
	if(!CreateBiTree(T)) printf("Create Error!\n");
	
	InOrderTraverse1(T, PrintElement);	//中序遍历非递归 
	printf("\n");
}

//创建空栈
Status InitStack(SqStack &S)
{
	S.base = (SElemType *) malloc (STACK_INIT_SIZE * sizeof(SElemType));
	if(!S.base) return ERROR;
	S.top = S.base;
	S.stacksize = STACK_INIT_SIZE;
	return OK; 
}

//入栈
Status Push(SqStack &S, SElemType e)
{
	if(S.top-S.base>=S.stacksize)
	{
		S.base = (SElemType *) realloc (S.base, (S.stacksize + STACKINCREMENT) * sizeof(SElemType));
		if(!S.base) return ERROR;
		S.top = S.base + S.stacksize;
		S.stacksize += STACKINCREMENT;
	}
	*S.top++ = e;
	return OK;
}

//出栈
Status Pop(SqStack &S, SElemType &e)
{
	if(S.base == S.top) return ERROR;
	e = *--S.top;
	return OK;
}

//中序遍历非递归
Status InOrderTraverse1(BiTree T, Status(*Visit)(TElemType e))
{
	SqStack S;
	BiTree p=T;
	
	if(!InitStack(S)) return ERROR;
	while(p || S.base!=S.top)
	{
		if(p)
		{
			Push(S, p);
			p = p->lchild;
		}
		else
		{
			Pop(S, p);
			if(!Visit(p->data)) return ERROR;
			p = p->rchild;
		}
	}
	return OK;
}

（4） 层次遍历二叉树

#include <stdio.h>
#include <stdlib.h>
#define ERROR 0
#define OK 1

#define QUEUEMAXSIZE 100

typedef int Status;

typedef int TElemType;
typedef struct BiTNode{
	TElemType data;
	struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;

//队列
typedef BiTree QElemType;
typedef struct SqQueue{
	QElemType *base;
	int front, rear;
}SqQueue;

//函数上面有不重复
Status CreateBiTree(BiTree & );	//二叉排序树构建(输入二叉排序树结点个数)int
Status InsertBST(BiTree & , TElemType );//插入
Status PrintElement(TElemType );	//输出

//层次遍历
Status InitQueue(SqQueue &);
Status EnQueue(SqQueue &, QElemType );
Status DeQueue(SqQueue &, QElemType &);
Status LevelOrderTraverse(BiTree , Status(* )(TElemType ));

int main()
{
	BiTree T;

	//二叉排序树
	if(!CreateBiTree(T)) printf("Create Error!\n");

	LevelOrderTraverse (T, PrintElement);	//层次遍历 
	printf("\n");
}

//创建空队列
Status InitQueue(SqQueue &Q)
{
	Q.base = (QElemType *) malloc (QUEUEMAXSIZE * sizeof(QElemType));
	if(!Q.base) return ERROR;
	Q.front = Q.rear = 0;
	return OK;
}

//入队
Status EnQueue(SqQueue &Q, QElemType e)
{
	if((Q.rear+1)%QUEUEMAXSIZE == Q.front) return ERROR;
	Q.base[Q.rear] = e;
	Q.rear = (Q.rear+1)%QUEUEMAXSIZE;
	return OK;
}

//出队
Status DeQueue(SqQueue &Q, QElemType &e)
{
	if(Q.front == Q.rear) return ERROR;
	e = Q.base[Q.front];
	Q.front = (Q.front+1)%QUEUEMAXSIZE;
	return OK;
}

//层次遍历
Status LevelOrderTraverse(BiTree T, Status(*Visit)(TElemType e))
{
	SqQueue Q;
	BiTree p=T;
	
	if(!InitQueue(Q)) return ERROR;
	EnQueue(Q,p);
	while(Q.front!=Q.rear)
	{
		DeQueue(Q, p);
		if(!Visit(p->data)) return ERROR;
		if(p->lchild) EnQueue(Q, p->lchild);
		if(p->rchild) EnQueue(Q, p->rchild);
	}
	return OK;
}

（5） 在二叉树中查找给定关键字(函数返回值为成功1,失败0)

Status SearchBST(BiTree T, TElemType key, BiTree f, BiTree &p)	//f指向双亲（初始为空），p指向该结点 
{
	if(!T)
	{
		p = f;
		return ERROR;
	}
	else if(T->data == key)
	{
		p = T;
		return OK;
	}
	else if(T->data > key) SearchBST(T->lchild, key, T, p);
	else SearchBST(T->rchild, key, T, p);
}

（6） 交换各结点的左右子树

Status ExchangeBST(BiTree &T)
{
	BiTree p=NULL;
	
	if(T)
	{
		p = T->lchild;
		T->lchild = T->rchild;
		T->rchild = p;
		ExchangeBST(T->lchild);
		ExchangeBST(T->rchild);
	}
	return OK;
}

（7） 求二叉树的深度

int DepthBST(BiTree T)
{
	int ldep, rdep;
	
	if(!T) return 0;
	ldep = DepthBST(T->lchild);
	rdep = DepthBST(T->rchild);
	if(ldep > rdep) return ldep+1;
	else return rdep+1;
}

（8） 叶子结点数

int LeafBST(BiTree T)
{
	static int leaf=0;
	
	if(T)
	{
		if(!T->lchild && !T->rchild) leaf++;
		LeafBST(T->lchild);
		LeafBST(T->rchild);
	}
	return leaf;
}

总结：

#include <stdio.h>
#include <stdlib.h>
#define ERROR 0
#define OK 1

#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10

#define QUEUEMAXSIZE 100

typedef int Status;

typedef int TElemType;
typedef struct BiTNode{
	TElemType data;
	struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;

typedef BiTree SElemType;
typedef struct SqStack{
	SElemType *base, *top;
	int stacksize;
}SqStack;

typedef BiTree QElemType;
typedef struct SqQueue{
	QElemType *base;
	int front, rear;
}SqQueue;

Status CreateBiTree1(BiTree & );	//二叉树的构建(#表示空树)char
Status PrintElement1(TElemType );	//char

Status CreateBiTree(BiTree & );	//二叉排序树构建(输入二叉排序树结点个数)int
Status InsertBST(BiTree & , TElemType );

Status PrintElement(TElemType );	//int

//递归遍历 
Status PreOrderTraverse(BiTree , Status(* )(TElemType ));	//先序 
Status InOrderTraverse(BiTree , Status(* )(TElemType ));	//中序 
Status PostOrderTraverse(BiTree , Status(* )(TElemType ));	//后序 

//中序遍历非递归 
Status InitStack(SqStack &);
Status Push(SqStack &, SElemType );
Status Pop(SqStack &, SElemType &);
Status InOrderTraverse1(BiTree , Status(* )(TElemType ));

//层次 
Status InitQueue(SqQueue &);
Status EnQueue(SqQueue &, QElemType );
Status DeQueue(SqQueue &, QElemType &);
Status LevelOrderTraverse(BiTree , Status(* )(TElemType ));

Status SearchBST(BiTree , TElemType , BiTree , BiTree & );	//查找 

Status ExchangeBST(BiTree & );			//交换左右子树 

int DepthBST(BiTree );					//深度 

int LeafBST(BiTree );					//叶子结点数 

Status TreeCopy(BiTree , BiTree & ); 	//树的复制 

int TreeCount(BiTree )					//树的结点数

BiTNode* FindNode( BiTree Ta, int i)	//递归查找中序第i个结点 



int main()
{
	BiTree T, p, f=NULL;
	int n, i;
	TElemType e, key;
	
	/*
	//二叉树
	printf("请按先序依次输入二叉树中各结点的值(#表示空树)：\n");
	if(!CreateBiTree1(T)) printf("Create Error!\n");
	PreOrderTraverse(T, PrintElement1);
	printf("\n");
	InOrderTraverse(T, PrintElement1);
	printf("\n");
	PostOrderTraverse(T, PrintElement1);
	printf("\n");
	*/
	
	
	
	//二叉排序树
	if(!CreateBiTree(T)) printf("Create Error!\n");
	
	PreOrderTraverse(T, PrintElement);
	printf("\n");
	InOrderTraverse(T, PrintElement);
	printf("\n");
	PostOrderTraverse(T, PrintElement);
	printf("\n");
	
	InOrderTraverse1(T, PrintElement);	//中序遍历非递归 
	printf("\n");
	
	LevelOrderTraverse (T, PrintElement);	//层次遍历 
	printf("\n");
	
	printf("请输入待查找关键字：\n");	//查找1 
	scanf("%d", &key);
	printf("%d\n", SearchBST(T,key,f,p));
	
	printf("请输入待查找关键字：\n");	//查找2 
	scanf("%d", &key);
	printf("%d\n", SearchBST(T,key,f,p));
	
	
	//插入新结点 
	printf("请输入带插入的关键字：\n");
	scanf("%d", &e);
	InsertBST(T, e);
	PreOrderTraverse(T, PrintElement);
	printf("\n");
	InOrderTraverse(T, PrintElement);
	printf("\n");
	PostOrderTraverse(T, PrintElement);
	printf("\n");
	
	InOrderTraverse1(T, PrintElement);	//中序遍历非递归 
	printf("\n");
	
	LevelOrderTraverse (T, PrintElement);	//层次遍历 
	printf("\n");
	
	
	//交换左右子树
	ExchangeBST(T);	//第一次交换 
	PreOrderTraverse(T, PrintElement);
	printf("\n");
	InOrderTraverse(T, PrintElement);
	printf("\n");
	PostOrderTraverse(T, PrintElement);
	printf("\n");
	
	ExchangeBST(T);	//第二次交换 
	PreOrderTraverse(T, PrintElement);
	printf("\n");
	InOrderTraverse(T, PrintElement);
	printf("\n");
	PostOrderTraverse(T, PrintElement);
	printf("\n");
	
	
	printf("%d\n", DepthBST(T));	//深度 
	
	printf("%d\n", LeafBST(T));	//叶子结点数 
}




//二叉树的构建 
//typedef char TElemType;
Status CreateBiTree1(BiTree &T)
{
	TElemType ch;
	
	scanf("%c", &ch);
	if(ch == '#') T = NULL;
	else
	{
		T = (BiTNode *) malloc (sizeof(BiTNode));
		if(!T) return ERROR;
		T->data = ch;
		CreateBiTree1(T->lchild);
		CreateBiTree1(T->rchild);
	}
	return OK;
}

Status PrintElement1(TElemType e)
{
	printf("%c", e);
	return OK;
}




//二叉排序树构建 
Status CreateBiTree(BiTree &T)
{
	int n, i;
	TElemType e;
	
	T = NULL;												//注意！！！！ 
	printf("请输入二叉排序树结点个数：\n");
	scanf("%d", &n);
	printf("请输入%d个整数（用空格隔开）：\n", n);
	for(i=1; i<=n; i++)
	{
		scanf("%d", &e);
		if(!InsertBST(T, e)) return ERROR;
	}
	return OK;
}

Status InsertBST(BiTree &T, TElemType e)
{
	if(!T)
	{
		T = (BiTNode *) malloc (sizeof(BiTNode));
		if(!T) return ERROR;
		T->data = e;
		T->lchild = T->rchild = NULL;
		return OK;
	}
	else if(T->data == e) return ERROR;
	else if(T->data > e) InsertBST(T->lchild, e);
	else InsertBST(T->rchild, e);
}

Status PrintElement(TElemType e)
{
	printf("%d ", e);
	return OK;
}

Status PreOrderTraverse(BiTree T, Status(*Visit)(TElemType e))
{
	if(T)
	{
		if(Visit(T->data))
			if(PreOrderTraverse(T->lchild, Visit))
				if(PreOrderTraverse(T->rchild, Visit)) return OK;
		return ERROR;
	}
	else return OK;
}

Status InOrderTraverse(BiTree T, Status(*Visit)(TElemType e))
{
	if(T)
	{
		if(InOrderTraverse(T->lchild, Visit))
			if(Visit(T->data))
				if(InOrderTraverse(T->rchild, Visit)) return OK;
		return ERROR;
	}
	else return OK;
}

Status PostOrderTraverse(BiTree T, Status(*Visit)(TElemType e))
{
	if(T)
	{
		if(PostOrderTraverse(T->lchild, Visit))
			if(PostOrderTraverse(T->rchild, Visit))
				if(Visit(T->data)) return OK;
		return ERROR;
	}
	else return OK;
}

Status InitStack(SqStack &S)
{
	S.base = (SElemType *) malloc (STACK_INIT_SIZE * sizeof(SElemType));
	if(!S.base) return ERROR;
	S.top = S.base;
	S.stacksize = STACK_INIT_SIZE;
	return OK; 
}

Status Push(SqStack &S, SElemType e)
{
	if(S.top-S.base>=S.stacksize)
	{
		S.base = (SElemType *) realloc (S.base, (S.stacksize + STACKINCREMENT) * sizeof(SElemType));
		if(!S.base) return ERROR;
		S.top = S.base + S.stacksize;
		S.stacksize += STACKINCREMENT;
	}
	*S.top++ = e;
	return OK;
}

Status Pop(SqStack &S, SElemType &e)
{
	if(S.base == S.top) return ERROR;
	e = *--S.top;
	return OK;
}

Status InOrderTraverse1(BiTree T, Status(*Visit)(TElemType e))
{
	SqStack S;
	BiTree p=T;
	
	if(!InitStack(S)) return ERROR;
	while(p || S.base!=S.top)
	{
		if(p)
		{
			Push(S, p);
			p = p->lchild;
		}
		else
		{
			Pop(S, p);
			if(!Visit(p->data)) return ERROR;
			p = p->rchild;
		}
	}
	return OK;
}

Status InitQueue(SqQueue &Q)
{
	Q.base = (QElemType *) malloc (QUEUEMAXSIZE * sizeof(QElemType));
	if(!Q.base) return ERROR;
	Q.front = Q.rear = 0;
	return OK;
}

Status EnQueue(SqQueue &Q, QElemType e)
{
	if((Q.rear+1)%QUEUEMAXSIZE == Q.front) return ERROR;
	Q.base[Q.rear] = e;
	Q.rear = (Q.rear+1)%QUEUEMAXSIZE;
	return OK;
}

Status DeQueue(SqQueue &Q, QElemType &e)
{
	if(Q.front == Q.rear) return ERROR;
	e = Q.base[Q.front];
	Q.front = (Q.front+1)%QUEUEMAXSIZE;
	return OK;
}

Status LevelOrderTraverse(BiTree T, Status(*Visit)(TElemType e))
{
	SqQueue Q;
	BiTree p=T;
	
	if(!InitQueue(Q)) return ERROR;
	EnQueue(Q,p);
	while(Q.front!=Q.rear)
	{
		DeQueue(Q, p);
		if(!Visit(p->data)) return ERROR;
		if(p->lchild) EnQueue(Q, p->lchild);
		if(p->rchild) EnQueue(Q, p->rchild);
	}
	return OK;
}

Status SearchBST(BiTree T, TElemType key, BiTree f, BiTree &p)	//f指向双亲（初始为空），p指向该结点 
{
	if(!T)
	{
		p = f;
		return ERROR;
	}
	else if(T->data == key)
	{
		p = T;
		return OK;
	}
	else if(T->data > key) SearchBST(T->lchild, key, T, p);
	else SearchBST(T->rchild, key, T, p);
}

Status ExchangeBST(BiTree &T)
{
	BiTree p=NULL;
	
	if(T)
	{
		p = T->lchild;
		T->lchild = T->rchild;
		T->rchild = p;
		ExchangeBST(T->lchild);
		ExchangeBST(T->rchild);
	}
	return OK;
}

int DepthBST(BiTree T)
{
	int ldep, rdep;
	
	if(!T) return 0;
	ldep = DepthBST(T->lchild);
	rdep = DepthBST(T->rchild);
	if(ldep > rdep) return ldep+1;
	else return rdep+1;
}

int LeafBST(BiTree T)
{
	static int leaf=0;
	
	if(T)
	{
		if(!T->lchild && !T->rchild) leaf++;
		LeafBST(T->lchild);
		LeafBST(T->rchild);
	}
	return leaf;
}

3、二叉排序树的复制

Status TreeCopy( BiTree Ta,BiTree &Tb)//树的复制
{
	InsertBiTree(Tb, Ta->data);
	if(Ta->lchild) TreeCopy(Ta->lchild, Tb->lchild);
	if(Ta->rchild) TreeCopy(Ta->rchild, Tb->rchild);
	return OK;
}

4、计算二叉树的结点个数

int TreeCount( BiTree T)//树的结点数
{
	static int count=0;
	if(T!=NULL)
	{
		count++;
		TreeCount(T->lchild);
		TreeCount(T->rchild);
	}
	return count;
}

5、利用递归实现查找中序遍历序列中第i个结点

int main()
{
	BiTree p;
	scanf("%d",&i);
	a=0;
	if(i<1 || i>n) printf("Error\n");
	else
	{
		p=FindNode(T, i);
		printf("%d\n", p->data);
	}
	scanf("%d",&i);
	a=0;
	if(i<1 || i>n) printf("Error\n");
	else
	{
		p=FindNode(T, i);
		printf("%d\n", p->data);
	}
}
int a;	//全局变量
BiTNode* FindNode( BiTree Ta, int i) //查找中序遍历序列中第i个结点。
{
	//补充内容
	static BiTree p;
	if(Ta==NULL) return ERROR;
	FindNode(Ta->lchild, i);
	a++;
	if(a==i) p = Ta;
	FindNode(Ta->rchild, i);
	return p;
}