二叉树的链式存储结构

二叉树有不同的链式存储结构，其中最常用的是二叉链表与三叉链表。

二叉链表的类型定义

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 
    } 
}