数据结构学习，二叉树

2023-11-19 14:53:52

目录

预先要引用的头文件以及宏定义

需要用到的其他数据结构（链栈和链队列）

所使用的二叉树的结构（二叉链表）

其基本操作接口

基本操作

创建一颗空二叉树

创建一颗二叉树，其中根结点的值为e，L和R分别为左子树和右子树

销毁二叉树

对二叉树判空

将一颗二叉树T分解成根，左子树，右子树3个部分    

替换左子树，若T非空，则用LT替换T的左子树，并用LT返回T的原有左子树

替换右子树，若T非空，则用RT替换T的右子树，并用RT返回T的原有右子树

进阶操作

//访问函数

递归遍历

先序遍历二叉树

中序遍历二叉树

后序遍历二叉树

返回二叉树深度

用count对二叉树T的叶子计数

先序构造二叉树

非递归遍历

层次遍历

先序非递归遍历

中序非递归遍历

后序非递归遍历

一些接口的测试

预先要引用的头文件以及宏定义

#include<stdio.h>
#include<iostream>

//
using namespace std;

#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -1
#define UNSUCCESS 0
#define SUCCESS 1

需要用到的其他数据结构（链栈和链队列）

//链栈
typedef struct LSNode {
	ElemType data;
	struct LSNode* next;
}LSNode,*LStack;

void InitStack_LS(LStack& S);				//初始化链栈
void DestroyStack_LS(LStack& S);			//销毁链栈
Status StackEmpty_LS(LStack S);				//判断栈是否为空，空返回TRUE，否则返回FALSE
Status Push_LS(LStack& S, ElemType e);		//元素e压入栈
Status Pop_LS(LStack& S, ElemType& e);		//栈S的栈顶元素出栈并用e返回
Status GetTop_LS(LStack S, ElemType& e);	//取栈S的栈顶元素，并用e返回

typedef struct LQNode {
	ElemType data;
	struct LQNode* next;
}LQNode,*QueuePtr;
typedef struct {
	QueuePtr front;	//队头指针
	QueuePtr rear;	//队尾指针
}LQueue;

void InitQueue_LQ(LQueue& Q);				//初始化队列Q
void DestroyQueue_LQ(LQueue& Q);			//销毁队列Q
Status EnQueue_LQ(LQueue& Q, ElemType e);	//在队列Q的队尾中插入元素e
Status DeQueue_LQ(LQueue& Q, ElemType& e);	//队列Q非空，删除队头元素，用e返回其值，返回OK，否则ERROR；

想看这两个数据结构的实现可以看

数据结构学习，链队列

数据结构学习，链栈

所使用的二叉树的结构（二叉链表）

typedef struct BITNode {
	TElemType data;            //数据域
	struct BITNode* lchild;    //左孩子
	struct BITNode* rchild;    //右孩子
}BiTNode, * BiTree, * ElemType;

其基本操作接口

void InitBiTree(BiTree& T);							//创建一颗空二叉树
BiTree MakeBiTree(TElemType e, BiTree L, BiTree R);	//创建一颗二叉树，其中根结点的值为e，L和R分别为左子树和右子树
void DestroyBitree(BiTree& T);						//销毁二叉树
Status BiTreeEmpty(BiTree T);						//对二叉树判空
Status BreakBiTree(BiTree& T, BiTree& L, BiTree& R);//将一颗二叉树T分解成根，左子树，右子树3个部分	
Status ReplaceLeft(BiTree& T, BiTree& LT);			//替换左子树，若T非空，则用LT替换T的左子树，并用LT返回T的原有左子树
Status ReplaceRight(BiTree& T, BiTree& RT);			//替换右子树，若T非空，则用RT替换T的右子树，并用RT返回T的原有右子树
//进阶操作
Status visit(TElemType a);
//递归遍历
Status PreOrderTraverse(BiTree T, Status(*visit)(TElemType));	//先序
Status InOrderTraverse(BiTree T, Status(*visit)(TElemType));	//中序
Status PostOrderTraverse(BiTree T, Status(*visit)(TElemType));	//后序
int BiTreeDepth(BiTree T);										//返回二叉树深度
void CountLeaf(BiTree T, int& count);							//用count对二叉树T的叶子计数
BiTree CreateBiTree(char* defBT, int& i);						//先序构造二叉树
//非递归遍历
void LevelOrderTraverse(BiTree T, Status(*visit)(TElemType));	//层次遍历
Status PreOrderTraverse_U(BiTree T, Status(*visit)(TElemType));	//先序非递归
Status InOrderTraverse_U(BiTree T, Status(*visit)(TElemType));	//中序非递归
Status PostOrderTraverse_U(BiTree T, Status(*visit)(TElemType));//后序非递归

基本操作

创建一颗空二叉树

void InitBiTree(BiTree& T)
{
	T = NULL;
}

创建一颗二叉树，其中根结点的值为e，L和R分别为左子树和右子树

BiTree MakeBiTree(TElemType e, BiTree L, BiTree R)
{
	BiTree T;
	T = (BiTree)malloc(sizeof(BiTNode));
	if (T != NULL)
	{
		T->data = e;
		T->lchild = L;
		T->rchild = R;
		return T;
	}
	else
	{
		return NULL;
	}
}

销毁二叉树

void DestroyBitree(BiTree& T)
{
	if (T != NULL)//简单粗暴的递归
	{
		DestroyBitree(T->lchild);
		DestroyBitree(T->rchild);
		free(T);
	}
}

对二叉树判空

Status BiTreeEmpty(BiTree T)
{
	if (T == NULL)
	{
		return TRUE;
	}
	else
	{
		return ERROR;
	}
}

将一颗二叉树T分解成根，左子树，右子树3个部分    

Status BreakBiTree(BiTree& T, BiTree& L, BiTree& R)
{
	if (T != NULL)
	{
		L = T->lchild;
		R = T->rchild;
		T->lchild = NULL;
		T->rchild = NULL;
		return OK;
	}
	else
	{
		return OVERFLOW;
	}
}

替换左子树，若T非空，则用LT替换T的左子树，并用LT返回T的原有左子树

Status ReplaceLeft(BiTree& T, BiTree& LT)
{
	BiTree temp;
	if (T != NULL)
	{
		temp = T->lchild;
		T->lchild = LT;
		LT = temp;
		return OK;
	}
	else
	{
		return ERROR;
	}
}

替换右子树，若T非空，则用RT替换T的右子树，并用RT返回T的原有右子树

Status ReplaceRight(BiTree& T, BiTree& RT)
{
	BiTree temp;
	if (T != NULL)
	{
		temp = T->rchild;
		T->rchild = RT;
		RT = temp;
		return OK;
	}
	else
	{
		return ERROR;
	}
}

进阶操作

//访问函数

Status visit(TElemType a)
{
	if (a != '#')
	{
		printf("%c", a);
		return OK;
	}
	else
	{
		return ERROR;
	}
}

递归遍历

先序遍历二叉树

Status PreOrderTraverse(BiTree T, Status(*visit)(TElemType))
{
	if (T == NULL)
	{
		return OK;
	}
	if (visit(T->data) == ERROR)//根
	{
		return ERROR;
	}
	if (PreOrderTraverse(T->lchild, visit) == ERROR)//左
	{
		return ERROR;
	}
	if (PreOrderTraverse(T->rchild, visit) == ERROR)//右
	{
		return ERROR;
	}
	return OK;
}

中序遍历二叉树

Status InOrderTraverse(BiTree T, Status(*visit)(TElemType))
{
	if (T == NULL)
	{
		return OK;
	}
	if (InOrderTraverse(T->lchild, visit) == ERROR)//左
	{
		return ERROR;
	}
	if (visit(T->data) == ERROR)//根
	{
		return ERROR;
	}
	if (InOrderTraverse(T->rchild, visit) == ERROR)//右
	{
		return ERROR;
	}
	return OK;
}

后序遍历二叉树

Status PostOrderTraverse(BiTree T, Status(*visit)(TElemType))
{
	if (T == NULL)
	{
		return OK;
	}
	if (PostOrderTraverse(T->lchild, visit) == ERROR)//左
	{
		return ERROR;
	}
	if (PostOrderTraverse(T->rchild, visit) == ERROR)//右
	{
		return ERROR;
	}
	if (visit(T->data) == ERROR)//根
	{
		return ERROR;
	}
	return OK;
}

返回二叉树深度

int BiTreeDepth(BiTree T)
{
	int depthLeft, depthRight;
	if (T == NULL)
	{
		return 0;
	}
	else
	{
		depthLeft = BiTreeDepth(T->lchild);
		depthRight = BiTreeDepth(T->rchild);
		return 1 + (depthLeft > depthRight ? depthLeft : depthRight);
	}
}

用count对二叉树T的叶子计数

void CountLeaf(BiTree T, int& count)
{
	if (T != NULL)
	{
		if (T->lchild == NULL && T->rchild == NULL)
		{
			count++;
		}
		CountLeaf(T->lchild, count);
		CountLeaf(T->rchild, count);
	}
}

先序构造二叉树

BiTree CreateBiTree(char* defBT, int& i)
{
	BiTree T;
	TElemType ch;
	ch = defBT[i++];
	if (ch == '#')
	{
		InitBiTree(T);
	}
	else
	{
		T = MakeBiTree(ch, NULL, NULL);
		T->lchild = CreateBiTree(defBT, i);
		T->rchild = CreateBiTree(defBT, i);
	}
	return T;
}

非递归遍历

层次遍历

void LevelOrderTraverse(BiTree T, Status(*visit)(TElemType))
{
	if (T != NULL)
	{
		LQueue Q;
		InitQueue_LQ(Q);
		BiTree p = T;
		visit(p->data);
		EnQueue_LQ(Q, p);
		while (DeQueue_LQ(Q, p) == OK)
		{
			if (p->lchild != NULL)
			{
				visit(p->lchild->data);
				EnQueue_LQ(Q, p->lchild);

			}
			if (p->rchild != NULL)
			{
				visit(p->rchild->data);
				EnQueue_LQ(Q, p->rchild);
			}
		}
		DestroyQueue_LQ(Q);
	}
}

下面三个非递归遍历可以看

我只能说，这是个大佬数据结构学习，二叉树https://blog.csdn.net/Benja_K/article/details/88389039

先序非递归遍历

Status PreOrderTraverse_U(BiTree T, Status(*visit)(TElemType))
{
	BiTree p;
	p = T;
	LStack S;
	InitStack_LS(S);
	while (p != NULL || StackEmpty_LS(S) != TRUE)
	{
		if (p != NULL)
		{
			Push_LS(S, p);
			visit(p->data);
			p = p->lchild;
		}
		else
		{
			Pop_LS(S, p);
			p = p->rchild;
		}
	}
	DestroyStack_LS(S);
	return OK;
}

中序非递归遍历

Status InOrderTraverse_U(BiTree T, Status(*visit)(TElemType))
{
	BiTree p;
	p = T;
	LStack S;
	InitStack_LS(S);
	while (p != NULL || StackEmpty_LS(S) != TRUE)
	{
		if (p != NULL)
		{
			Push_LS(S, p);		
			p = p->lchild;
		}
		else
		{
			Pop_LS(S, p);
			visit(p->data);
			p = p->rchild;
		}
	}
	DestroyStack_LS(S);
	return OK;
}

后序非递归遍历

Status PostOrderTraverse_U(BiTree T, Status(*visit)(TElemType))
{
	LStack S;
	InitStack_LS(S);
	int top = -1;
	int Stack[15];   
	BiTNode* p = T;
	while (p != NULL || StackEmpty_LS(S) != TRUE)
	{
		if (p != NULL) {     
			Push_LS(S, p);
			top++;
			Stack[top] = 1;
			p = p->lchild;
		}
		else 
		{
			if (Stack[top] == 1) 
			{  
				GetTop_LS(S, p);
				Stack[top] = 2;
				p = p->rchild;
			}
			else 
			{         
				Pop_LS(S, p);
				top--;
				visit( p->data);    
				p = NULL;      
			}
		}
	}
	DestroyStack_LS(S);
	return OK;
}

一些接口的测试

所测试的二叉树为

int main()
{
	//ABEF#G###C#DHI####CF#B###//先序
	char defBT[100] = { '#' };
	if (defBT != NULL)
	{
		printf("将要输入的树转化为二叉树T并先序输入\n");
		printf("其中#表示结点为空\n");
		//scanf("%s", defBT);
		cin >> defBT;
		getchar();
	}
	else
	{
		return ERROR;
	}
	BiTree T;
	int i = 0;
	T = CreateBiTree(defBT, i);
	PreOrderTraverse(T, visit);
	cout << "\n";
	InOrderTraverse(T, visit);
	cout << "\n";
	PostOrderTraverse(T, visit);
	cout << "\n";
	
	cout << BiTreeDepth(T) << endl;
	int j = 0;
	CountLeaf(T, j);
	cout << j << endl;
	LevelOrderTraverse(T, visit);
	cout << "\n";
	PreOrderTraverse_U(T, visit);
	cout << "\n";
	InOrderTraverse_U(T, visit);
	cout << "\n";
	PostOrderTraverse_U(T, visit);
}

数据结构学习，二叉树

 二叉树还有许多的操作，如二叉树的复制，二叉树的查找，二叉树有多少个结点，判别这个二叉树是不是完全二叉树等，这就留给大家自己实现了。

上一篇：MyBatis入门


下一篇：Java Caching JSR107介绍（五）