二叉树的链式存储结构
二叉树有不同的链式存储结构,其中最常用的是二叉链表与三叉链表。
二叉链表的类型定义
typedef struct btnode
{
DataType data;
struct btnode *lchild, *rchild; // 指向左右孩子的指针
} *BinTree;
BinTree root; // root 为指向根结点的指针
三叉链表的类型定义
typedef struct ttnode
{
DataType data;
struct ttnode *lchild, *parent, *rchild; // parent 为指向双亲的指针
} *TBinTree;
TBinTree root; // root 为指向根结点的指针
二叉树遍历的递归实现
假定 visit(bt)
是一个已定义的过程,其功能是访问指针 bt 所指结点。
// 先序遍历根指针为 bt 的二叉树
void preorder(BinTree bt)
{
if (bt != NULL) {
visit(bt); // 访问根结点 bt
preorder(bt->lchild); // 先序遍历左子树
preorder(bt->rchild); // 先序遍历右子树
}
}
// 中序遍历根指针为 bt 的二叉树
void inorder(BinTree bt)
{
if (bt != NULL) {
inorder(bt->lchild); // 中序遍历左子树
visit(bt); // 访问根结点 bt
inorder(bt->rchild); // 中序遍历右子数
}
}
// 后序遍历根指针为 bt 的二叉树
void postorder(BinTree bt)
{
if (bt != NULL) {
postorder(bt->lchild); // 后序遍历左子树
postorder(bt->rchild); // 后序遍历右子数
visit(bt); // 访问根结点 bt
}
}