数据
结构

二叉树的遍历

一、树

在谈二叉树的知识点之前，我们首先来看一下树和图的基本概念。

树：不包含回路的连通无向图，树是一种简单的非线性结构。

由于树有一个不包含回路的特点，因此树被赋予了许多特性，如下所示：

1、一棵树中任意的两个结点有且仅有唯一的一条路径连通
2、一棵树如果有n个结点，那么它一定恰好有n-1条边
3、在一棵树中加上一条边，将会构成一个回路
4、一棵树中有且仅有一个没有前驱的结点，即为根结点

通常情况下，我们在对树进行讨论的时候，将一棵树中的每个点称为结点:

根结点：没有父结点的结点
叶结点：没有子结点的结点
内部结点：一个结点既不是根结点也不是叶结点

每个结点有一个深度的概念，例如上图左边的树，4号结点深度是3。

二、二叉树

1. 基本概念

二叉树是一种非线性结构，二叉树是由递归定义的，其结点有左右子树之分。

2. 二叉树的存储结构

二叉树一般采用链式存储结构，存储结点由数据域和指针域组成，二叉树的链式存储结构也称为二叉链表。

指针域：左指针域和右指针域

特点：

1、每个结点最多有两颗子树
2、左子树和右子树是有顺序的，次序不能颠倒
3、即使某个结点只有一颗子树，也要区分左右子树
4、二叉树可为空，空的二叉树没有结点，非空二叉树有且仅有一个根节点

二叉树中有两种比较特殊的二叉树：满二叉树、完全二叉树，对于满二叉树和完全二叉树可以按照层次进行顺序存储。

满二叉树：二叉树中每个内部结点都存在左子树和右子树

满二叉树一定是完全二叉树，但完全二叉树不一定是满二叉树。

满二叉树的严格定义：一颗深度为h且具有2^h-1个结点的二叉树。

完全二叉树：

解释一：如果一颗二叉树除了最右边位置上有一个或几个叶结点缺少外，其他都是丰满的，那么这样的二叉树就是完全二叉树。

解释二：除第h层外，其他各层（1到h-1）的结点数都达到最大个数，第h层从右向左连续缺若干结点，则这个二叉树就是完全二叉树。

也就是说如果一个结点有右子结点，那么它一定也有左子结点。

解释三：除了最后一层外，每一层上的节点数均达到最大值，在最后一层上只缺少右边的若干结点。

完全二叉树的形状类似于下图：

为了方便理解，请看下图：

二叉树相关名词解释：

结点的度：结点拥有的子树数目
叶子结点：度为0的结点
分支结点：度不为0的结点
树的度：树中结点的最大的度
层次：根结点的层次为1，其余结点的层次等于该结点的双亲结点的层次加1
树的高度：树中结点的最大层次

二叉树基本性质：

性质1：在二叉树的第k层上至多有2^k-1个结点（k>=1）
性质2：在深度为m的二叉树至多有2^m-1个结点
性质3：对任意一颗二叉树，度为0的结点（即叶子结点）总是比度为2的结点多一个
性质4：具有n个结点的完全二叉树的深度至少为[log2n]+1，其中[log2n]表示log2n的整数部分

存储方式

存储方式和图一样，有链表和数组两种，用数组存储访问速度快，但插入、删除节点操作比较费时。实际应用中，更多的是采用链来表示二叉树。

实现代码：

#include <stdio.h>#include <stdlib.h>#define N 10typedef struct node{ char data; struct node *lchild; /* 左子树 */ struct node *rchild; /* 右子树 */}BiTNode, *BiTree;void CreatBiTree (BiTree *T) /* BiTree *T等价于 struct node **T */{ char ch; scanf("%c", &ch); if (ch == '#') /* 当遇到#时，令树的结点为NULL，从而结束该分支的递归 */ { *T = NULL; } else { *T = (BiTree)malloc(sizeof(BiTNode)); if (*T == NULL) { printf("内存分配失败"); exit(0); } (*T)->data = ch; /* 生成结点 */ CreatBiTree(&(*T)->lchild); /* 构造左子树 */ CreatBiTree(&(*T)->rchild); /* 构造右子树 */ /* 这里需要注意的是->的优先级比&高，所以&(*T)->lchild得到的是lchild的地址 */ }}int main(){ int level = 1; BiTree t = NULL; printf("以前序遍历方式输入二叉树\n"); CreatBiTree(&t); /* 传入指针的地址 */}

上面的实现代码使用的是链表，代码采用的是以前序遍历方式输入二叉树，当输入“#”时，指针指向NULL，说明是该结点是叶结点。

三、二叉树的遍历（前序/中序/后序遍历）

二叉树的遍历，是指不重复地访问二叉树中所有结点，主要指非空二叉树，对于空二叉树则结束返回，二叉树的遍历主要包括前序遍历、中序遍历、后序遍历。

前序遍历：首先访问根结点，然后遍历左子树，最后遍历右子树（根->左->右）

顺序：访问根节点->前序遍历左子树->前序遍历右子树

/* 以递归方式前序遍历二叉树 */void PreOrderTraverse(BiTree t, int level){ if (t == NULL) { return ; } printf("data = %c level = %d\n ", t->data, level); PreOrderTraverse(t->lchild, level + 1); PreOrderTraverse(t->rchild, level + 1);}

中序遍历：首先遍历左子树，然后访问根节点，最后遍历右子树（左->根->右）

顺序：中序遍历左子树->访问根节点->中序遍历右子树

/* 以递归方式中序遍历二叉树 */void PreOrderTraverse(BiTree t, int level){ if (t == NULL) { return ; } PreOrderTraverse(t->lchild, level + 1); printf("data = %c level = %d\n ", t->data, level); PreOrderTraverse(t->rchild, level + 1);}

后序遍历：首先遍历左子树，然后遍历右子树，最后访问根节点（左->右->根）

顺序：后序遍历左子树->后序遍历右子树->访问根节点

/* 以递归方式后序遍历二叉树 */void PreOrderTraverse(BiTree t, int level){ if (t == NULL) { return ; } PreOrderTraverse(t->lchild, level + 1); PreOrderTraverse(t->rchild, level + 1); printf("data = %c level = %d\n ", t->data, level);}

综上所述，我们主要讲解了树、图、二叉树以及遍历的基本知识点。从上面的分析中我们可以看出，树的三种遍历方式极其相似，只是语句 printf的位置发生了一些变化，其他语言实现类似，大家可自行实现。

Bilibili : 洛必达数数

CSDN博客：算法之美DL

GitHub：statisticszhang

数据结构—树|二叉树|前序遍历、中序遍历、后序遍历【图解实现】