二叉树的实现及应用

• 本文记录二叉树的数据结构定义及基本操作的算法描述，并对算法进行简单应用。
• 采用C语言实现。

源程序

//BiTree.c
#include <stdio.h>
#include <stdlib.h>

//二叉树的数据结构定义
typedef char ElemType;
typedef struct BiTNode{
	ElemType data;
	struct BiTNode *lchild;
	struct BiTNode *rchild;
}BiTNode, *BiTree;

//前序创建二叉树
void CreatBiTree(BiTree *T) {
    ElemType ch;
    scanf("%c", &ch);
    if (ch == '#'){
        *T = NULL;
    }
    else{
        *T = (BiTNode *)malloc(sizeof(BiTNode));
        (*T)->data = ch;
        CreatBiTree(&(*T)->lchild);
        CreatBiTree(&(*T)->rchild);
    }
}

//前序遍历
void PreOrderTraversal (BiTree T) {
    if (T) {
        printf("%c", T->data);
        PreOrderTraversal (T->lchild);
        PreOrderTraversal (T->rchild);
    }
}

//中序遍历
void InOrderTraversal (BiTree T) {
    if (T) {
        InOrderTraversal( T->lchild );
        printf("%c", T->data);
        InOrderTraversal( T->rchild );
    }
}

//后序遍历
void PostOrderTraversal (BiTree T) {
    if (T) {
        PostOrderTraversal( T->lchild );
        PostOrderTraversal( T->rchild );
        printf("%c", T->data);
    }
}
int main() {
	BiTree T;

	printf("Create  Binary Tree:");
	CreatBiTree(&T);
	printf("\n");

	printf("PreOrder:");
	PreOrderTraversal(T);
	printf("\n\n");

	printf("InOrder:");
	InOrderTraversal(T);
	printf("\n\n");

	printf("PostOrder:");
	PostOrderTraversal(T);
	printf("\n\n");

	return 0;
}

运行结果

Create  Binary Tree:ABD###C#F##

PreOrder:ABDCF

InOrder:DBACF

PostOrder:DBFCA