关于树的定义，从书上摘抄点过来。
树是n(>=0)个结点的有限集，在这个结点集合中，存在一下关系：
- 树中存在唯一的一个结点无前趋，这个结点称为树根
- 除了除根结点外，其他每个结点都有且仅有一个直接前趋
- 树中每个结点都可以有多个后继，无后继的结点成为树叶
二叉树的定义：
- 有一个特定的称为根的结点
- 根结点以外的其余结点分别由两棵互不相交的称为左子树和右子树的二叉树组成。
满二叉树：
深度为k且含有2的K次方-1个结点的二叉树称为满二叉树。除了最后一层为叶结点外，所有其他结点都有左右两个子女。
完全二叉树：
深度为k，含有那个结点的二叉树，当且尽当每个结点的编号与相应满二叉树结点顺序号1~n对应时，称此二叉树为完全二叉树。
对二叉树的操作主要有遍历，分为先序/中序/后序遍历。下面的代码实现了二叉树的遍历操作。遍历的核心是递归。
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 50
typedef struct node
{
char data;
struct node *lchild;
struct node *rchild;
}BTNode;
BTNode *BTNode_Create(char *str); //创建一个二叉树
void BTNode_Show(BTNode *p); //输出显示一个二叉树
void BTNode_PreOrder(BTNode *p); //先序遍历
void BTNode_MidOrder(BTNode *p); //中序遍历
void BTNode_PostOrder(BTNode *p); //后序遍历
int main(void)
{
char *str = NULL;
BTNode *p = NULL;
int choice;
str = (char*)malloc(MAXSIZE);
printf("二叉树操作练习\n");
printf("输入一个二叉树(嵌套括号表示法):\n");
gets(str);
p = BTNode_Create(str);
printf("输出生成的二叉树\n");
BTNode_Show(p);
printf("\n");
while(1)
{
printf("二叉树遍历练习\n");
printf("1.先序遍历\n");
printf("2.中序遍历\n");
printf("3.后序遍历\n");
printf("4.退出程序\n");
printf("做出选择:\n");
scanf("%d", &choice);
switch(choice)
{
case 1:
BTNode_PreOrder(p);
printf("\n");
break;
case 2:
BTNode_MidOrder(p);
printf("\n");
break;
case 3:
BTNode_PostOrder(p);
printf("\n");
break;
case 4:
return 1;
break;
default:
break;
}
}
return 0;
}
//嵌套括号法创建二叉树
BTNode *BTNode_Create(char *str)
{
BTNode *s[MAXSIZE], *p, *B = NULL;
int i = 0, top = -1, flag;
char ch;
ch = str[0];
while(ch != '\0')
{
switch(ch)
{
case '(': //上个结点为根结点.根结点入栈，下个结点为左孩子
top++;
s[top] = p;
flag = 1;
break;
case ')': //左右孩子处理完毕，根结点出栈
top--;
break;
case ',': //表示下个结点为右孩子
flag = 2;
break;
default:
p = (BTNode*)malloc(sizeof(BTNode));
p->data = ch;
p->lchild = NULL;
p->rchild = NULL;
if(B == NULL) //B为空，表示当前输入的为根结点
B = p;
else
if(flag == 1) //左孩子
s[top]->lchild = p;
else if(flag == 2) //右孩子
s[top]->rchild = p;
break;
}
i++;
ch = str[i];
}
return B;
}
//输出显示二叉树
void BTNode_Show(BTNode *p)
{
if(p != NULL)
{
printf("%c", p->data);
if(p->lchild != NULL || p->rchild != NULL)
{
printf("(");
BTNode_Show(p->lchild); //递归处理
if(p->rchild != NULL)
{
printf(",");
BTNode_Show(p->rchild);
}
printf(")");
}
}
}
//先序遍历
void BTNode_PreOrder(BTNode *p)
{
if(p != NULL)
{
putchar(p->data);
BTNode_PreOrder(p->lchild); //递归处理
BTNode_PreOrder(p->rchild);
}
}
//中序遍历
void BTNode_MidOrder(BTNode *p)
{
if(p != NULL)
{
BTNode_MidOrder(p->lchild); //递归处理
putchar(p->data);
BTNode_MidOrder(p->rchild);
}
}
//后序遍历
void BTNode_PostOrder(BTNode *p)
{
if(p != NULL)
{
BTNode_PostOrder(p->lchild); //递归处理
BTNode_PostOrder(p->rchild);
putchar(p->data);
}
}