二叉树的建立跟遍历
学习二叉树的建立和遍历，首先了解一下先序、中序、后序遍历算法:
若二叉树非空，则依次执行如下操作：
1．先序遍历的递归算法定义：
访问根结点-> 遍历左子树-> 遍历右子树。
2. 中序遍历的递归算法定义：
3．后序遍历得递归算法定义：
遍历左子树->遍历右子树->访问根结点。
再看一下完全二叉树特点 若i为某结点位置，n为结点数 对于tree，有如下特点：
a）若i为奇数且i>1，那么tree的左兄弟为tree[i-1]；
b）若i为偶数且i<n，那么tree的右兄弟为tree[i+1]；
c）若i>1，tree的双亲为tree[i div 2]；
d）若2*i<=n，那么tree的左孩子为tree[2*i]；若2*i+1<=n，那么tree的右孩子为tree[2*i+1]；
e）若i>n div 2,那么tree为叶子结点->对应于（c）；
f）若i<(n-1) div 2.那么tree必有两个孩子->对应于（d）。
g）满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树
范例说明：
#include<stdio.h>
#include<stdlib.h>
typedef int datatype;
typedef struct _node{
int no;
struct _node *Lchild,*Rchild;
}bitree;
bitree *create_bitree(int i,int n)//二叉树的建立
{
bitree *root;
root=(bitree*)malloc(sizeof(bitree));
root->no=i;
if(2*i<=n)//若2*i<=n，那么tree的左孩子为tree[2*i]；
root->Lchild=create_bitree(2*i,n);
else
root->Lchild=NULL;
if(2*i+1<=n)//若2*i+1<=n，那么tree的右孩子为tree[2*i+1]；
root ->Rchild=create_bitree(2*i+1,n);
else
root->Rchild=NULL;
return root;
}
void pre_order(bitree *r)//先序遍历(遍历左子树->访问根结点->遍历右子树)
{
if(r==NULL)
return ;
printf("%d->",r->no);
pre_order(r->Lchild);
pre_order(r->Rchild);
}
void in_order(bitree *r)//中序遍历(遍历左子树->访问根结点->遍历右子树)
{
if(r==NULL)
return;
in_order(r->Lchild);
printf("%d->",r->no);
in_order(r->Rchild);
}
void post_oder(bitree *r)//后序遍历(遍历左子树->遍历右子树->访问根结点)
{
if(r==NULL)
return;
post_oder(r->Lchild);
post_oder(r->Rchild);
printf("%d->",r->no);
}
int main()
{
bitree *root;
root=create_bitree(1,12);
printf("先序遍历:");
pre_order(root);
printf("\b\b \n");
root=create_bitree(1,12);
printf("中序遍历:");
in_order(root);
printf("\b\b \n");
root=create_bitree(1,12);
printf("后序遍历:");
post_oder(root);
printf("\b\b \n");
return 0;
}
范例图解：
结果为：先序遍历: 1->2->4->8->9->5->10->11->3->6->12->7
中序遍历：8->4->9->2->10->5->11->1->12->6->3->7
后序遍历：8->9->4->10->11->5->2->12->6->7->3->1