前言
二叉树遍历是指按照一定的顺序访问二叉树中的每个节点，使得每个节点恰好被访问一次。遍历是二叉树上最重要的运算之一，是二叉树上进行其他运算的基础。
一、二叉树遍历概念
二叉树遍历分类
- 前序遍历 ：根节点–>左子树–>右子树。在前序遍历时，首先访问根节点，然后依次访问左子树和右子树。
- 中序遍历 : 左子树–>根节点–>右子树。在中序遍历时，首先访问左子树，然后访问根节点，最后访问右子树。
- 后序遍历：左子树–>右子树–>根节点。在后序遍历时，首先访问左子树和右子树，然后访问根节点。
- 层序遍历： 由顶层到底层，一层一层遍历。
二叉树其他操作
树节点的个数，树深度，树 k 层的个数，查找节点。
二、二叉树遍历实现
我们以下面为例子：
2.1 二叉树建立
1.定义一个结构体，分别有左右两个指针。
2.为每一个节点创建孔家。
3.创建二叉树，并如上图连接。
//定义结构体 typedef int BTTypeData; typedef struct BinaryTree { BTTypeData data; struct BinaryTree* left; struct BinaryTree* right; }BinaryTree; //创建空间 BinaryTree* BuyBinaryTree(BTTypeData x) { BinaryTree* node = (BinaryTree*)malloc(sizeof(BinaryTree)); if (node == NULL) { perror("malloc fail"); return NULL; } node->data = x; node->left = NULL; node->right = NULL; return node; } //建树 BinaryTree* CreateBinaryTree() { BinaryTree* node1 = BuyBinaryTree(1); BinaryTree* node2 = BuyBinaryTree(2); BinaryTree* node3 = BuyBinaryTree(3); BinaryTree* node4 = BuyBinaryTree(4); BinaryTree* node5 = BuyBinaryTree(5); BinaryTree* node6 = BuyBinaryTree(6); BinaryTree* node7 = BuyBinaryTree(7); BinaryTree* node8 = BuyBinaryTree(8); BinaryTree* node9 = BuyBinaryTree(9); node1->left = node2; node1->right = node4; node2->left = node3; node4->left = node5; node4->right = node6; node3->right = node7; node6->left = node8; node6->right = node9; return node1; }
2.2 前序遍历
在递归实现中，前序遍历的基本思想是对于每一个节点，先访问该节点，然后对其左子树进行前序遍历，最后对其右子树进行前序遍历。如果当前节点为空，则直接返回。这种方法的优点是代码简洁明了，易于理解，但缺点是可能导致栈溢出，特别是在处理深度较大的二叉树时。
遍历结果：1–> 2–> 3 –>7 –>4 –>5 –>6–> 8 –>9
//前序遍历 void PreOrder(BinaryTree* root) { if (root == NULL) { //printf("NULL "); return; } printf("%d ", root->data); PreOrder(root->left); PreOrder(root->right); }
2.2 中序遍历
首先对左子树进行中序遍历，然后访问根节点，最后对右子树进行中序遍历。
遍历结果：3 –>7–>2–> 1–> 5–> 4–>8–> 6–> 9
void InOrder(BinaryTree* root) { if (root == NULL) { //printf("NULL "); return; } InOrder(root->left); printf("%d ", root->data); InOrder(root->right); }
2.3 后序遍历
递归函数首先访问左子树，然后访问右子树，最后访问根节点。如果当前节点为空，则直接返回。
遍历结果：7–> 3–> 2–> 5–> 8 –>9 –>6 –>4 –>1
//后序遍历 void PostOrder(BinaryTree* root) { if (root == NULL) { //printf("NULL "); return; } PostOrder(root->left); PostOrder(root->right); printf("%d ", root->data); }
2.4 层序遍历
在二叉树的层序遍历是指按照树的层次顺序，从上到下、从左到右逐层访问二叉树的节点。这种遍历方式可以帮助我们了解二叉树的结构布局，特别是在处理树状数据结构时非常有用。
利用队列的特点，有关队列可参考 栈和队列
- 将根节点入队。
- 当队列不为空时，从队列中取出一个节点，访问该节点。
- 将该节点的左右子节点（如果存在）入队。
- 重复步骤2和3，直到队列为空。
遍历结果：1–> 2 –>4 –>3 –>5 –>6 –>7 –>8 –>9
//层序遍历 void LevelOrder(BinaryTree* root) { if (root == NULL) { printf("NULL "); return; } Queue TBT; QueueInit(&TBT); if (root) QueuePush(&TBT, root); while (!QueueEmpty(&TBT)) { BinaryTree* front = QueueTop(&TBT); QueuePop(&TBT); printf("%d ", front->data); if (front->left) QueuePush(&TBT, front->left); if (front->right) QueuePush(&TBT, front->right); } QueueDestroy(&TBT); }
2.5 二叉树的节点个数
利用递归的方法，左右子树调用，如果该节点为NULL 便会返回0，否则返回1。
//树的结点个数 int TreeSize(BinaryTree* root) { return root == 0 ? 0:TreeSize(root->left) + TreeSize(root->right) + 1; }
2.6 二叉树的深度
利用 left和right记录左右子树的个数，然后比较 选择较大的一个。
如图： 
//树的高度 int TreeHeight(BinaryTree* root) { if (root == NULL) { return 0; } int left = TreeHeight(root->left) ; int right = TreeHeight(root->right); return left > right ? left + 1 : right + 1; }
2.7 二叉树第K层的个数
假设查找第三层，K为3 ，每次递归K–，知道K== 1 的时候 返回1。
//层的个数 int TreeKLevel(BinaryTree* root, int k) { if (root == NULL) { return 0; } if (k == 1) { return 1; } return TreeKLevel(root->left, k - 1) + TreeKLevel(root->right, k - 1); }
2.8 二叉树查找结点
节点的查找，如果节点为NULL饭后NULL，如果此节点的data等于x，返回节点的地址。
//查找节点 BinaryTree* TreeFind(BinaryTree* root, BTTypeData x) { if (root == NULL) { return NULL; } if (root->data == x) { return root; } BinaryTree* lret = TreeFind(root->left, 7); if (lret) return lret; BinaryTree* rret = TreeFind(root->right, 7); if (rret) return rret; return NULL; }
源码
queue.c
#define _CRT_SECURE_NO_WARNINGS #include "queue.h" //初始化 void QueueInit(Queue* ps) { assert(ps); ps->head = ps->tail = NULL; ps->szie = 0; } //销毁 void QueueDestroy(Queue* ps) { assert(ps); QNode* cur = ps->head; while (cur) { QNode* next = cur->next; free(cur); cur = next; } ps->head = ps->tail = NULL; ps->szie = 0; } //入队 void QueuePush(Queue* ps,QDataType x) { assert(ps); QNode* newcode = (QNode*)malloc(sizeof(QNode)); if (newcode == NULL) { perror("malloc fail"); return ; } newcode->next = NULL; newcode->data = x; if (ps->head == NULL) { ps->head = ps->tail = newcode; } else { ps->tail->next = newcode; ps->tail = newcode; } ps->szie++; } //删除 void QueuePop(Queue* ps) { assert(ps); assert(ps->head != NULL); assert(!QueueEmpty(ps)); if (ps->head->next == NULL) { free(ps->head); ps->head = ps->tail = NULL; } else { QNode* next = ps->head->next; free(ps->head); ps->head = next; } ps->szie--; } //大小 int QueueSize(Queue* ps) { assert(ps); return ps->szie; } //判空队 bool QueueEmpty(Queue* ps) { assert(ps); return ps->szie == 0; } //出队头 QDataType QueueTop(Queue* ps) { assert(ps); assert(!QueueEmpty(ps)); return ps->head->data; } //出队尾 QDataType QueueBack(Queue* ps) { assert(ps); return ps->tail->data; }
queue.h
#pragma once #include <stdio.h> #include <assert.h> #include <stdlib.h> #include <stdbool.h> typedef struct BinaryTree* QDataType; typedef struct QNode { struct QNode* next; QDataType data; }QNode; typedef struct Queue { QNode*head; QNode*tail; int szie; }Queue; //单链表的实现，FIFO //初始化 void QueueInit(Queue* ps); //销毁 void QueueDestroy(Queue* ps); //入队 void QueuePush(Queue* ps, QDataType x); //删除 void QueuePop(Queue* ps); //大小 int QueueSize(Queue* ps); //判空队 bool QueueEmpty(Queue* ps); //出队头 QDataType QueueTop(Queue* ps); //出队尾 QDataType QueueBack(Queue* ps);
travelling_binary_tree
#define _CRT_SECURE_NO_WARNINGS #include <stdio.h> #include <stdlib.h> #include <assert.h> #include "queue.h" //定义结构体 typedef int BTTypeData; typedef struct BinaryTree { BTTypeData data; struct BinaryTree* left; struct BinaryTree* right; }BinaryTree; //创建空间 BinaryTree* BuyBinaryTree(BTTypeData x) { BinaryTree* node = (BinaryTree*)malloc(sizeof(BinaryTree)); if (node == NULL) { perror("malloc fail"); return NULL; } node->data = x; node->left = NULL; node->right = NULL; return node; } //建树 BinaryTree* CreateBinaryTree() { BinaryTree* node1 = BuyBinaryTree(1); BinaryTree* node2 = BuyBinaryTree(2); BinaryTree* node3 = BuyBinaryTree(3); BinaryTree* node4 = BuyBinaryTree(4); BinaryTree* node5 = BuyBinaryTree(5); BinaryTree* node6 = BuyBinaryTree(6); BinaryTree* node7 = BuyBinaryTree(7); BinaryTree* node8 = BuyBinaryTree(8); BinaryTree* node9 = BuyBinaryTree(9); node1->left = node2; node1->right = node4; node2->left = node3; node4->left = node5; node4->right = node6; node3->right = node7; node6->left = node8; node6->right = node9; return node1; } //前序遍历 void PreOrder(BinaryTree* root) { if (root == NULL) { //printf("NULL "); return; } printf("%d ", root->data); PreOrder(root->left); PreOrder(root->right); } //中序遍历 void InOrder(BinaryTree* root) { if (root == NULL) { //printf("NULL "); return; } InOrder(root->left); printf("%d ", root->data); InOrder(root->right); } //后序遍历 void PostOrder(BinaryTree* root) { if (root == NULL) { //printf("NULL "); return; } PostOrder(root->left); PostOrder(root->right); printf("%d ", root->data); } //层序遍历 void LevelOrder(BinaryTree* root) { if (root == NULL) { printf("NULL "); return; } Queue TBT; QueueInit(&TBT); if (root) QueuePush(&TBT, root); while (!QueueEmpty(&TBT)) { BinaryTree* front = QueueTop(&TBT); QueuePop(&TBT); printf("%d ", front->data); if (front->left) QueuePush(&TBT, front->left); if (front->right) QueuePush(&TBT, front->right); } QueueDestroy(&TBT); } //树的结点个数 int TreeSize(BinaryTree* root) { return root == 0 ? 0:TreeSize(root->left) + TreeSize(root->right) + 1; } //树的高度 int TreeHeight(BinaryTree* root) { if (root == NULL) { return 0; } int left = TreeHeight(root->left) ; int right = TreeHeight(root->right); return left > right ? left + 1 : right + 1; } //层的个数 int TreeKLevel(BinaryTree* root, int k) { if (root == NULL) { return 0; } if (k == 1) { return 1; } return TreeKLevel(root->left, k - 1) + TreeKLevel(root->right, k - 1); } //查找节点 BinaryTree* TreeFind(BinaryTree* root, BTTypeData x) { if (root == NULL) { return NULL; } if (root->data == x) { return root; } BinaryTree* lret = TreeFind(root->left, 7); if (lret) return lret; BinaryTree* rret = TreeFind(root->right, 7); if (rret) return rret; return NULL; } int main() { BinaryTree* root = CreateBinaryTree(); PreOrder(root); printf("\n"); InOrder(root); printf("\n"); PostOrder(root); printf("\n"); LevelOrder(root); printf("\n"); printf("TreeSize : %d\n", TreeSize(root)); printf("TreeHeight : %d\n", TreeHeight(root)); printf("TreeKLevel : %d\n", TreeKLevel(root, 3)); printf("TreeFind : %p\n", TreeFind(root, 1)); return 0; }
}
//查找节点
BinaryTree* TreeFind(BinaryTree* root, BTTypeData x)
{
if (root == NULL) { return NULL; } if (root->data == x) { return root; } BinaryTree* lret = TreeFind(root->left, 7); if (lret) return lret; BinaryTree* rret = TreeFind(root->right, 7); if (rret) return rret; return NULL;
}
int main()
{
BinaryTree* root = CreateBinaryTree();
PreOrder(root); printf("\n"); InOrder(root); printf("\n"); PostOrder(root); printf("\n"); LevelOrder(root); printf("\n"); printf("TreeSize : %d\n", TreeSize(root)); printf("TreeHeight : %d\n", TreeHeight(root)); printf("TreeKLevel : %d\n", TreeKLevel(root, 3)); printf("TreeFind : %p\n", TreeFind(root, 1)); return 0;
