数据结构-二叉树

1.树的定义和基本性质

树是一种非线性的数据结构，它是由n（n>=0）个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。有一个特殊的结点，称为根结点，根节点没有前驱结点除根节点外，其余结点被分成M(M>0)个互不相交的集合T1、T2、……、Tm，其中每一个集合Ti(1<= i <= m)又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱，可以有0个或多个后继因此，树是递归定义的。   

二叉树

二叉树是n(n>=0)个节点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根节点和两棵互不相交的、分别称为根节点的左子树和右子树组          

 （1）建立队列及二叉树节点

typedef struct BTNode{
	char element;
	BTNode* left;
	BTNode* right;
}
 
typedef struct BTNodePtrQueue{
	BTNodePtr* nodePtrs;
	int front;
	int rear;
}

（2）初始化

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;
}

（3）判断队列是否为空

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

（4）入队

oid 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 enqueue %c. queue full.rn", paraBTNodePtr->element);
		return;
	}
	paraQueuePtr->nodePtrs[paraQueuePtr->rear] = paraBTNodePtr;
	paraQueuePtr->rear = (paraQueuePtr->rear + 1) % QUEUE_SIZE;
	printf("enqueue %c ends.rn", paraBTNodePtr->element);
}

（5）出队

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

（6）初始化

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

（7）建立二叉树

BTNodePtr stringToBTree(char* paraString){
	int i;
	char ch;
 
	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);
 
		i ++;
		ch = paraString[i];
		if (ch == '#') {
			tempParent->left = NULL;
		} else {
			tempLeftChild = constructBTNode(ch);
			enqueue(tempQueuePtr, tempLeftChild);
			tempParent->left = tempLeftChild;
		}
 
		i ++;
		ch = paraString[i];
		if (ch == '#') {
			tempParent->right = NULL;
		} else {
			tempRightChild = constructBTNode(ch);
			enqueue(tempQueuePtr, tempRightChild);
			tempParent->right = tempRightChild;
		}
	}
 
	return resultHeader;
}

（8）前序遍历

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

 

 

（9）中序遍历

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

 

 

（10）后序遍历

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

 

 

（11）主函数

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;
}