数据结构,二叉树及其遍历

总代码

#include 
#include 
#include 

#define MAXSIZE 5

//对于二叉树，我们一般都是用链式存储，顺序存储的话会造成很多空间的浪费 
typedef struct BTNode
{
	char element;
	struct BTNode *left;
	struct BTNode *right;
}*BTNodePtr;

//这里队列就用的是顺序循环存储啦 
typedef struct BTNodeQueue
{
	
	BTNodePtr* nodePtrs;
	int front;
	int rear;
}*BTNodeQueuePtr;

BTNodeQueuePtr BTNodeQueueInit()
{
	BTNodeQueuePtr resultPtr = (BTNodeQueuePtr)malloc(sizeof(struct BTNodeQueue)); 
	//不要忘记给动态数组malloc哦 
	resultPtr->nodePtrs = (BTNodePtr*)malloc(MAXSIZE * sizeof(struct BTNode));
	 
	
	resultPtr->front = 0;
	resultPtr->rear = 0;
	
	return resultPtr; 
}

BTNodePtr constructNode(char paraChar)
{
	BTNodePtr tempPtr = (BTNodePtr)malloc(sizeof(struct BTNode));
	
	tempPtr->element = paraChar;
	tempPtr->left = NULL;
	tempPtr->right = NULL;
	
	return tempPtr;
}

void enqueue(BTNodeQueuePtr paraQueuePtr,BTNodePtr paraPtr)
{
	if((paraQueuePtr->rear+1) % MAXSIZE == (paraQueuePtr->front) % MAXSIZE)
	{
		printf("队列满了，无法入队n");
		return ;
	}
	
	paraQueuePtr->nodePtrs[paraQueuePtr->rear % MAXSIZE] = paraPtr;
	paraQueuePtr->rear = (paraQueuePtr->rear+1) % MAXSIZE;
}

BTNodePtr dequeue(BTNodeQueuePtr paraQueuePtr)
{
	if(paraQueuePtr->front == paraQueuePtr->rear)
	{
		printf("队列为空，无法出队n");
		return ; 
	}
	BTNodePtr tempPtr = paraQueuePtr->nodePtrs[paraQueuePtr->front % MAXSIZE];
	paraQueuePtr->front = (paraQueuePtr->front+1) % MAXSIZE;
	
	return tempPtr;
}

BTNodePtr stringToBT(char *paraString)
{
	int i = 0;
	char ch;
	BTNodeQueuePtr resultQueuePtr = BTNodeQueueInit();
	BTNodePtr headerPtr,tempParent,leftChild,rightChild;
	
	ch = paraString[i];
	i ++;
	
	headerPtr = constructNode(ch);
	enqueue(resultQueuePtr,headerPtr);
	
	while(resultQueuePtr->front != resultQueuePtr->rear)
	{
		tempParent = dequeue(resultQueuePtr);
		
		//1.下一个字符为左孩子
		ch = paraString[i];
		i ++;
		if(ch == '#')
		{
			//实际上初始化的时候本来就为NULL 
			tempParent->left = NULL;
		} 
		else
		{
			leftChild = constructNode(ch);
			tempParent->left = leftChild;
			enqueue(resultQueuePtr,leftChild);
		}
		
		//2.下一个字符为右孩子 
		ch = paraString[i];
		i ++;
		if(ch == '#')
		{
			//实际上初始化的时候本来就为NULL 
			tempParent->right = NULL;
		} 
		else
		{
			rightChild = constructNode(ch);
			tempParent->right  = rightChild;
			enqueue(resultQueuePtr,rightChild);
		}
	}
	
	return headerPtr;
}

void levelwise(BTNodePtr paraHeader)
{
	int i = 0;
	char ch;
	char tempString[100];
	BTNodeQueuePtr resultQueuePtr = BTNodeQueueInit();
	BTNodePtr tempNodePtr;	

	enqueue(resultQueuePtr,paraHeader);
	
	while(resultQueuePtr->front != resultQueuePtr->rear)
	{
		tempNodePtr = dequeue(resultQueuePtr);
		
		tempString[i] = tempNodePtr->element;
		i++;
		
		if (tempNodePtr->left != NULL)
		{
			enqueue(resultQueuePtr, tempNodePtr->left);
		}
		
		if (tempNodePtr->right != NULL)
		{
			enqueue(resultQueuePtr, tempNodePtr->right);
		}
	}
	
	tempString[i] = '';
	printf("%s",tempString);
	
}

void preorder(BTNodePtr paraHeader)
{
	if(paraHeader == NULL)
	{
		return ;
	}
	
	printf("%c",paraHeader->element);
	preorder(paraHeader->left);
	preorder(paraHeader->right);
}

void inorder(BTNodePtr paraHeader)
{
	if(paraHeader == NULL)
	{
		return ;
	}
	
	inorder(paraHeader->left);
	printf("%c",paraHeader->element);
	inorder(paraHeader->right);
}

void postorder(BTNodePtr paraHeader)
{
	if(paraHeader == NULL)
	{
		return ;
	}
	
	postorder(paraHeader->left);
	postorder(paraHeader->right);
	printf("%c",paraHeader->element);
}

int main(){
	BTNodePtr tempHeader;
	tempHeader = constructNode('c');
	printf("There is only one node. Preorder visit: ");
	preorder(tempHeader);
	printf("rn");

	char* tempString = "acde#bf######";
	tempHeader = stringToBT(tempString);
	printf("Preorder: ");
	preorder(tempHeader);
	printf("rn");
	printf("Inorder: ");
	inorder(tempHeader);
	printf("rn");
	printf("Postorder: ");
	postorder(tempHeader);
	printf("rn");
	printf("Levelwise: ");
	levelwise(tempHeader);
	printf("rn");

	return 0;
}

出队和入队

void enqueue(BTNodeQueuePtr paraQueuePtr,BTNodePtr paraPtr)
{
	if((paraQueuePtr->rear+1) % MAXSIZE == (paraQueuePtr->front) % MAXSIZE)
	{
		printf("队列满了，无法入队n");
		return ;
	}
	
	paraQueuePtr->nodePtrs[paraQueuePtr->rear % MAXSIZE] = paraPtr;
	paraQueuePtr->rear = (paraQueuePtr->rear+1) % MAXSIZE;
}

BTNodePtr dequeue(BTNodeQueuePtr paraQueuePtr)
{
	if(paraQueuePtr->front == paraQueuePtr->rear)
	{
		printf("队列为空，无法出队n");
		return ; 
	}
	BTNodePtr tempPtr = paraQueuePtr->nodePtrs[paraQueuePtr->front % MAXSIZE];
	paraQueuePtr->front = (paraQueuePtr->front+1) % MAXSIZE;
	
	return tempPtr;
}

字符串变二叉树

BTNodePtr stringToBT(char *paraString)
{
	int i = 0;
	char ch;
	BTNodeQueuePtr resultQueuePtr = BTNodeQueueInit();
	BTNodePtr headerPtr,tempParent,leftChild,rightChild;
	
	ch = paraString[i];
	i ++;
	
	headerPtr = constructNode(ch);
	enqueue(resultQueuePtr,headerPtr);
	
	while(resultQueuePtr->front != resultQueuePtr->rear)
	{
		tempParent = dequeue(resultQueuePtr);
		
		//1.下一个字符为左孩子
		ch = paraString[i];
		i ++;
		if(ch == '#')
		{
			//实际上初始化的时候本来就为NULL 
			tempParent->left = NULL;
		} 
		else
		{
			leftChild = constructNode(ch);
			tempParent->left = leftChild;
			enqueue(resultQueuePtr,leftChild);
		}
		
		//2.下一个字符为右孩子 
		ch = paraString[i];
		i ++;
		if(ch == '#')
		{
			//实际上初始化的时候本来就为NULL 
			tempParent->right = NULL;
		} 
		else
		{
			rightChild = constructNode(ch);
			tempParent->right  = rightChild;
			enqueue(resultQueuePtr,rightChild);
		}
	}
	
	return headerPtr;
}

遍历

void levelwise(BTNodePtr paraHeader)
{
	int i = 0;
	char ch;
	char tempString[100];
	BTNodeQueuePtr resultQueuePtr = BTNodeQueueInit();
	BTNodePtr tempNodePtr;	

	enqueue(resultQueuePtr,paraHeader);
	
	while(resultQueuePtr->front != resultQueuePtr->rear)
	{
		tempNodePtr = dequeue(resultQueuePtr);
		
		tempString[i] = tempNodePtr->element;
		i++;
		
		if (tempNodePtr->left != NULL)
		{
			enqueue(resultQueuePtr, tempNodePtr->left);
		}
		
		if (tempNodePtr->right != NULL)
		{
			enqueue(resultQueuePtr, tempNodePtr->right);
		}
	}
	
	tempString[i] = '';
	printf("%s",tempString);
	
}

总结：二叉树是树的特例，即每一个元素最多只能有两个分支。二叉树是十分重要的，一般的树都可以由二叉树转换过去并且一一对应。所以在我们熟练掌握二叉树之后，才能对一般的树进行操作。