数据结构的C++实现之二叉树的遍历和存储结构

数据结构的C++实现之二叉树的遍历和存储结构2013-08-14 csdn Simba888888在《二叉树的定义和性质》中我们已经认识了二叉树这种数据结构。我们知道链表的每个节点可以有一个后继，而二叉树（Binary Tree）的每个节点可以有两个后继。比如这样定义二叉树的节点：

typedef struct node *link;

struct node {

unsigned char item;

link l, r;

};

这样的节点可以组织成下图所示的形态。

二叉树可以这样递归地定义：

1. 就像链表有头指针一样，每个二叉树都有一个根指针（上图中的root指针）指向它。根指针可以是NULL，表示空二叉树，或者

2. 根指针可以指向一个节点，这个节点除了有数据成员之外还有两个指针域，这两个指针域又分别是另外两个二叉树（左子树和右子树）的根指针。

链表的遍历方法是显而易见的：从前到后遍历即可。二叉树是一种树状结构，如何做到把所有节点都走一遍不重不漏呢？有以下几种方法，如下图（来自《linux c 编程一站式学习》）所示：