数据结构:二叉树的遍历

写在前面

学习二叉树结构,最简单的方式就是遍历。所谓二叉树遍历,就是按照某种特定的规则,一次对二叉树中的节点进行相应的操作,并且每个节点只操作一次。 访问节点所做的操作要看具体的应用问题。遍历是二叉树上最重要的运算之一,也是二叉树上进行其他运算的基础。


Ⅰ.  二叉树的遍历

0x00 关于遍历

二叉树遍历(Traversal):沿着某条搜索路线,依次对树中每个结点均做一次且仅做一次访问。 按照规则,二叉树的遍历有:前序 / 中序 / 后序 的递归结构遍历。除了前序、中序和后续遍历外,我们还可以对二叉树进行层序遍历

数据结构:二叉树的遍历_第1张图片

0x01 二叉树前序遍历

数据结构:二叉树的遍历_第2张图片

前序遍历(Preorder Traversal):访问根节点的操作发生在遍历其右子树之前。

即,首先访问根结点,然后遍历左子树,最后遍历右子树。

代码实现前序遍历:

(这里我们用 Ø 符号来表示 NULL)

/* 二叉树前序遍历 */
void PreOrder(BTNode* root) {
	/* 首先判断根是否为空,为空就返回 */
	if (root == NULL) {        
		printf("Ø ");	// 暂时打印出来,便于观察	   
		return;				   
	}

	/* 走到这里说明不为空,根据前序遍历,先访问根节点 */
	printf("%c ", root->data);

	/* 然后遍历左子树(利用递归) */
	PreOrder(root->left);

	/* 最后遍历右子树(利用递归) */
	PreOrder(root->right);	                  
}

解读:

① 首先判断根是否为空,如果根为空,则返回。这里为了表示,我们把空节点以 " Ø " 打印出来。

② 如果跟不为空,这说明有数据。由于是前序遍历(Preorder),前序遍历是先访问根节点,然后遍历左子树,最后再遍历右子树。所以,我们这里先要访问的是根节点,我们把根节点的数据打印出来。

③ 然后我们需要遍历左子树,这时我们利用递归就可以实现。将根节点 root 的左数 left 传入 PreOrder 函数(将其左树看作根),一直递归下去,直到碰到 root == NULL 则返回。

④ 最后,遍历完左子树后遍历右子树。利用递归,方法同上。

数据结构:二叉树的遍历_第3张图片

0x02 二叉树中序遍历

中序遍历(Inorder Traversal):访问根节点的操作发生在遍历其左右子树之中。

即,首先遍历左子树,然后访问根结点,最后遍历右子树。

/* 二叉树中序遍历 */
void InOrder(BTNode* root) {
	/* 首先判断根是否为空,为空就返回 */
	if (root == NULL) {
		printf("Ø ");  // 暂时打印出来,便于观察
		return;
	}

	/* 走到这里说明不为空,根据中序遍历,先遍历左子树 */
	InOrder(root->left);

	/* 然后访问根节点(利用递归) */
	printf("Ø ", root->data);

	/* 最后遍历右子树(利用递归) */
	InOrder(root->right);
}

解读:

① 首先判断根是否为空,如果根为空,则返回。

② 如果跟不为空,这说明有数据。由于是中序遍历(Inorder),中序遍历是先遍历左子树,然后访问根节点,最后遍历右子树。

0x03 二叉树后序遍历

后序遍历(Postorder Traversal):访问根节点的操作发生在遍历其左右子树之后。

即,首先遍历左子树,然后遍历右子树,最后访问根结点。

/* 二叉树后序遍历 */
void PostOrder(BTNode* root) {
	/* 首先判断根是否为空,为空就返回 */
	if (root == NULL) {
		printf("/ ");
		return;
	}

	/* 走到这里说明不为空,根据后序遍历,先遍历左子树(利用递归) */
	PostOrder(root->left);

	/* 然后遍历右子树(利用递归) */
	PostOrder(root->right);

	/* 最后访问根节点 */
	printf("%c ", root->data);
}

解读:

① 首先判断根是否为空,如果根为空,则返回。

② 如果跟不为空,这说明有数据。由于是后序遍历(Postorder),后序遍历是先遍历左子树,然后遍历右子树,最后访问根节点。

0x04 层序遍历

层序遍历(Level Traversal):设二叉树的根节点所在的层数为1的情况下,从二叉树的根节点出发,首先访问第1层的树根节点,然后再从左到右访问第2层上的节点。接着是第3层的节点……以此类推,自上而下、从左向右地逐层访问树的节点。

数据结构:二叉树的遍历_第4张图片

❓ 该如何实现层序遍历呢?

我们可以利用队列的性质来实现!

我们之前再讲过队列,这里你可以选择自己实现一个队列。如果不想实现就直接 CV 即可,因为我们这里重点要学的是层序遍历!

链接:【数据结构】队列的基本概念 | 从零开始实现队列

Queue.h:

#include 
#include 
#include 
#include 

typedef int QueueDataType;

typedef struct QueueNode {
	struct QueueNode* next;
	QueueDataType data;
} QueueNode;

typedef struct Queue {
	QueueNode* pHead;
	QueueNode* pTail;
} Queue;

void QueueInit(Queue* pQ);                    //队列初始化
void QueueDestroy(Queue* pQ);                 //销毁队列
bool QueueIfEmpty(Queue* pQ);                 //判断队列是否为空
void QueuePush(Queue* pQ, QueueDataType x);   //入队
void QueuePop(Queue* pQ);                     //出队
QueueDataType QueueFront(Queue* pQ);          //返回队头数据
QueueDataType QueueBack(Queue* pQ);           //返回队尾数据
int QueueSize(Queue* pQ);                     //求队列大小


Queue.c:

 #define _CRT_SECURE_NO_WARNINGS 1
#include "Queue.h"

/* 队列初始化 */
void QueueInit(Queue* pQ) {
	assert(pQ);
	pQ->pHead = pQ->pTail = NULL;
}

/* 销毁队列 */
void QueueDestroy(Queue* pQ) {
	assert(pQ);
	QueueNode* cur = pQ->pHead;
	while (cur != NULL) {
		QueueNode* cur_next = cur->next;
		free(cur);
		cur = cur_next;
	}
	pQ->pHead = pQ->pTail = NULL;
}

/* 判断队列是否为空 */
bool QueueIfEmpty(Queue* pQ) {
	assert(pQ);
	return pQ->pHead == NULL;
}

/* 入队 */
QueueNode* CreateNewNode(QueueDataType x) {
	QueueNode* new_node = (QueueNode*)malloc(sizeof(QueueNode));
	if (new_node == NULL) {
		printf("malloc failed!\n");
		exit(-1);
	}
	new_node->data = x;
	new_node->next = NULL;

	return new_node;
}
void QueuePush(Queue* pQ, QueueDataType x) {
	assert(pQ);
	QueueNode* new_node = CreateNewNode(x);

	if (pQ->pHead == NULL) {
		pQ->pHead = pQ->pTail = new_node;
	}
	else {
		pQ->pTail->next = new_node;
		pQ->pTail = new_node;
	}
}

/* 出队 */
void QueuePop(Queue* pQ) {
	assert(pQ);
	assert(!QueueIfEmpty(pQ));

	QueueNode* save_next = pQ->pHead->next;
	free(pQ->pHead);
	pQ->pHead = save_next;

	if (pQ->pHead == NULL) {
		pQ->pTail = NULL;
	}
}

/* 返回队头数据 */
QueueDataType QueueFront(Queue* pQ) {
	assert(pQ);
	assert(!QueueIfEmpty(pQ));

	return pQ->pHead->data;
}

/* 返回队尾数据 */
QueueDataType QueueBack(Queue* pQ) {
	assert(pQ);
	assert(!QueueIfEmpty(pQ));

	return pQ->pTail->data;
}

/* 求队列大小 */
int QueueSize(Queue* pQ) {
	assert(pQ);
	int count = 0;
	QueueNode* cur = pQ->pHead;

	while (cur != NULL) {
		count++;
		cur = cur->next;
	}

	return count;
}

这里为了方便讲解 #include "展开" 的特点,我们把树的定义放到 test.c 中,并且在 test.c 里完成层序遍历。

数据结构:二叉树的遍历_第5张图片

test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "Queue.h"

typedef char BTDataType;
typedef struct BinaryTreeNode {
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
	BTDataType data;
} BTNode;

//#include "Queue.h"  解决方案?

/* 创建新节点 */
BTNode* BuyNode(BTDataType x) {
	BTNode* new_node = (BTNode*)malloc(sizeof(BTNode));
	if (new_node == NULL) {
		printf("malloc failed!\n");
		exit(-1);
	}
	new_node->data = x;
	new_node->left = new_node->right = NULL;

	return new_node;
}

/* 手动创建二叉树 */
BTNode* CreateBinaryTree() {
	BTNode* nodeA = BuyNode('A');
	BTNode* nodeB = BuyNode('B');
	BTNode* nodeC = BuyNode('C');
	BTNode* nodeD = BuyNode('D');
	BTNode* nodeE = BuyNode('E');
	BTNode* nodeF = BuyNode('F');

	nodeA->left = nodeB;
	nodeA->right = nodeC;
	nodeB->left = nodeD;
	nodeC->left = nodeE;
	nodeC->right = nodeF;

	return nodeA;
}

由于是我们的数据类型是 BTNode,我们需要修改一下 Queue.h 的 QueueDataType,我们之前一直强调的 typedef 的好处,这里就显现出来了。我们只需要把 int 改成 BTNode 就可以了,而不需要改很多地方。

Queue.h:

#include 
#include 
#include 
#include 

typedef BTNode* QueueDataType;

typedef struct QueueNode {
	struct QueueNode* next;
	QueueDataType data;
} QueueNode;

typedef struct Queue {
	QueueNode* pHead;
	QueueNode* pTail;
} Queue;

void QueueInit(Queue* pQ);                    //队列初始化
void QueueDestroy(Queue* pQ);                 //销毁队列
bool QueueIfEmpty(Queue* pQ);                 //判断队列是否为空
void QueuePush(Queue* pQ, QueueDataType x);   //入队
void QueuePop(Queue* pQ);                     //出队
QueueDataType QueueFront(Queue* pQ);          //返回队头数据
QueueDataType QueueBack(Queue* pQ);           //返回队尾数据
int QueueSize(Queue* pQ);                     //求队列大小

这时我们运行一下代码会出现一个问题,我们发现它报错了:

数据结构:二叉树的遍历_第6张图片

 它说,缺少 " { " ,这明显是胡说八道的,咱编译器也没有那么只能,毕竟是也不是VS2077。

❓ 这里产生问题的原因是什么呢?

编译器原则:编译器认识 int,因为 int 是一个内置类型。但是 BTNode* 编译器并不认识,就需要 "往上面" 去找这个类型。这里显然往上找,是找不到它的定义的,所以编译器会报错。

数据结构:二叉树的遍历_第7张图片

如果你要用这个类型,你就需要先定义这个类型。test.c文件中 #include "Queue.h" ,相当于把这里的代码拷贝过去了。这时,由于BTNode*会在上面展开,导致找不到 BTNode*  。

❓ 我把 #include 移到 定义类型的代码 的后面,可以解决问题吗?

数据结构:二叉树的遍历_第8张图片

可以!遗憾的是只能解决这里 typedef BTNode* 的问题,还有 Queue.c 里的问题……

那我们该怎么做,能彻底解决呢?

解决方案:前置声明。 这样就不会带来问题了,满足了先声明后使用。

数据结构:二叉树的遍历_第9张图片

Queue.h (修改后):

#include 
#include 
#include 
#include 

// 前置声明
struct BinaryTreeNode;
typedef struct BinaryTreeNode* QueueDataType;

typedef struct QueueNode {
	struct QueueNode* next;
	QueueDataType data;
} QueueNode;

typedef struct Queue {
	QueueNode* pHead;
	QueueNode* pTail;
} Queue;

void QueueInit(Queue* pQ);                    //队列初始化
void QueueDestroy(Queue* pQ);                 //销毁队列
bool QueueIfEmpty(Queue* pQ);                 //判断队列是否为空
void QueuePush(Queue* pQ, QueueDataType x);   //入队
void QueuePop(Queue* pQ);                     //出队
QueueDataType QueueFront(Queue* pQ);          //返回队头数据
QueueDataType QueueBack(Queue* pQ);           //返回队尾数据
int QueueSize(Queue* pQ);                     //求队列大小

思路如下:

        ① 让根节点先入队。

        ② 记录当前队头后打印,并让队头出队,然后检测,如过孩子不为空就把孩子带进去。

          (上一层节点出队时带入下一层节点入队)

        ③ 只要队列不为空就说明还没完。如果队列为空,说明下面最后一层没有节点,遍历结束。

注意事项:使用完队列后别忘了要销毁!

代码实现:

void BinaryTreeLevelOrder(BTNode* root) {
	if (root == NULL) {		// 判断根是否为空
		return;
	}

	Queue pQ;			// 建立队列
	QueueInit(&pQ);		// 初始化队列
	QueuePush(&pQ, root);	// 先让根进入队列
	while (!QueueIfEmpty(&pQ)) {	// 只要队列内还有元素,就进入循环
		BTNode* front = QueueFront(&pQ);	// 记录当前对头数据
		printf("%c ", front->data);  // 打印队头数据
		QueuePop(&pQ);	 // 当队头出队

		if (front->left != NULL) {		// 如果队头元素的左子树不为空
			QueuePush(&pQ, front->left);	// 让左子树进入队列
		}
		if (front->right != NULL) {		// 如果对头元素的右子树不为空
			QueuePush(&pQ, front->right);	// 让右子树进入队列
		}
	}

	QueueDestroy(&pQ);	 // 销毁队列
}

解读:

① 首先判断根是否为空,如果为空就没有必要往下走了。

② 建立和初始化队列后,首先让根节点进入队列。只要队列内还有元素存在(说明还没遍历完)就进入循环。每次循环进入后都记录一下当前队头,这里使用 QueueFront 取队头数据即可。之后打印对头的数据。

③ 打印完后让队头出队,随后判断它的左子树和右子树,如果不为空就允许它们进队。我们先判断 left,再判断 right,这样就可以做到一层一层从左往右走的效果了。

④ 最后使用完队列后,别忘了销毁队列!


Ⅱ. BINARY TREE TRAVERSALS 阅读笔记

0x00 概念

经常出现的一个操作是遍历树,也就是说,对树上的每个节点都精确访问一次。

完全遍历会对树中的信息产生一个线性顺序。

当遍历一棵树时,我们希望以同样的方式对待每个节点和它的子树。

假设对于树中的每个节点:

L 代表向左移动

V 代表访问该节点(eg. 打印出数据字段)

R 代表向右移动。

则存在 6 种可能的遍历组合:

LVR —— 中序遍历(inorder traversal)

LRV —— 后序遍历(postorder traversal)

VLR —— 前序遍历(preorder traversal)

VRL, \, \, RVL, \, \, RLV.

二叉树的三种遍历,与表达式的 infix, \, postfix, \, prefix  三种形式,不乏紧密、自然的联系。

数据结构:二叉树的遍历_第10张图片(图5.15)

 

0x01 中序遍历 - Inorder Traversal

void inorder(tree_pointer ptr)
/* inorder tree traversal */
{
	if (ptr) {
		inorder(ptr->left_child);
		printf("%d", ptr->data);
		inorder(ptr->right_child);
	}
}

图5.15 按顺序输出:

 数据结构:二叉树的遍历_第11张图片

0x02 前序遍历 - Preorder Traversal

void preorder(tree_pointer ptr)
/* preorder tree traversal */
{
	if (ptr) {
		printf("%d", ptr->data);
		preorder(ptr->left_child);
		preorder(ptr->right_child);
	}
}

图5.15 按顺序输出:

0x03 后序遍历 - Postorder Traversal

void postorder(tree_pointer ptr)
/* postorder tree traversal */
{
	if (ptr) {
		postorder(ptr->left_child);
		postorder(ptr->right_child);
		printf("%d", ptr->data);
	}
}

图5.15 按顺序输出:

0x04 非递归(循环)中序遍历 - Iterative Inorder Traversal

图5.16 含蓄地表现了 Program5.1 的堆叠和拆垛的过程。

一个没有动作的节点表示该节点被添加到堆栈中, - 而一个有printf动作的节点表示该节点被从堆栈中移除。 注意: - 左边的节点被堆叠起来,直到到达一个空节点, - 然后该节点被从堆叠中移除, - 该节点的右边子节点被堆叠起来

void iter_inorder(tree_pointer node)
{
	int top = -1; /* initialize stack */
	tree_pointer stack[MAX_STACK_SIZE];
	for (; ; ) {
		for (; node; node = node->left_child)
			add(&top, node); /* add to stack */
		node = delete(&top); /* delete from stack */
		if (!node) break; /* empty stack */
		printf("%d", node->data);
		node = node->right_child;
	}
}

iter_inorder 的分析:令 n 是树中结点个数。iterInorder 把每个节点入栈一次、出栈一次,所以时间复杂度为 O(n),空间复杂度取决于树的深度,也是 O(n)

0x05 层序遍历 - Level Order Traversal

数据结构:二叉树的遍历_第12张图片

层序遍历(Level Traversal):设二叉树的根节点所在的层数为1的情况下,从二叉树的根节点出发,首先访问第1层的树根节点,然后再从左到右访问第2层上的节点。接着是第3层的节点……以此类推,自上而下、从左向右地逐层访问树的节点。

层序遍历需要利用队列来实现遍历。

void level_order(tree_pointer ptr)
/* level order tree traversal */
{
	int front = rear = 0;
	tree_pointer queue[MAX_QUEUE_SIZE];
	if (!ptr) return; /* empty tree */
	addq(front, &rear, ptr);
	for (; ; ) {
		ptr = deleteq(&front, rear); /*empty list returns NULL*/
		if (ptr) {
			printf("%d", ptr->data);
			if (ptr->left_child)
				addq(front, &rear, ptr->left_child);
			if (ptr->right_child)
				addq(front, &rear, ptr->right_child);
		}
		else break;
	}
}

Ⅲ. 其他二叉树操作

0x00 复制二叉树

根据二叉树的定义,以及前中后序的递归实现,可以很容易地编写其他二叉树操作的C程序。

以常用的二叉树复制操作为例,程序 5.6 中的 copy 函数为实现代码。程序结构与刚才的 postorder 很接近,它实际上是根据它的代码修改而得到的,改动很少。

[Program 5.6] 复制二叉树

tree_pointer copy(tree_pointer original)
/* this function returns a tree_pointer to an exact copy
of the original tree */
{
	tree_pointer temp;
	if (original) {
		temp = (tree_pointer)malloc(sizeof(node));
		if (IS_FULL(temp)) {
			fprintf(stderr, "The memory is full\n");
			exit(1);
		}
		temp->left_child = copy(original->left_child);
		temp->right_child = copy(original->right_child);
		temp->data = original->data;
		return temp;
	}
	return NULL;
}

0x01 判断两个二叉树全等 - Testing For Equality Of Binary Trees

两个全等的二叉树定义为两者的结构相等,并且对应数据域的内容相等。

int equal(tree_pointer first, tree_pointer second)
/* function returns FALSE if the binary trees first and
second are not equal, otherwise it returns TRUE */
{
	return ((!first && !second) || (first && second &&
		(first->data == second->data) &&
		equal(first->left_child, second->left_child) &&
		equal(first->right_child, second->right_child))
}

0x03 可满足性问题(The Satisfiability Problem)

考虑由遍历 x_1,x_2,...,x_n 和操作符  构成的演算公式集合。

变量只有两种取值 true 和 flase。

公式满足如下条件:

数据结构:二叉树的遍历_第13张图片

(1)一个变量是一个表达式

(2)如果 x 和 y 是表达式, 则 是表达式

(3)操作符的优先级从高到低为 ,但括号可以改变运算顺序。

这三条基本规则可以生成命题演算的所有演算公式,如 "蕴含" 可用 表示。

数据结构:二叉树的遍历_第14张图片

对于给定的公式,是否存在一个变量集合的赋值,使该公式的求值结果为 true。

[program 5.8] 求解可满足性问题的第一个程序

for (all 2n possible combinations) {
	generate the next combination;
	replace the variables by their values;
	evaluate the expression;
	if (its value is true) {
		printf();
		return;
	}
}
printf("No satisfiable combination\n");

数据结构:二叉树的遍历_第15张图片为了评为了评估一个表达式,我们可以按后序遍历树,评估子树,直到整个表达式被简化为一个单一的值。 这对应于算术表达式的后缀评估。

数据结构:二叉树的遍历_第16张图片

[program 5.8]  后序求值

void post_order_eval(tree_pointer node)
{
	/* modified postorder traversal to evaluate
	a propositional calculus tree */
	if (node) {
		post_order_eval(node->left_child);
		post_order_eval(node->right_child);
		switch (node->data) {
		case not : node->value =
			!node->right_child->value;
			break;
		caseand : node->value =
			node->right_child->value && node->left_child->value;
		break;
		case or : node->value =
			node->right_child->value || node->left_child->value;
			break;
		case true: node->value = TRUE;
			break;
		case false: node->value = FALSE;
		}
	}
}


参考资料

Fundamentals of Data Structures in C

你可能感兴趣的