1、定义
typedef struct BiTNode {
char data;
struct BiTNode* lchild, * rchild;
}BiTNode, * BiTree;
typedef BiTree ElemType;
2、二叉树的先中后序遍历
void visit(BiTNode* TN) {
printf("%d", TN->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);
}
}
3、层次遍历
void levelOrder(BiTree T) {
LinkQueue Q;
InitQueue(Q);
BiTree p;
EnQueue(Q, T);
while (!IsEmpty(Q))
{
DeQueue(Q, p);
visit(p);
if (p->lchild != NULL)
EnQueue(Q, p->lchild);
if (p->rchild != NULL)
EnQueue(Q, p->rchild);
}
}
4、二叉树的创建
1)先序+中序
void BuildPreInTree(BiTree &T, char* pre_str, char* in_str, int preL, int preR, int inL, int inR) {
/*
preL,preR是先序区间
inL,inL是中序区间
inRoot_index是根节点下标
*/
T = (BiTNode*)malloc(sizeof(BiTNode));
T->data = pre_str[preL];
int inRoot_index = 0;
if (inL == inR) {
inRoot_index = inL;
}
for (int i = inL; i <= inR ; i++) {
if (in_str[i] == pre_str[preL]) {
inRoot_index = i;
break;
}
}
if (inRoot_index - inL > 0) {
BuildPreInTree(T->lchild, pre_str, in_str, preL + 1, preL + inRoot_index-inL, inL, inRoot_index - 1);
}
else
{
T->lchild = NULL;
}
if (inR - inRoot_index > 0) {
BuildPreInTree(T->rchild, pre_str, in_str, preL + inRoot_index -inL+1, preR, inRoot_index + 1, inR);
}
else {
T->rchild = NULL;
}
}
2)后序+中序
void BuildPostInTree(BiTree& T, char* post_str, char* in_str, int postL, int postR, int inL, int inR) {
/*
T 树的指针
post_str 先序遍历的数组指针
in_str 中序遍历的数组指针
postL,postR 先序遍历数组的范围(左指针和右指针)
inL,inR 中序遍历数组范围(左指针和右指针)
*/
T = (BiTNode*)malloc(sizeof(BiTNode));
T->data = post_str[postR];
int inRoot_index = 0;
if (inR == inL) {
inRoot_index = inR;
}
for (int i = inR; i >= inL; i--) {
in_str[i];
if (post_str[postR] == in_str[i]) {
inRoot_index = i;
break;
}
}
if (inRoot_index - inL > 0) {
BuildPostInTree(T->lchild, post_str, in_str, postL, postR+inRoot_index-inR-1, inL, inRoot_index - 1);
}
else
{
T->lchild = NULL;
}
if (inR - inRoot_index > 0) {
BuildPostInTree(T->rchild, post_str, in_str, postR - inR + inRoot_index, postR - 1, inRoot_index + 1, inR);
}
else
{
T->rchild = NULL;
}
}