完全二叉树的创建与遍历

创建一棵完全二叉树（递归方式）（创建方法仅使用与完全二叉树）

层序遍历完全二叉树（遍历算法适用于所有二叉树）：利用队列FIFO的性质

中序遍历完全二叉树（递归方式，遍历算法适用于所有二叉树）

先序遍历完全二叉树（递归方式，遍历算法适用于所有二叉树）

后序遍历完全二叉树（递归方式，遍历算法适用于所有二叉树）

代码如下（代码缺点：有malloc但是没有free，会导致程序占用过多内存）

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

/*
 * 1.递归算法创建一颗完全二叉树
 * 2.递归算法中序/先序/后序遍历一颗完全二叉树
 * 3.利用队列FIFO的特性层序遍历一颗完全二叉树
 * */
typedef struct Node {
	// 二叉树节点
	int data;
	struct Node *left;
	struct Node *right;
} Node, *BinTree;

typedef struct qNode {
	// 队列节点
	Node* treenode;
	struct qNode *next;
} qNode, *Queue;

bool isEmpty(Queue queue);
Node* delete(Queue queue);
void add(Queue queue, Node* ptr);
BinTree create(int arr[], int i, int length);  // craete a Complete Binary Tree
void accessTreeNode(Node* ptr);
void levelOrder(BinTree T, Queue queue);
void inOrder(BinTree T);
void preOrder(BinTree T);
void postOrder(BinTree T);

int main(int argc, char* argv[]) {
	// 按照层序和一个数组创建一颗完全二叉树
	int arr[] = {4, 3, 9, 8 ,2, 1};
	BinTree T = create(arr, 0, sizeof(arr)/sizeof(int));
	printf("Original     data: ");
	for (int i = 0; i < sizeof(arr)/sizeof(int); i++) {
			printf("%d ", arr[i]);
	}
	printf("\n");
	
	// 初始化一个队列
	Queue queue = (qNode*)malloc(sizeof(qNode));
	queue->treenode = NULL;
	queue->next = NULL;
	
	// 利用队列，层序遍历完全二叉树
	printf("Level Order begin: ");
	levelOrder(T, queue);
	printf("\n");	
	
	// 中序遍历二叉树
	printf("In    Order begin: ");
	inOrder(T);
	printf("\n");
	
	// 先序遍历二叉树
	printf("Pre   Order begin: ");
	preOrder(T);
	printf("\n");

	// 后序遍历二叉树
	printf("Post  Order begin: ");
	postOrder(T);
	printf("\n");
	
	return 0;
}

BinTree create(int arr[], int i, int length) {
	// 递归创建一颗完全二叉树
	BinTree T = NULL;
	if (i < length) {
		T = (Node*)malloc(sizeof(Node));
		T->data = arr[i];
		T->left = create(arr, 2*i+1, length);
		T->right = create(arr, 2*i+2, length);
	}
	return T;
}
bool isEmpty(Queue queue) {
	/*判断队列是否为空*/
	return queue->next == NULL;
}
Node* delete(Queue queue) {
	/*队头元素出队*/
	if (isEmpty(queue)) return NULL;
	qNode* p = queue->next;
	queue->next = p->next;
	Node* ret = p->treenode;  // ret保存出队元素的数据域
	free(p);
	return ret;
}
void add(Queue queue, Node* ptr) {
	/*元素在队尾入队*/
	qNode* newnode = malloc(sizeof(qNode));
	newnode->treenode = ptr;
	newnode->next = NULL;
	
	// 循环结束后，temp指向当前的队尾元素
	Queue temp = queue;
	while(temp->next != NULL) {
		temp = temp->next;
	}
	temp->next = newnode;
}
void accessTreeNode(Node* ptr) {
	/*访问完全二叉树的一个节点*/
	printf("%d ", ptr->data);
}
void levelOrder(BinTree T, Queue queue) {
	/*利用队列，层序遍历二叉树*/
	add(queue, T); // 根节点入队
	while (!isEmpty(queue)) {
		// 队头元素出队，并访问之
		Node* temp = delete(queue);
		accessTreeNode(temp);
		
		// 将该元素的孩子节点入队
		if (temp->left != NULL) add(queue, temp->left);
		if (temp->right != NULL) add(queue, temp->right);
	}
}

void inOrder(BinTree T) {
	/*中序遍历二叉树*/
	if (T != NULL) {
		inOrder(T->left);
		accessTreeNode(T);
		inOrder(T->right);
	}
}

void preOrder(BinTree T) {
	/*先序遍历二叉树*/
	if (T != NULL) {
		accessTreeNode(T);
		preOrder(T->left);
		preOrder(T->right);
	}
}

void postOrder(BinTree T) {
	/*后序遍历二叉树*/
	if (T != NULL) {
		postOrder(T->left);
		postOrder(T->right);
		accessTreeNode(T);
	}
}

完全二叉树图形化

输出结果