二叉树是笔试面试中考试最频繁的数据结构之一，主要包括，程序建立一个二叉树，三种次序遍历二叉树，返回叶子节点的数目，求二叉树节点的总数等。建立一个二叉树节点的数据结构

typedef struct Node
{
int data;
struct Node *left,*right;
}Node;，结构体内包括数据，左子树，又子树；

一、建立二叉树的程序代码如下

[cpp] Node *CreatBTree() //建立二叉树
{
Node *t;
int x;
scanf("%d",&x);
if(x==0)
{
t=NULL;
}
else
{
t=(Node*)malloc(sizeof(Node));
t->data=x;
printf("\n请输入%d结点的左子结点:",t->data );
t->left=CreatBTree();
printf("\n请输入%d结点的右子结点:",t->data );
t->right=CreatBTree();
}
return t;
}

Node *CreatBTree() //建立二叉树
{
Node *t;
int x;
scanf("%d",&x);
if(x==0)
{
t=NULL;
}
else
{
t=(Node*)malloc(sizeof(Node));
t->data=x;
printf("\n请输入%d结点的左子结点:",t->data );
t->left=CreatBTree();
printf("\n请输入%d结点的右子结点:",t->data );
t->right=CreatBTree();
}
return t;
}

二、前序遍历二叉树

[cpp] void preVisit(Node *T)
{
if(T==NULL) return;
else
{
printf("%3d",T->data);
preVisit(T->left);
preVisit(T->right);
}
}

void preVisit(Node *T)
{
if(T==NULL) return;
else
{
printf("%3d",T->data);
preVisit(T->left);
preVisit(T->right);
}
}
三、中序遍历二叉树

[cpp] void middVisit(Node *T)
{
if(T==NULL) return;
else
{
middVisit(T->left);
printf("%3d",T->data);
middVisit(T->right);
}
}

void middVisit(Node *T)
{
if(T==NULL) return;
else
{
middVisit(T->left);
printf("%3d",T->data);
middVisit(T->right);
}
}
四、后序遍历二叉树

[cpp] void lastVisit(Node *T)
{
if(T==NULL) return;
else
{
lastVisit(T->left);
lastVisit(T->right);
printf("%3d",T->data);
}
}

void lastVisit(Node *T)
{
if(T==NULL) return;
else
{
lastVisit(T->left);
lastVisit(T->right);
printf("%3d",T->data);
}
}
五、返回叶子节点数目

[cpp] int leafnum(Node *T)
{
if (!T)
{
return 0;
}
else if ((!T->left)&&(!T->right))
{
return 1;
}
else
{
return ((leafnum(T->left)+leafnum(T->right)));
}
}

int leafnum(Node *T)
{
if (!T)
{
return 0;
}
else if ((!T->left)&&(!T->right))
{
return 1;
}
else
{
return ((leafnum(T->left)+leafnum(T->right)));
}
}
六、返回节点总数目

[cpp] view plaincopyprint int Nodenum(Node *T)
{
if (T)
{
return 1+Nodenum(T->left)+Nodenum(T->right);
}
if (T==NULL)
{
return 0;
}

}

int Nodenum(Node *T)
{
if (T)
{
return 1+Nodenum(T->left)+Nodenum(T->right);
}
if (T==NULL)
{
return 0;
}