二叉排序树c语言版

1、定义二叉树数据域、二叉树结点

/**
 * 二叉树节点数据
*/
typedef  struct treenodedata
{
    int sort;

    char* name;

} TreeNodeData;


/***
 * 二叉树节点定义
*/
typedef struct binarytree
{
    /**
     * 结点数据域
    */
    TreeNodeData* data;

     /**左子树*/
    struct binarytree* leftChild;

     /**左子树*/
    struct binarytree*  rightChild;

} TreeNode;

2、二叉排序树操作函数声明

/**
 * 创建二叉树
*/
TreeNode*  create_tree_node(TreeNodeData* data);

/**
 * 添加二叉排序树
*/
void  insert_tree_node(TreeNode** tree ,TreeNodeData* data);

/**
 * 前序遍历
*/
void   per_order(TreeNode** tree );


/**
 * 中序序遍历
*/
void   in_order(TreeNode** tree );



/**
 * 后序遍历
*/
void   post_order(TreeNode** tree );

/**
 * 销毁
*/
void   destroy_binary_tree(TreeNode* tree);

3、二叉排序树操作函数定义

/**
 * 创建二叉树结点
 */
TreeNode* create_tree_node(TreeNodeData *data)
{
    TreeNode* node = malloc(sizeof(TreeNode*));
    if (node == NULL)
    {
        perror("create_tree_node结点分配内存空间异常\n");
        return NULL;
    }
    node->data = malloc(sizeof(TreeNodeData *));
    if (node->data == NULL)
    {
        perror("节点数数据域分配内存空间失败\n");
        free(node);
        return NULL;
    }
    node->data->sort = data->sort;
    node->data->name = data->name;
    node->leftChild = NULL;
    node->rightChild = NULL;
    printf("创建二叉树成功\n");
    return node;
}

/**
 * 添加二叉排序树
 * TreeNode **tree 为了该改变函数外部指针变量的值，这里需要使用二级指针传参
 */
void insert_tree_node(TreeNode **tree, TreeNodeData *data)
{
    TreeNode* curNode = *tree;
    if (curNode == NULL)
    {
        TreeNode* node = create_tree_node(data);
        if(node==NULL)
        {
            return;
        }
        *tree = node;
        return;
    }
    /// 插入节点数据域小于父节点数据域，递归左子树
    if (curNode->data->sort > data->sort)
       insert_tree_node(&((*tree)->leftChild),data);
    else
       insert_tree_node(&((*tree)->rightChild),data);     
}

/**
 * 前序遍历
 */
void per_order(TreeNode **tree)
{
   TreeNode* curNode = *tree;
   if(curNode==NULL)
   {
     return;
   }
   printf("前序遍历sort=%d,name=%s\n",curNode->data->sort,curNode->data->name);
   per_order(&(curNode->leftChild));
   per_order(&(curNode->rightChild));
}



/**
 * 中序序遍历
*/
void   in_order(TreeNode** tree )
{
   TreeNode* curNode = *tree;
   if(curNode==NULL)
   {
     return;
   }
   in_order(&(curNode->leftChild));
   printf("中序序遍历sort=%d,name=%s\n",curNode->data->sort,curNode->data->name);
   in_order(&(curNode->rightChild));

}



/**
 * 后序遍历
*/
void   post_order(TreeNode** tree )
{
   TreeNode* curNode = *tree;
   if(curNode==NULL)
   {
     return;
   }
   post_order(&(curNode->leftChild));
   post_order(&(curNode->rightChild));
   printf("后序遍历sort=%d,name=%s\n",curNode->data->sort,curNode->data->name);
}


/**
 * 销毁
*/
void   destroy_binary_tree(TreeNode* tree)
{
   if(tree==NULL)
   {
     return;
   }
   destroy_binary_tree(tree->leftChild);
   destroy_binary_tree(tree->rightChild);
   tree = NULL;
   free(tree);    
   printf("销毁二叉树完毕\n");
}

4、测试

void  test_binary_tree()
{
  TreeNodeData st_arr[7] ={ {10,"GuanYu"},{8,"ZhangFei"},{12,"ZHaoYun"},{7,"WeiYan"}, {9,"ZheGeLiang"},{11,"MaChao"},{13,"LiuBei"}} ;
  int  i = 0;
  TreeNode* tree = NULL;
  printf("111-tree=%p\n",tree);
  for(;i<7;i++)
  {
    TreeNodeData*  data = &st_arr[i];
    insert_tree_node(&tree,data);
  }
  printf("222-tree=%p\n",tree);
  printf("前序遍历------------------------------\n");
  per_order(&tree);
  printf("中序遍历------------------------------\n");
  in_order(&tree);
  printf("后序遍历------------------------------\n");
  post_order(&tree);
    printf("销毁二叉树------------------------------\n");
  destroy_binary_tree(tree);
}