数据结构之二叉树的遍历与存储程序(数据结构实验之二叉树二遍历二叉树)

导语：数据结构之二叉树的遍历

基本概念：

每个结点最多有两棵子树，左子树和右子树。

性质：

1、非空二叉树的第n层上至多有2^(n-1)个元素。

2、深度为h的二叉树至多有2^h-1个结点。

满二叉树：所有终端都在同一层次，且非终端结点的度数为2。

在满二叉树中若其深度为h，则其所包含的结点数必为2^h-1。

完全二叉树：除了最大的层次即成为一颗满二叉树且层次最大那层所有的结点均向左靠齐，即集中在左面的位置上，不能有空位置。

对于完全二叉树，设一个结点为i则其父节点为i/2，2i为左子节点，2i+1为右子节点。

存储结构

二叉树的存储结构可以采用顺序存储，也可以采用链式存储，其中链式存储更加灵活。

在链式存储结构中，与线性链表类似，二叉树的每个结点采用结构体表示，结构体包含三个域：数据域、左指针、右指针。

在C语言中的定义

定义二叉树

二叉树的遍历

遍历即将树的所有结点访问且仅访问一次。按照根节点位置的不同分为前序遍历，中序遍历，后序遍历。

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

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

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

遍历下面这个二叉树

前序遍历：abdefgc

中序遍历：debgfac

后序遍历：edgfbca

代码实现( q是头指针)

前序遍历

中序遍历

后序遍历

本文内容由小春整理编辑！