二叉树的建立与遍历
//二叉树的建立
int i,h;
//根节点，右遍头节点，左边头节点，右边普通节点，左边普通节点，右边叶子，左边叶子
tree *father,*rightson,*leftson,*right_node,*left_node,*left_node_son,*right_node_son;
father=(tree*)malloc(sizeof(tree));//创建根节点
rightson=(tree*)malloc(sizeof(tree));//创建右遍头节点
leftson=(tree*)malloc(sizeof(tree));//创建左边头节点
father->p=0;
printf("tree!\n");
printf("input size=:");//输入树的大小
scanf("%d",&father->data);//把树的大小存入根节点数据域
if (father->data>MAXSIZE){//错误处理，输入大于最大长度
printf("ERROR!");
return ERROR;//返回错误
}
for (i = 0;i < father->data; i++){
right_node=(tree*)malloc(sizeof(tree));//创建右遍的树枝
right_node->data=i;//赋值
right_node_son=(tree*)malloc(sizeof(tree));//创建一个叶子
right_node_son->data=i+1;//给叶子赋值
right_node->right=right_node_son;//树枝的右指针指向叶子
right_node->left=rightson;//指向树枝的下一个节点
rightson=right_node;
}
i=0;
for (i = 0; i <father->data; i++){
left_node=(tree*)malloc(sizeof(tree));//创建左边树枝
left_node->data=i+3;//赋值
left_node_son=(tree*)malloc(sizeof(tree));//创建一个叶子
left_node_son->data=i+2;//给叶子赋值
left_node->left=left_node_son;//树枝的左边指针指向叶子
left_node->right=leftson;//指向树枝的下一个节点
leftson=left_node;
}
首先创建出根节点与两边的尾节点。然后读取二叉树的深度，并存于二叉树的根节点的数据域中。之后通过一个for循环来读取输入，并创建新的节点加入到树上。第一次输入读取输入到树枝节点的数据域，第二次输入读取到树叶节点的数据域。然后树枝节点指向叶子节点，下一步树枝节点指向下一个树枝节点，进行下一次输入操作。
树的形状
树的遍历
代码片：
int preorderoutput(tree *pre_father){
printf("print!\n");
pre_father->p++;//用变量p来结束递归
if (pre_father->p<5){
printf("left=%d\n",pre_father->left->data);//输出
pre_father->left=pre_father->left->left;//指针指向下一个节点
preorderoutput(pre_father);//递归
}
else if (pre_father->p>=5 && pre_father->p<10){
printf("right=%d\n",pre_father->right->data);//输出
pre_father->right=pre_father->right->right;//指针指向下一个节点
preorderoutput(pre_father);//递归
}
return OK;
}
//递归法输出叶子
int print_son(tree *son_father){
printf("print!\n");
son_father->p++;
if (son_father->p>=10 && son_father->p<15){
printf("leftson=%d\n",son_father->left->right->data);//输出
son_father->left=son_father->left->left;//树枝向下
son_father->left->right=son_father->left->right;//指向新的叶子
print_son(son_father);
}
else if(son_father->p>=15 && son_father->p<20){
printf("rightson=%d\n",son_father->right->left->data);//输出
son_father->right=son_father->right->right;//树枝向下
son_father->right->left=son_father->right->left;//指向新的叶子
}
return OK;
方向是有左到右，先输出树枝，在输出叶子。采用了递归的方法。
函数 preorderoutput ：在p的值0-5间时，输出左侧树枝，指针以此指向下一个树枝节点。在5-10间则输出右侧树枝，指针依次指向下一个树枝节点。
函数 print_son ：输出叶子。在p的值在10-15之间，遍历左侧树枝，因为在建立树时已经将树枝节点指向叶子节点，所以可以直接重新赋值叶子节点，来输出叶子的数据域。算是一个不足之处因为想要输出叶子还要在重新从根节点遍历，浪费了额外的时间与空间，影响力算法的效率，所以还需改进！！！