二叉树的实现-BSTree

一、树和二叉树

1-1 树的定义

翻译过来就是：树是由结点构成的，结点可以有也可以没有。若有结点，则肯定只有一个根结点。树是一种递归结构，俗称 “套娃”

1-2 二叉树的定义

翻译过来就是：二叉树是树的一个子集，每一个结点 至多 只能有两个结点（左结点和右结点）

二、二叉树的特性

2-1 二叉树的存储

二叉树的存储结构可以采用 顺序存储 和 链式存储 两种方式。下面示例采用链式存储结构实现

示例中，小小改动，其中名称和结点数据域变化

typedef struct BSTreeNode
{
	int    key;                 // 关键字(键值)
	struct BSTreeNode *left;    // 左孩子
	struct BSTreeNode *right;   // 右孩子
	struct BSTreeNode *parent;  // 父结点
}Node, *BSTree;

2-2 二叉树的遍历

遍历二叉树（traversing binary tree）是指按某条搜索路径巡访树中每一个结点，使得每一个结点均被访问一次，而且仅被访问一次。

“遍历” 是二叉树各种操作的基础，假设访问结点的具体操作不仅仅局限于输出结点数据域的值，而把 “访问” 延申到对结点的判别、计数等其他操作，可以解决一些关于而二叉树的其他实际问题。

根据访问限定先左后右，有3种访问情况，分别称之为 先（根）序遍历、中（根）序遍历和后（根）序遍历

注意：以集合的方式区分左子树和右子树，不能单纯的以左结点、右结点进行遍历