算法与数据结构系列之[二叉树-中]

上篇介绍了二叉树的理论部分，这篇贴出二叉树完整的C语言代码实现。

BinaryTree.c

#include <stdio.h>
#include <stdlib.h>

typedef int TElemTpye;

typedef struct BinaryTreeNode{
   TElemTpye data;
   struct BinaryTreeNode *left,*right;
}BinaryTreeNode,*BinaryTree;

/**
* 初始化树，创建根节点
* @return
*/
BinaryTree InitBinaryTree(){
   BinaryTree root;  //根节点
   TElemTpye rootVal;
   root = (BinaryTree)malloc(sizeof(BinaryTreeNode));
   printf("请输入根节点：\n");
   scanf("%d",&rootVal);
   if(rootVal <= 0){
       printf("请输入大于0的数，否则为空树");
       exit(0);
   }
   root->data = rootVal;
   root->left = NULL;
   root->right = NULL;
   return root;

}

/**
* 创建二叉树
* @param T
*/
void CreateBinaryTree(BinaryTree *T){
   TElemTpye val;
   BinaryTree node;
   printf("请输入%d的左子节点\n",(*T)->data);
   scanf("%d",&val);
   if(val <= 0){    //val小于等于0都表示空树，这里是为了方便才这么写，其实0和负数是可以作为二叉树的节点的
       node = NULL;
       return;
   }

   if(val >0){
       node =(BinaryTree) malloc(sizeof(BinaryTreeNode));
       if(!node)
           exit(-1);
       (node)->data = val;
       node->left = NULL;
       node->right = NULL;
       (*T)->left = node;
       CreateBinaryTree(&(*T)->left);
   }

   printf("请输入%d的右子节点\n",(*T)->data);
   scanf("%d",&val);
   if(val > 0){
       node =(BinaryTree) malloc(sizeof(BinaryTreeNode));
       if(!node)
           exit(-1);
       node->data = val;
       node->left = NULL;
       node->right = NULL;
       (*T)->right = node;
       CreateBinaryTree(&(*T)->right);
   }
}

/**
* 二叉树的前序遍历
* @param binaryTree
*/
void PreOrder(BinaryTree node){
   if(node == NULL)
       return;
   printf("%d",node->data);
   PreOrder(node->left);
   PreOrder(node->right);
}

/**
* 二叉树的中序遍历
* @param binaryTree
*/
void InOrder(BinaryTree node){
   if(node == NULL)
       return;
   InOrder(node->left);
   printf("%d",node->data);
   InOrder(node->right);
}

/**
* 二叉树的后序遍历
* @param binaryTree
*/
void PostOrder(BinaryTree node){
   if(node == NULL)
       return;
   PostOrder(node->left);
   PostOrder(node->right);
   printf("%d",node->data);
}

BinaryTree.h

#ifndef TEST_BINARYTREE_H
#define TEST_BINARYTREE_H
typedef int TElemTpye;


typedef struct BinaryTreeNode{
    TElemTpye data;
    struct BinaryTreeNode *left,*right;
}BinaryTreeNode,*BinaryTree;
//初始化树，创建根节点
BinaryTree InitBinaryTree();
//创建一棵二叉树
void CreateBinaryTree(BinaryTree *T);
//二叉树的前序遍历
void PreOrder(BinaryTree binaryTree);
//二叉树的中序遍历
void InOrder(BinaryTree binaryTree);
//二叉树的后序遍历
void PostOrder(BinaryTree binaryTree);

main.c

BinaryTree root;
root = InitBinaryTree();
CreateBinaryTree(&root);
//前序遍历
PreOrder(root);
printf("\n");
//中序遍历
InOrder(root);
printf("\n");
//后序遍历
PostOrder(root);
printf("\n");

运行结果

请输入根节点：
1
请输入1的左子节点
2
请输入2的左子节点
4
请输入4的左子节点
8
请输入8的左子节点
0
请输入4的右子节点
9
请输入9的左子节点
0
请输入2的右子节点
5
请输入5的左子节点
0
请输入1的右子节点
3
请输入3的左子节点
6
请输入6的左子节点
0
请输入3的右子节点
7
请输入7的左子节点
0
124895367
849251637
894526731