学习目标：学会二叉树的构建与遍历

学习指导：帆神的代码

学习任务：

1. 抄写代码

2. 学习成果目录

   1全部代码

   2测试结果

   3图解

代码说明：

1. 二叉树的深度遍历使用了栈, 所以代码很简洁. 不使用栈的方式有相应代码数据结构 C 代码 6.x: 自己建栈实现二叉树遍历.
2. 层次遍历用到了队列. 这次故意把究竟分配得比较少, 看循环队列是否正常复用空间.
3. 从字符串构建二叉树也要用栈. 这里也可以看出二叉树的非压缩存储.
4. 二叉树（Binary tree）是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。二叉树特点是每个节点最多只能有两棵子树，且有左右之分   。二叉树是n个有限元素的集合，该集合或者为空、或者由一个称为根的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成，是有序树。当集合为空时，称该二叉树为空二叉树。在二叉树中，一个元素也称作一个节点。
5. 手动添加了前中后序遍历（我偏要用递归）。

学习时间：

2022.5.24

1全部代码

#include 
#include 
#include 

#define MAXSIZE 5

//二叉树的结构 
typedef struct BTnode
{
	char element;
	struct BTnode *left;
	struct BTnode *right;	
}*BTnodePtr;
//队列
typedef struct BTNodePtrQueue
{
	BTnodePtr *nodePtrs;
	int front;
	int rear;
}*QueuePtr;

QueuePtr initQueue()
{
	QueuePtr resultPtr = (QueuePtr)malloc(sizeof(struct BTNodePtrQueue));
	resultPtr->nodePtrs = (BTnodePtr*)malloc(MAXSIZE * (sizeof(BTnodePtr)));
	resultPtr->front = 0;
	resultPtr->rear = 1;
	return resultPtr;	
} 

int isQueueEmpty(QueuePtr paraQueuePtr)
{
	if ((paraQueuePtr->front + 1) % MAXSIZE == paraQueuePtr->rear) 
	{
		return 1;
	}
	
	return 0;
}

void enqueue(QueuePtr Queue,BTnodePtr newBTnodePtr)
{
	if((Queue->rear +1)%MAXSIZE == (Queue->front)%MAXSIZE )
	{
		printf("错误，队满，无法添加节点.n");
		return ; 
	}	
	Queue->nodePtrs [Queue->rear] = newBTnodePtr;
	Queue->rear = (Queue->rear+1)%MAXSIZE;
	printf("添加 节点%c 成功.n", newBTnodePtr->element);
	
} 

BTnodePtr deQueue(QueuePtr Queue)
{
	if(isQueueEmpty(Queue))
	{
		printf("错误，队空，无法删除节点.n");
		return Queue->nodePtrs [Queue->front];
	}
	Queue->front = (Queue->front +1)%MAXSIZE;
	printf("删除 节点%c 成功.n",Queue->nodePtrs [Queue->front]->element);
	
	return  Queue->nodePtrs [Queue->front];
} 

BTnodePtr constructBTnode(char newElement)
{
	BTnodePtr newPtr = (BTnodePtr)malloc(sizeof(struct BTnode));
	newPtr->element = newElement;
	newPtr->left = NULL;
	newPtr->right  = NULL;
	return newPtr;
}

BTnodePtr stringToBTree(char *newString)
{
	int i=0;
	char ch;
	
	//使用队列管理指针
	QueuePtr Queue = initQueue();
	
	BTnodePtr resultHeader;//根
	BTnodePtr tempParent,tempLeftChlid,tempRightChild;
	
	ch = newString[i];
	resultHeader = constructBTnode(ch);
	enqueue(Queue,resultHeader);
	
	while(!isQueueEmpty(Queue))
	{
		tempParent = deQueue(Queue);
		//左子节点
		i++;
		if(newString[i] == '#')
		{
			tempParent->left = NULL;
		}
		else
		{
			tempLeftChlid = constructBTnode(newString[i]);
			enqueue(Queue,tempLeftChlid);
			tempParent->left = tempLeftChlid;
		}
		//右子节点
		i++;
		if(newString[i] == '#')
		{
			tempParent->right = NULL;
		}
		else
		{
			tempRightChild = constructBTnode(newString[i]);
			enqueue(Queue,tempRightChild);
			tempParent->right = tempRightChild;
		}
		
	} 
	//返回根节点
	return resultHeader;	
}

void levelwise(BTnodePtr newTreePtr)
{
	char string[100];
	int i = 0;
	//使用队列管理指针
	QueuePtr Queue = initQueue();
	BTnodePtr tempNodePtr;
	
	enqueue(Queue,newTreePtr);
	while(!isQueueEmpty(Queue))
	{
		tempNodePtr = deQueue(Queue);
		string[i] = tempNodePtr->element ;
		i++;
		if(tempNodePtr->left != NULL)
		{
			enqueue(Queue,tempNodePtr->left);
		}
		if(tempNodePtr->right  != NULL)
		{
			enqueue(Queue,tempNodePtr->right);
		}
	}
	string[i] = '';
	printf("层序遍历:%sn",string);
} 

int preVisitBiTree(BTnodePtr newTreePtr)
{
	if(newTreePtr)
	{
		
		printf("%c",newTreePtr->element);
		
		
		preVisitBiTree(newTreePtr->left);
		
		
		preVisitBiTree(newTreePtr->right);
		
	}
	return 0;
}

int inVisitBiTree(BTnodePtr newTreePtr)
{
	if(newTreePtr)
	{
		
		preVisitBiTree(newTreePtr->left);
		
		
		
		printf("%c",newTreePtr->element);
		
		
		preVisitBiTree(newTreePtr->right);
		
	}
	return 0;
}

int postVisitBiTree(BTnodePtr newTreePtr)
{
	if(newTreePtr)
	{
		
		preVisitBiTree(newTreePtr->left);
		
		
		
		preVisitBiTree(newTreePtr->right);
		
		
		
		printf("%c",newTreePtr->element);
		
	}
	return 0;
}

void BinaryTreeTest(){
	printf("---- BinaryTreeTest 测试开始 ----n");
	printf("初始化二叉树n");
	BTnodePtr tempHeader;
	char* tempString = "acde#bf######";
	tempHeader = stringToBTree(tempString);
	printf("进行层序遍历n");
	levelwise(tempHeader);
	printf("n前序遍历:");
	preVisitBiTree(tempHeader);
	printf("n中序遍历:");
	inVisitBiTree(tempHeader);
	printf("n后序遍历:");
	postVisitBiTree(tempHeader);
	printf("n");
	printf("---- BinaryTreeTest 测试结束 ----n");
}

int main(){
	BinaryTreeTest();
	return 1;
}

2测试结果

---- BinaryTreeTest 测试开始 ----
初始化二叉树
添加 节点a 成功.
删除 节点a 成功.
添加 节点c 成功.
添加 节点d 成功.
删除 节点c 成功.
添加 节点e 成功.
删除 节点d 成功.
添加 节点b 成功.
添加 节点f 成功.
删除 节点e 成功.
删除 节点b 成功.
删除 节点f 成功.
进行层序遍历
添加 节点a 成功.
删除 节点a 成功.
添加 节点c 成功.
添加 节点d 成功.
删除 节点c 成功.
添加 节点e 成功.
删除 节点d 成功.
添加 节点b 成功.
添加 节点f 成功.
删除 节点e 成功.
删除 节点b 成功.
删除 节点f 成功.
层序遍历:acdebf

前序遍历:acedbf
中序遍历:ceadbf
后序遍历:cedbfa
---- BinaryTreeTest 测试结束 ----

3图解

层序遍历：把二叉树分层，然后每一层从左到右遍历