二叉树的创建与遍历

按照根节点N、左子树L、右子树R的访问顺序分为：先序（NLR)、中序(LNR)和后序(LRN)三种遍历算法。

使用链式存储结构的二叉树的创建与遍历代码如下：

#include
#include

#define OVERFLOW -2
#define NULL_TREE '.'

typedef char TElemType;

typedef struct BiTNode {
    TElemType data;	// 数据域
    struct BiTNode* lchild, * rchild;	// 左右孩子指针
}BiTNode, * BiTree;

// 建二叉树
void CreateBiTree(BiTree& T) {
    // 按照先序次序输入二叉树中结点的值， '.'表示空树
    char ch;
    scanf(" %c", &ch);
    if (ch == NULL_TREE) T = NULL;
    else {
        if (!(T = (BiTNode*)malloc(sizeof(BiTNode)))) exit(OVERFLOW);   // 内存空间不够，退出程序
        T->data = ch;
        CreateBiTree(T->lchild);  // 递归构造左子树
        CreateBiTree(T->rchild);  // 递归构造右子树
    }
}

void visit(BiTree Node) {
    printf("%c ", Node->data);
}

// 先序遍历
void PreOrder(BiTree T) {
    if (T != NULL) {
        visit(T);	//访问根结点
        PreOrder(T->lchild);	// 递归遍历左子树
        PreOrder(T->rchild);	// 递归遍历右子树
    }
}

// 中序遍历
void InOrder(BiTree T) {
    if (T != NULL) {
        InOrder(T->lchild); // 递归遍历左子树
        visit(T);	// 访问根节点	
        InOrder(T->rchild);	// 递归遍历右子树
    }
}

// 后序遍历
void PostOrder(BiTree T) {
    if (T != NULL) {
        PostOrder(T->lchild);	// 递归遍历左子树
        PostOrder(T->rchild);	// 递归遍历右子树
        visit(T);				// 访问根节点
    }
}

int main() {
    BiTree btree;

    
    CreateBiTree(btree);     // 建树
    // 先序遍历
    PreOrder(btree); printf("n");
    
    // 中序遍历
    InOrder(btree); printf("n");
    
    // 后序遍历
    PostOrder(btree); printf("n");
    
    return 0;
}

建立的树如下图所示

三种遍历算法中，遍历左、右子树的顺序都是固定的，只是访问根结点的顺序不同。
不管采用哪种遍历算法，每个结点都访问一次且仅访问一次，故时间复杂度都是O(n)。
在递归遍历中，递归工作栈的栈深恰好为树的深度，所以在最坏情况下，二叉树是有n个结点且深度为n的单支树，遍历算法的空间复杂度为O(n)。