哎哟，不晓得哪里错了，各位大哥帮帮忙呗！O(∩_∩)O谢谢
/*2011年10月7日16:44:06二叉树结构示例
*/
# include <stdio.h>
# include <conio.h>
# include <stdlib.h>
# define MANLEN 20
//准备数据
typedef char DATA;
typedef struct CBT
{
DATA data;
struct CBT * left;
struct CBT * right;
}CBTType;
//初始化二叉树
CBTType * InitTree()
{
CBTType * node;
if (node=(CBTType * )malloc(sizeof(CBTType)))
{
printf("请输入根结点数据:\n");
scanf("%s", &node->data);
node->left = NULL;
node->right = NULL;
/*if (node != NULL)
{
return node;
}
else
{
return NULL;
}*/
return NULL;
}
printf("申请内存失败!\n");
return NULL;
}
//添加结点
void AddTreeNode(CBTType * treeNode)
{
CBTType * TreeFindNode(CBTType * treeNode, DATA data);
CBTType * pnode, * parent;
DATA data;
char menusel;
if (pnode=(CBTType * )malloc(sizeof(CBTType)))
{
printf("输入二叉树结点数据:\n");
fflush(stdin);
scanf("%s", &data);
parent = TreeFindNode(treeNode, data);
if (!parent)
{
printf("未找到该父结点:\n");
free(pnode);
return;
}
printf("1.添加该结点到左子树\n2.添加该结点到右子树\n");
do
{
menusel = getchar();
menusel -= '0';
if (menusel == 1 || menusel == 2)
{
if (parent == NULL)
{
printf("不存在父结点，先设置父结点!\n");
}
else
{
switch(menusel)
{
case 1:
if (parent->left)
{
printf("左子树结点不为空!\n");
}
else
{
parent->left = pnode;
}
break;
case 2:
if (parent->right)
{
printf("右子树结点不为空!\n");
}
else
{
parent->right = pnode;
}
break;
default:
printf("无效参数!\n");
}
}
}
}while (menusel != 1 && menusel != 2);
}
}
//查找结点
CBTType * TreeFindNode(CBTType * treeNode, DATA data)
{
CBTType * ptr;
if (treeNode == NULL)
{
return NULL;
}
else
{
if (treeNode->data == data)
{
return treeNode;
}
else
{
if (ptr=TreeFindNode(treeNode->left, data))
{
return ptr;
}
else if (ptr=TreeFindNode(treeNode->right, data))
{
return ptr;
}
else
{
return NULL;
}
}
}
}
//获取左子树
CBTType * TreeLeftNode(CBTType * treeNode)
{
if (treeNode)
{
return treeNode->left;
}
else
{
return NULL;
}
//return treeNode;
}
//获取右子树
CBTType * TreeRightNode(CBTType * treeNode)
{
if (treeNode)
{
return treeNode->right;
}
else
{
return NULL;
}
}
//判断空树
int TreeIsEmpty(CBTType * treeNode)
{
if (treeNode)
{
return 0;
}
else
{
return 1;
}
}
//计算二叉树的深度
int TreeDepth(CBTType * treeNode)
{
int depleft, depright;
if (treeNode == NULL)
{
return 0;
}
else
{
depleft = TreeDepth(treeNode->left);
depright = TreeDepth(treeNode->right);
if (depleft > depright)
{
return depleft+1;
}
else
{
return depright+1;
}
}
}
//清空二叉树
void ClearTree(CBTType * treeNode)
{
if (treeNode)
{
CLearTree(treeNode->left);
ClearTree(treeNode->right);
free(treeNode);
treeNode = NULL;
}
}
//显示结点数据
void TreeNodeData(CBTType * p)
{
printf("%c", p->data);
}
//遍历二叉树
//1.按层遍历算法
void LevelTree(CBTType * treeNode, void(*TreeNodeData)(CBTType * p))
{
CBTType * p;
CBTType * q[MANLEN];
int head = 0, tail = 0;
if (treeNode)
{
tail = (tail+1)%MANLEN;
q[tail] = treeNode;
}
while (head != tail)
{
head = (head+1)%MANLEN;
p = q[head];
TreeNodeData(p);
if (p->left != NULL)
{
tail = (tail+1)%MANLEN;
q[tail] = p->left;
}
if (p->right != NULL)
{
tail = (tail+1)%MANLEN;
q[tail] = p->right;
}
}
}
//2.先序遍历算法
void DLRTree(CBTType * treeNode, void( * TreeNodeData)(CBTType * p))
{
if (treeNode)
{
TreeNodeData(treeNode);
DLRTree(treeNode->left, TreeNodeData);
DLRTree(treeNode->right, TreeNodeData);
}
}
//3.中序遍历算法
void LDRTree(CBTType * treeNode, void( * TreeNodeData)(CBTType * p))
{
if (treeNode)
{
LDRTree(treeNode->left, TreeNodeData);
TreeNodeData(treeNode);
LDRTree(treeNode->right, TreeNodeData);
}
}
//后序遍历算法
void LRDTree(CBTType * treeNode, void( * TreeNodeData)(CBTType * p))
{
if (treeNode)
{
LRDTree(treeNode->left, TreeNodeData);
LRDTree(treeNode->right, TreeNodeData);
TreeNodeData(treeNode);
}
}
int main(void)
{
CBTType * root = NULL;
char menusel;
void( * TreeNodeData1)();//指向函数的指针，括号中没有参数即可为任意参数
TreeNodeData1 = TreeNodeData;//指向具体操作的函数
//设置根元素
root = InitTree();
//添加结点
do
{
printf("请选择菜单添加二叉树的结点\n");
printf("0, 退出\t");
printf("1,添加二叉树的结点\n");
fflush(stdin);
menusel = getchar();
switch(menusel)
{
case '1':
AddTreeNode(root);
break;
case '0':
break;
default:
;
}
}while (menusel != '0');
//遍历
do
{
printf("请选择菜单遍历二叉树， 输入0表示退出:\n");
printf("1.先序遍历DLR\t");
printf("2.中序遍历LDT\t");
printf("3.后序遍历LRD\t");
printf("4.按层遍历\t");
fflush(stdin);
menusel = getchar();
switch(menusel)
{
case '0':
break;
case '1':
printf("\n先序遍历DLR的结果: ");
DLRTree(root, TreeNodeData1);
printf("\n");
break;
case '2':
printf("\n中序LDR遍历的结果: ");
LDRTree(root, TreeNodeData1);
printf("\n");
break;
case '3':
printf("\n后序遍历LRD的结果: ");
LRDTree(root, TreeNodeData1);
printf("\n");
break;
case '4':
printf("\n按层遍历的结果: ");
LevelTree(root, TreeNodeData1);
printf("\n");
break;
default:
;
}
}while (menusel != '0');
//深度
printf("\n二叉树的深度为:%d\n", TreeDepth(root));
ClearTree(root);
root = NULL;
return 0;
}
