数据结构之二叉树的遍历

一、基本概念

每个结点最多有两棵子树，左子树和右子树，次序不可以颠倒。

性质：

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

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

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

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

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

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

二、存储结构

顺序存储：

将数据结构存在一块固定的数组中。

[cpp] view plain copy print?

#define LENGTH 100

typedef char datatype;

typedef struct node{

datatype data;

int lchild,rchild;

int parent;

}Node;

Node tree[LENGTH];

int length;

int root;

虽然在遍历速度上有一定的优势，但因所占空间比较大，是非主流二叉树。二叉树通常以链式存储。

链式存储：

[cpp] view plain copy print?

typedef char datatype;

typedef struct BinNode{

datatype data;

struct BinNode* lchild;

struct BinNode* rchild;

}BinNode;

typedef BinNode* bintree;          //bintree本身是个指向结点的指针

三、二叉树的遍历

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

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

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

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

例如：求下面树的三种遍历

前序遍历：abdefgc

中序遍历：debgfac

后序遍历：edgfbca

网易有道二叉树的题如下：

设某棵二叉树的中序遍历序列为BADC，前序遍历序列为ABCD，则后序遍历该二叉树得到序列为（）.

A. BADC

B. BDCA

C. BCDA

D. CBDA

根据前序遍历可以看出根为A，B为左子树，由于前序和中序右子树正好相反，所有C是跟，D是C的左子树。

后序遍历的顺序是左右跟，因此就是B  ，D，C，A。