#include
#include
#include
typedef struct btnode
{char data; /*suppose the data field's type is char*/
struct btnode *lchild; /*left pointer field */
struct btnode *rchild; /*right pointer field */
}NODE;
void main()
{ NODE *root,*q,n;
NODE *create(NODE *p);
void preorder(NODE *root);
void inorder(NODE *root);
void postorder(NODE *root);
int t;
q=&n;
root=create(q);
printf("At the first,we create a tree\n");
printf("Please input nodes of tree\n");
if (root==NULL) printf("It's an empty tree!\n");
else
{
printf("\n1.The preordetraverse \n");
printf(" 2.The inordertraverse \n");
printf(" 3.The postordertraverse \n");
printf(" Please choose a kind of order\n");
scanf("%d",&t);
switch (t)
{
case 1: preorder(root); break;
case 2: inorder(root); break;
case 3:postorder(root); break;
default: printf(" The error!");
}
}
}
NODE * create(NODE *p) /*create the structure of binary tree */
{ char ch;
NODE *t;
scanf("%c",&ch);
if(ch==' ') p=NULL;//如果输入的ch为空，那么只能创建一个空树了
else
{p->data=ch;//data=ch;
t=(NODE *)malloc(sizeof(NODE));
/*
*创建左孩子（或者左子树），并给赋值给p->lchild，
*如果执行这条语句时p->lchild=create(t);，输入ch为空，那么p->lchild=NULL,
*如果创建右孩子（或者右子树），也和左孩子（或者左子树）一样时，
*这种情况是最简单的一种，只创建了单个节点的树，
* （root）
* / \
* (null) (null)
*还有一种就是，你输入（r,a,' ',b,' '）,这时创建树
* （r）
* / \
* （a）（b）
*/
p->lchild=create(t);
t=(NODE*)malloc(sizeof(NODE));
p->rchild=create(t);
}
return p;
}
void preorder(NODE *root) /*travel the tree using preorder */
{
/*
*前序遍历树，这里是递归调用，先遍历根，然后遍历左子树，最后是遍历右子树
*比如：
* （r）
* / \
* (a) (b)
* / \ /
* (c)(d) (f)
*那遍历是，先是输出r,然后遍历左子树，输出根a，然遍历根（a）的左子树（c），
*c没有左子树，然后遍历根（a）的右子树，输出d，根为（a）树遍历完了，就遍历根为（r）的右子树
*就输出（d），（f）
*最终遍历顺序（r-a-c-d-b-f）
*/
if (root!=NULL)
{ printf( " %c", root->data);
preorder(root->lchild);
preorder(root->rchild);
}
return;
}
void inorder (NODE *root) /*travel the tree using inorder */
{
/*
*这个是中序遍历，思想和前序遍历一样的，只是改变了遍历顺序，
*它是先左子树，根，后右子树
* （r）
* / \
* (a) (b)
* / \ /
* (c)(d) (f)
*这个树的遍历顺序是：（c-a-d-r-f-b）,根都在中间，如根为（a）的子树（c-a-d）
*/
if (root!=NULL)
{ inorder(root->lchild);
printf(" %c ", root->data);
inorder(root->rchild);
}
return;
}
void postorder(NODE *root) /*travel the tree using postorder */
{
/*
*后序遍历，它的顺序是（左，右，根），还是以上面的树为例：
*遍历顺序为：c-d-a-f-b-r.注意，根都在后面，如根r，根a，根b
*/
if (root!=NULL)
{ postorder (root->lchild);
postorder (root->rchild);
printf(" %c ", root->data);
}
return;
} |
转播
