数据结构----二叉树

完整代码

#include
#include

#define QUEUE_SIZE 5


typedef struct BTNode{
	char element;
	BTNode* left;
	BTNode* right;
}BTNode, *BTNodePtr;


typedef struct BTNodePtrQueue{
	BTNodePtr* nodePtrs;
	int front;
	int rear;
}BTNodePtrQueue, *QueuePtr;


QueuePtr initQueue(){
	QueuePtr resultQueuePtr=(QueuePtr)malloc(sizeof(struct BTNodePtrQueue));
	resultQueuePtr->nodePtrs=(BTNodePtr*)malloc(QUEUE_SIZE * sizeof(BTNodePtr));
	resultQueuePtr->front=0;
	resultQueuePtr->rear=1;
	return resultQueuePtr;
}//of initQueue


bool isQueueEmpty(QueuePtr paraQueuePtr){
	if((paraQueuePtr->front+1)%QUEUE_SIZE==paraQueuePtr->rear){
		return true;
	}//of if
	return false;
}//of isQueueEmpty


void enqueue(QueuePtr paraQueuePtr, BTNodePtr paraBTNodePtr){
	printf("front = %d, rear = %d.rn",paraQueuePtr->front,paraQueuePtr->rear);
	if((paraQueuePtr->rear+1)%QUEUE_SIZE==paraQueuePtr->front%QUEUE_SIZE){
		printf("Error, trying to the enqueue %c. queue full.rn",paraBTNodePtr->element);
		return;
	}//of if
	paraQueuePtr->nodePtrs[paraQueuePtr->rear]=paraBTNodePtr;
	paraQueuePtr->rear=(paraQueuePtr->rear + 1)%QUEUE_SIZE;
	printf("enqueue %c ends.rn",paraBTNodePtr->element);
}//of enqueue


BTNodePtr dequeue(QueuePtr paraQueuePtr){
	if(isQueueEmpty(paraQueuePtr)){
		printf("Error, empty queuern");
		return NULL;
	}//of if
	
	paraQueuePtr->front=(paraQueuePtr->front+1)%QUEUE_SIZE;
	//BTNodePtr tempPtr = paraQueuePtr->nodePtrs[paraQueuePtr->front+1]
	
	printf("dequeue %c ends.rn",paraQueuePtr->nodePtrs[paraQueuePtr->front]->element);
	return paraQueuePtr->nodePtrs[paraQueuePtr->front];
}//of dequeue


BTNodePtr ConstructBTNode(char paraChar){
	BTNodePtr resultPtr = (BTNodePtr)malloc(sizeof(BTNode));
	resultPtr->element=paraChar;
	resultPtr->left=NULL;
	resultPtr->right=NULL;
	return resultPtr;
}//of ConstructBTNode


BTNodePtr stringToBTree(char* paraString){
	int i;
	char ch;
	
	//Use a queue to manage  the pointers
	QueuePtr tempQueuePtr = initQueue();
	
	BTNodePtr resultHeader;
	BTNodePtr tempParent, tempLeftChild, tempRightChild;
	i=0;
	ch=paraString[i];
	resultHeader = ConstructBTNode(ch);
	enqueue(tempQueuePtr, resultHeader);
	
	while(!isQueueEmpty(tempQueuePtr)){
		tempParent = dequeue(tempQueuePtr);
		
		//The left child
		i++;
		ch=paraString[i];
		if(ch== '#'){
			tempParent->right=NULL;
		}
		else{
			tempRightChild = ConstructBTNode(ch);
			enqueue(tempQueuePtr,tempRightChild);
			tempParent->right = tempRightChild;
		}//of if
	}//of while
	
	return resultHeader;
}//of stringToBTree


void levelwise(BTNodePtr paraTreePtr){
	//Use a queue to manage the pointers
	char tempString[100];
	int i=0;
	QueuePtr tempQueuePtr = initQueue();
	BTNodePtr tempNodePtr;
	enqueue(tempQueuePtr, paraTreePtr);
	while(!isQueueEmpty(tempQueuePtr)){
		tempNodePtr = dequeue(tempQueuePtr);
		
		//For output.
		tempString[i] = tempNodePtr->element;
		i++;
		
		if(tempNodePtr->left !=NULL){
			enqueue(tempQueuePtr,tempNodePtr->left);
		}//of if
		if(tempNodePtr->right !=NULL){
			enqueue(tempQueuePtr,tempNodePtr->right);
		}//of if
	}//of while 
	tempString[i]='';
	
	printf("Levelwise: %srn",tempString);
}//of levelwise


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


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


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


int main(){
	BTNodePtr tempHeader;
	tempHeader = ConstructBTNode('c');
	printf("There is only one node. Preorder visit: ");
	preorder(tempHeader);
	printf("rn");
	
	char* tempString="acde#bf#####";
	
	tempHeader=stringToBTree(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 1;
}//of main

三种遍历

1.前序遍历(根左右)
递归定义：
（1）访问根节点
（2）前序遍历根节点的左子树
（3）前序遍历根节点的右子树
2.中序遍历(左根右)
递归定义;
（1）中序遍历根节点的左孩子
（2）访问根节点
（3）中序遍历根节点的右孩子
3.后序遍历(左右根)
递归定义;
（1）后序遍历根节点的左子树
（2）后序遍历根节点的右子树
（3）访问根节点
 

 运行结果