C语言二叉树遍历超详图解

拼搏现实的明天。 2024-04-18 06:29 16阅读 0赞

[https://www.360kuai.com/pc/9e7aac6a61fdb56a3?cota=4&sign=360\_57c3bbd1&refer\_scene=so\_1][https_www.360kuai.com_pc_9e7aac6a61fdb56a3_cota_4_sign_360_57c3bbd1_refer_scene_so_1]

二叉树的顺序存储结构就是用一维数组存储二叉树中的节点，并且节点的存储位置，也就是数组的下标要能体现节点之间的逻辑关系。—–>一般只用于完全二叉树

![format_png][]

**链式存储—–>二叉链表**

定义： lchild | data | rchild（两个指针域，一个数据域）

typedef struct Node { ElemType data; struct Node *lchild, *rchild;}BiTnode,* BiTree;

**注意点：**

1）已知 **前序遍历序列** 和 **中序遍历序列**，**可以唯一确定一颗二叉树**

2）已知 **中序遍历序列**和 **后序遍历序列**，**可以唯一确定一颗二叉树**

而已知 前序和后序 是不能确定一颗二叉树的

**二叉树的遍历：**是指从根节点出发，按照某种次序依次访问二叉树中的所有节点，使得每个节点被访问一次且仅被访问一次。

**1、前序遍历：根-左-右**

![format_png 1][]

代码：

void PreOrder(BiTree T) /*先序遍历: 根-左-右*/{ if(T != NULL) { Visit(T); /*访问根节点*/ PreOrder(T->lchild); /*访问左子节点*/ PreOrder(T->rchild); /*访问右子节点*/ }}

**2、中序遍历：左-根-右**

![format_png 2][]

代码：

void InOrder(BiTree T)/*中序遍历：左-根-右*/{ if(T != NULL) { InOrder(T->lchild); //左 Visit(T); //根 InOrder(T->rchild); //右 }}

**3、后序遍历：左-右-根**

![format_png 3][]

代码：

void PostOrder(BiTree T)/*后序遍历：左-右-根*/{ if(T != NULL) { PostOrder(T->lchild); //左 PostOrder(T->rchild); //右 Visit(T); //根 }}

**4、层序遍历：从根节点出发，依次访问左右孩子结点，再从左右孩子出发，依次它们的孩子结点，直到节点访问完毕**

![format_png 4][]

代码：该程序用到了队列的思想，可以参考下图理解

（该图为展示的是 **图的广度优先遍历示意图，应用的就是层序遍历的思想**）

/*层序遍历 思路：按从左至右的顺序来逐层访问每个节点，层序遍历的过程需要队列*/void LevelOrder(BiTree T){ BiTree p = T; queue queue; /*队列*/ queue.push(p); /*根节点入队*/ while(!queue.empty()) /*队列不空循环 */ { p = queue.front(); /*对头元素出队*/ //printf("%c ",p->data); /*访问p指向的结点*/ cout <<>data <<>

queue.pop(); /\*退出队列\*/ if(p->lchild != NULL)\{ /\*左子树不空，将左子树入队\*/ queue.push(p->lchild); \} if(p->rchild != NULL)\{ /\*右子树不空，将右子树入队\*/ queue.push(p->rchild); \} \}\}

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5nX21pbnM5OTk_size_16_color_FFFFFF_t_70][]

[https_www.360kuai.com_pc_9e7aac6a61fdb56a3_cota_4_sign_360_57c3bbd1_refer_scene_so_1]: https://www.360kuai.com/pc/9e7aac6a61fdb56a3?cota=4&sign=360_57c3bbd1&refer_scene=so_1
[format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9wMC5zc2wucWhpbWdzNC5jb20vdDAxZGYzNzVhOTBkMmNiYTc4OC5qcGc?x-oss-process=image/format,png
[format_png 1]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9wMC5zc2wucWhpbWdzNC5jb20vdDAxYjZiZWU3MjIxYzczM2I3ZS5qcGc?x-oss-process=image/format,png
[format_png 2]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9wMC5zc2wucWhpbWdzNC5jb20vdDAxZTFlNGFhOWUxMzllYTIwYS5qcGc?x-oss-process=image/format,png
[format_png 3]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9wMC5zc2wucWhpbWdzNC5jb20vdDAxZDI3Mjg0M2M4MzBmNTU4Ni5qcGc?x-oss-process=image/format,png
[format_png 4]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9wMC5zc2wucWhpbWdzNC5jb20vdDAxNDMzMjQ5MGM1ZmQ5MGM3Yi5qcGc?x-oss-process=image/format,png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5nX21pbnM5OTk_size_16_color_FFFFFF_t_70]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/58dfa27050c0432488990edb97f930fb.jpg