数据结构第九天——二叉树的构建与遍历

1、树的创建

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

2、队列的创建

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

3、队列初始化

QueuePtr initQueue() {
	QueuePtr resultQueuePtr = (QueuePtr)malloc(sizeof(BTNodePtrQueue));
	resultQueuePtr->nodePtrs = (BTNodePtr*)malloc(sizeof(BTNode) * 5);
	resultQueuePtr->front = 0;
	resultQueuePtr->rear = 1;
	
	return resultQueuePtr;
}

4、判断队列是否为空

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

5、添加

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

6、删除

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

7、初始化树结点

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

8、初始化树

BTNodePtr stringToBTree(char *paraString) {
	int i;
	char ch;
	
	QueuePtr tempQueuePtr = initQueue();
	
	BTNodePtr resultHeader;
	BTNodePtr tempParent, tempLeftChild, tempRightChild;
	i = 0;
	ch = paraString[0];
	resultHeader = constructBTNode(ch);
	enqueue(tempQueuePtr, resultHeader);
	
	while (isQueueEmpty(tempQueuePtr) == 0) {
		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;
}

9、层序遍历

void levelwise(BTNodePtr paraTreePtr) {
	char tempString[100];
	int i = 0;
	QueuePtr tempQueuePtr = initQueue();
	BTNodePtr tempNodePtr;
	enqueue(tempQueuePtr, paraTreePtr);
	while (isQueueEmpty(tempQueuePtr) == 0) {
		tempNodePtr = dequeue(tempQueuePtr);
		
		tempString[i] = tempNodePtr->element;
		i ++;
		
		if (tempNodePtr->left != NULL) {
			enqueue(tempQueuePtr, tempNodePtr->left);
		}
		
		if (tempNodePtr->right != NULL) {
			enqueue(tempQueuePtr, tempNodePtr->right);
		}
	}
	tempString[i] = '';
	
	printf("Levelwise:%sn", tempString);
}

10、先序遍历

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

11、中序遍历

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

12、后序遍历

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

总代码

#include
#include


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


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


 
QueuePtr initQueue() {
	QueuePtr resultQueuePtr = (QueuePtr)malloc(sizeof(BTNodePtrQueue));
	resultQueuePtr->nodePtrs = (BTNodePtr*)malloc(sizeof(BTNode) * 5);
	resultQueuePtr->front = 0;
	resultQueuePtr->rear = 1;
	
	return resultQueuePtr;
}


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


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


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


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


 
BTNodePtr stringToBTree(char *paraString) {
	int i;
	char ch;
	
	QueuePtr tempQueuePtr = initQueue();
	
	BTNodePtr resultHeader;
	BTNodePtr tempParent, tempLeftChild, tempRightChild;
	i = 0;
	ch = paraString[0];
	resultHeader = constructBTNode(ch);
	enqueue(tempQueuePtr, resultHeader);
	
	while (isQueueEmpty(tempQueuePtr) == 0) {
		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;
}


  
void levelwise(BTNodePtr paraTreePtr) {
	char tempString[100];
	int i = 0;
	QueuePtr tempQueuePtr = initQueue();
	BTNodePtr tempNodePtr;
	enqueue(tempQueuePtr, paraTreePtr);
	while (isQueueEmpty(tempQueuePtr) == 0) {
		tempNodePtr = dequeue(tempQueuePtr);
		
		tempString[i] = tempNodePtr->element;
		i ++;
		
		if (tempNodePtr->left != NULL) {
			enqueue(tempQueuePtr, tempNodePtr->left);
		}
		
		if (tempNodePtr->right != NULL) {
			enqueue(tempQueuePtr, tempNodePtr->right);
		}
	}
	tempString[i] = '';
	
	printf("Levelwise:%sn", tempString);
}


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


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


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

int main() {
	BTNodePtr tempHeader;
	tempHeader = constructBTNode('c');
	printf("There is only one node. nPreorder visit:");
	preorder(tempHeader);
	printf("n");
	
	char *tempString = "acde#bf######";
	
	tempHeader = stringToBTree(tempString);
	printf("Preorder:");
	preorder(tempHeader);
	printf("n");
	printf("Inorder:");
	inorder(tempHeader);
	printf("n");
	printf("Postorder:");
	postorder(tempHeader);
	printf("n");
	printf("Levelwise:");
	levelwise(tempHeader);
	printf("n");
	
	return 0;
}

结果显示

There is only one node.
Preorder visit:c
front = 0, rear = 1.
enqueue a ends.
dequeue a ends.
front = 1, rear = 2.
enqueue c ends.
front = 1, rear = 3.
enqueue d ends.
dequeue c ends.
front = 2, rear = 4.
enqueue e ends.
dequeue d ends.
front = 3, rear = 0.
enqueue b ends.
front = 3, rear = 1.
enqueue f ends.
dequeue e ends.
dequeue b ends.
dequeue f ends.
Preorder:acedbf
Inorder:ceadbf
Postorder:cedbfa
Levelwise:front = 0, rear = 1.
enqueue a ends.
dequeue a ends.
front = 1, rear = 2.
enqueue c ends.
front = 1, rear = 3.
enqueue d ends.
dequeue c ends.
front = 2, rear = 4.
enqueue e ends.
dequeue d ends.
front = 3, rear = 0.
enqueue b ends.
front = 3, rear = 1.
enqueue f ends.
dequeue e ends.
dequeue b ends.
dequeue f ends.
Levelwise:acdebf

（1）：先序、中序和后序都是通过递归实现

（2）：初始化树那里，之前一直想不通那个resultheader怎么把其它结点连接上，就很奇怪，后来发现在dequeue函数那里，返回的是指针，所以在那里让header和parent连接上了

（3）：还有注意细节，在初始化那里，我不小心把rear = 1，写成了-1，结果后面就一直错

（4）：还有层序遍历，通过队列实现，读入一个结点，加入到队列，然后出队列的同时，又把它的左右结点加入到队列，直到把队列都出完

（5）：注意在初始化队列那里，队列的nodePtrs申请动态内存时，malloc前面的括号，那个BTNodePtr加了*号，但是在定义树结点时，typedef快捷定义了*BTNodePtr,后面发现在队列的结构体里面，定义的是BTNodePtr *nodePtrs，所以是指针的指针，这点注意