ks17:algorithm apple$ cat btree_test.c
///***************************************************************
/// @Filename: btree_test.c
/// @Brief: 尝试构建b树，并使用三种遍历算法对树进行遍历
///
///
/// @notice: 在函数里面申请空间给指针，是不能返回的，必须包装一层，赋值给指针的指针方式，否则函数返回后赋值结果是NULL
/// @Author: kuang17
/// @Last modified: 2019-06-17 18:51
///*************************************************************** #include "stdio.h"
#include "stdlib.h"
#include "string.h" ///定义结构
typedef struct treeNode
{
int data;
struct treeNode* parent;
struct treeNode* lch;
struct treeNode* rch;
}TreeNode; typedef struct BtreeData
{
TreeNode* rootNode;
}Btree; ///定义参数
struct BtreeData* m_btree; ///定义函数
TreeNode* mallocNode();
int initTree(Btree* btree, int rootData);
int perorderTraversalTree(TreeNode* pnode);
int inorderTraversalTree(TreeNode* pnode);
int postorderTraversalTree(TreeNode* pnode);
int addNode(TreeNode* parentNode, int newData); ///主函数
int main(int argc, char** argv)
{
int originData[100] = {0, 0, 0};
int count = 0; //init tree
m_btree = (struct BtreeData*)malloc(sizeof(struct BtreeData));
initTree(m_btree, atoi(argv[1]));
if(m_btree->rootNode != NULL)
printf("root data is: %d\n", m_btree->rootNode->data); //create tree
char input[12] = "{\0}";
int is_end = 1;
while (is_end)
{
gets(input);
printf("input is %s\n", input);
if (strcmp(input, "end") == 0){
printf("end input.\n");
is_end = 0;
} else{
//add to tree
addNode(m_btree->rootNode, atoi(input));
originData[count++] = atoi(input);
}
}
//perorder traversal
printf("perorder traversal :\n");
perorderTraversalTree(m_btree->rootNode); //inorder traversal
printf("inorder traversal :\n");
inorderTraversalTree(m_btree->rootNode); //postorder traversal
printf("postorder traversal: \n");
postorderTraversalTree(m_btree->rootNode); printf("\norigin is :\n");
for(int i = 0; i < count; i++)
{
printf("%d\n", originData[i]);
}
printf("end\n");
} // *********************************************************************
/// @Brief mallocNode 申请空间
///
/// @Returns
// *********************************************************************
TreeNode* mallocNode()
{
TreeNode* newNode;
newNode = (TreeNode*)malloc(sizeof(TreeNode));
newNode->data = 0;
newNode->parent = NULL;
newNode->lch = NULL;
newNode->rch = NULL;
return newNode;
} // *********************************************************************
/// @Brief initTree 初始化树
///
/// @Param btree
/// @Param rootData
///
/// @Returns
// *********************************************************************
int initTree(Btree* btree, int rootData)
{
TreeNode* rootNode;
rootNode = mallocNode();
rootNode->data = rootData;
btree->rootNode = rootNode;
return 0;
} // *********************************************************************
/// @Brief addNode 添加节点
///
/// @Param parentNode
/// @Param newData
///
/// @Returns
// *********************************************************************
int addNode(TreeNode* parentNode, int newData)
{
TreeNode* newNode;
newNode = mallocNode();
newNode->data = newData; if(newData <= parentNode->data)
{
printf("parent data is: %d, add lch\n", parentNode->data);
if(parentNode->lch == NULL)
{
//这里没法直接给parentNode赋值，只能给他的节点赋值
parentNode->lch = newNode;
}else
{
addNode(parentNode->lch, newData);
}
} if(newData > parentNode->data)
{
printf("parent data is: %d, add rch\n", parentNode->data);
if(parentNode->rch == NULL){
parentNode->rch = newNode;
} else {
addNode(parentNode->rch, newData);
}
} return 0;
} // *********************************************************************
/// @Brief perorderTraversalTree 先序遍历
///
/// @Param pnode
///
/// @Returns
// *********************************************************************
int perorderTraversalTree(TreeNode* pnode)
{
if(pnode == NULL)
return 0; perorderTraversalTree(pnode->lch);
printf("%d\n", pnode->data);
perorderTraversalTree(pnode->rch);
return 1;
} // *********************************************************************
/// @Brief inorderTraversalTree 中序遍历
///
/// @Param pnode
///
/// @Returns
// *********************************************************************
int inorderTraversalTree(TreeNode* pnode)
{
if(pnode == NULL)
return 0; printf("%d\n", pnode->data);
inorderTraversalTree(pnode->lch);
inorderTraversalTree(pnode->rch);
return 1;
} // *********************************************************************
/// @Brief postorderTraversalTree 后序遍历
///
/// @Param pnode
///
/// @Returns
// *********************************************************************
int postorderTraversalTree(TreeNode* pnode)
{
if(pnode == NULL)
return 0; postorderTraversalTree(pnode->lch);
postorderTraversalTree(pnode->rch);
printf("%d\n", pnode->data);
return 1;
}