1、代码
2、运行结果
3、分析
1、代码
#include <stdio.h>
#include <stdlib.h> typedef struct _Node
{
int value;
struct _Node * pLeft;
struct _Node * pRight;
} Node; Node * getNewNode(int iValue)
{
Node * p = (Node *)malloc(sizeof(Node));
if(NULL != p)
{
p->value = iValue;
p->pLeft = NULL;
p->pRight = NULL;
} return p;
} void deleteNode(Node * p)
{
if(NULL != p)
{
free(p);
}
} int addElm(Node * p, int value)
{
Node * pX = p;
while(pX)
{
if(value < pX->value)
{
if(NULL == pX->pLeft)
{
pX->pLeft = getNewNode(value);
printf("add [%2d] to left of [%2d]\n", value, pX->value);
break;
}
else
{
pX = pX->pLeft;
}
}
else
{
if(NULL == pX->pRight)
{
pX->pRight = getNewNode(value);
printf("add [%2d] to right of [%2d]\n", value, pX->value);
break;
}
else
{
pX = pX->pRight;
}
}
} return ;
} Node * makeBinaryTree(int iList[], int iNum)
{
Node * p = getNewNode(iList[]);
int i = ;
for(i = ; i < iNum; i++)
{
addElm(p, iList[i]);
}
printf("\n"); return p;
} void destroyBinaryTree(Node * p)
{
if(NULL == p)
{
return;
}
destroyBinaryTree(p->pLeft);
destroyBinaryTree(p->pRight);
deleteNode(p);
} int preorderTraversal(Node * p)
{
if(NULL == p)
{
return -;
}
printf("%2d ", p->value);
preorderTraversal(p->pLeft);
preorderTraversal(p->pRight);
return ;
} int postorderTraversal(Node * p)
{
if(NULL == p)
{
return -;
}
postorderTraversal(p->pLeft);
postorderTraversal(p->pRight);
printf("%2d ", p->value);
return ;
} int inorderTraversal(Node * p)
{
if(NULL == p)
{
return -;
}
inorderTraversal(p->pLeft);
printf("%2d ", p->value);
inorderTraversal(p->pRight);
return ;
} void preTrvl(Node * p)
{
printf("pre : ");
preorderTraversal(p);
printf("\n");
} void postTrvl(Node * p)
{
printf("post : ");
postorderTraversal(p);
printf("\n");
} void inTrvl(Node * p)
{
printf("in : ");
inorderTraversal(p);
printf("\n");
} void printList(int iList[], int iNum)
{
for(int i = ; i < iNum; i++)
{
printf("%d ", iList[i]);
}
printf("\n");
} int main()
{
int iList[] = {, , , , , , , , , , , };
int iNum = ; printList(iList, iNum);
Node * p = makeBinaryTree(iList, iNum);
preTrvl(p);
postTrvl(p);
inTrvl(p);
destroyBinaryTree(p);
}
2、运行结果
$ ./binaryTree add [ ] to right of [ ]
add [ ] to left of [ ]
add [ ] to left of [ ]
add [ ] to right of [ ]
add [ ] to left of [ ]
add [ ] to left of [ ]
add [ ] to left of [ ]
add [] to right of [ ]
add [ ] to left of [ ]
add [] to left of []
add [] to right of [] pre :
post :
in :
3、分析
从运行结果的第三行开始，就是开始进行数据插入的地方，下面对运行结果中，每一行插入动作后二叉树的情况进行画图描述。
第03行：add [ 9] to right of [ 6] 第04行：add [ 8] to left of [ 9]
第05行：add [ 3] to left of [ 6] 第06行：add [ 5] to right of [ 3]
第07行：add [ 4] to left of [ 5] 第08行：add [ 7] to left of [ 8]
第09行：add [ 2] to left of [ 3] 第10行：add [12] to right of [ 9]
第11行：add [ 1] to left of [ 2]
第12行：add [10] to left of [12]
第13行：add [11] to right of [10]