二叉樹是樹的特殊一種，具有如下特點：1、每個結點最多有兩顆子樹，結點的度最大為2。2、左子樹和右子樹是有順序的，次序不能顛倒。3、即使某結點只有一個子樹，也要區分左右子樹。
頭文件 BTree.h

#ifndef __BTREE_H__
#define __BTREE_H__#define BLEFT  0                 // 表示插入二叉樹的左邊
#define BRIGHT 1                 // 表示插入二叉樹的右邊#define TRUE   1
#define FALSE  0typedef char BTreeData;
// 二叉樹的結點
typedef struct _btreeNode
{BTreeData data;struct _btreeNode* lchild;   // 指向左孩子結點的指針struct _btreeNode* rchild;   // 指向右孩子結點的指針
}BTreeNode;
// 二叉樹
typedef struct _btree
{BTreeNode *root;             // 指向二叉樹的根節點int  count;                  // 記錄二叉樹結點的個數
}BTree;
typedef void(*Print_BTree)(BTreeNode*);// 創建一棵二叉樹
BTree* Create_BTree();// pos 走的路徑 值類似 110（左右右）  011 （右右左）
// count 代表走的步數
// flag  代表被替換的結點應該插入在新節點的位置，如果是BLEFT 表示插在左邊，BRIGHT表示插在右邊
int Btree_Insert (BTree* tree, BTreeData data, int pos, int count, int flag);// 打印二叉樹
void Display (BTree* tree, Print_BTree pfunc);// 刪除pos處的結點
int Delete   (BTree* tree, int pos, int count);// 求樹的高度
int BTree_Height  (BTree* tree);// 求樹的度
int BTree_Degree  (BTree* tree);// 清除樹
int BTree_Clear   (BTree* tree);// 銷毀樹
int BTree_Destroy (BTree** tree);// 打印
void printA (BTreeNode* node);// 前序遍歷
void pre_order  (BTreeNode* node);// 中序遍歷
void mid_order  (BTreeNode* node);// 后序遍歷
void last_order (BTreeNode* node);#endif // __BTREE_H__

源文件 BTree.c

#include "BTree.h"
#include <stdlib.h>
#include <stdio.h>BTree *Create_BTree()
{BTree* btree = (BTree*) malloc(sizeof(BTree)/sizeof(char));if (NULL == btree){return NULL;}btree->count = 0;btree->root  = NULL;return btree;
}int Btree_Insert (BTree* tree, BTreeData data, int pos, int count, int flag)
{if (NULL == tree || (flag != BLEFT && flag != BRIGHT)){return FALSE;}BTreeNode* node = (BTreeNode*) malloc(sizeof(BTreeNode)/sizeof(char));if (NULL == node){return FALSE;}node->data   = data;node->lchild = NULL;node->rchild = NULL;// 找插入的位置BTreeNode *parent  = NULL;BTreeNode *current = tree->root;     // current 一開始指向根節點，根節點的父節點是空int way;                             // 保存當前走的位置while (count > 0 && current != NULL){way = pos &  1;                  // 取出當前走的方向pos = pos >> 1;                  // 移去走過的路線// 因為當前位置就是走完以后的位置的父節點parent = current;if (way == BLEFT)   // 往左走{current = current->lchild;}else{current = current->rchild;}count --;}// 把被替換掉的結點插入到新節點下面if (flag == BLEFT){node->lchild = current;}else{node->rchild = current;}// 把新節點插入到二叉樹中,way保存了應該插入在父節點的左邊還是右邊if (NULL != parent){if (way == BLEFT){parent->lchild = node;}else{parent->rchild = node;}}else{tree->root = node;  // 替換根節點}tree->count++;return TRUE;
}void r_display (BTreeNode* node, Print_BTree pfunc, int gap)
{int i;if (node == NULL){for (i = 0; i < gap; i++){printf ("-");}printf ("\n");return;}for (i = 0; i < gap; i++){printf ("-");}// 打印結點// printf ("%c\n", node->data);pfunc (node);if (NULL != node->lchild || NULL != node->rchild){// 打印左孩子r_display (node->lchild, pfunc, gap+4);// 打印右孩子r_display (node->rchild, pfunc, gap+4);}
}void Display (BTree* tree, Print_BTree pfunc)
{if (tree == NULL){return;}r_display (tree->root, pfunc, 0);
}void r_delete (BTree* tree, BTreeNode* node)
{if (NULL == node || NULL == tree){return;}// 先刪除左孩子r_delete (tree, node->lchild);// 刪除右孩子r_delete (tree, node->rchild);free (node);tree->count--;
}int Delete (BTree* tree, int pos, int count)
{if (NULL == tree)return FALSE;// 找結點BTreeNode* parent  = NULL;BTreeNode* current = tree->root;int way;while (count > 0 && NULL != current){way = pos &  1;pos = pos >> 1;parent = current;if (way == BLEFT){current = current->lchild;}else{current = current->rchild;}       count--;}if (NULL != parent){if (way == BLEFT){parent->lchild = NULL;}else{parent->rchild = NULL;}}else{tree->root = NULL;}// 釋放結點r_delete (tree, current);return TRUE;
}int r_height (BTreeNode* node)
{if (NULL == node){return 0;}int lh = r_height (node->lchild);int rh = r_height (node->rchild);return (lh > rh ? lh+1 : rh+1);
}int BTree_Height (BTree* tree)
{if (NULL == tree){return FALSE;}int ret = r_height (tree->root);return ret;
}int r_degree (BTreeNode* node)
{if (NULL == node){return 0;}int degree = 0;if (NULL != node->lchild){degree++;}if (NULL != node->rchild){degree++;}if (1 == degree){int ld = r_degree (node->lchild);if (2 == ld){return 2;}int rd = r_degree (node->rchild);if (2 == rd){return 2;}}return degree;
}int BTree_Degree (BTree* tree)
{if (NULL == tree){return FALSE;}int ret = r_degree (tree->root);return ret;
}int BTree_Clear (BTree* tree)
{if (NULL == tree){return FALSE;}Delete (tree, 0, 0);  // 刪除根節點tree->root = NULL;return TRUE;
}int BTree_Destroy (BTree** tree)
{if (NULL == tree){return FALSE;}BTree_Clear (*tree);free (*tree);*tree = NULL;return TRUE;
}void pre_order  (BTreeNode* node)
{if (NULL == node){return;}printf    ("%4c", node->data);pre_order (node->lchild);pre_order (node->rchild);
}void mid_order  (BTreeNode* node)
{if (NULL == node){return;}mid_order (node->lchild);printf    ("%4c", node->data);mid_order (node->rchild);
}void last_order (BTreeNode* node)
{if (NULL == node){return;}last_order (node->lchild);  last_order (node->rchild);printf     ("%4c", node->data);
}void printA (BTreeNode* node)
{printf ("%c\n", node->data);
}

主函數 main.c

#include "BTree.h"
#include <stdio.h>int main()
{BTree* btree = Create_BTree();if (NULL == btree){printf ("創建失敗\n");}else{printf ("創建成功\n");}Btree_Insert (btree, 'A', 0, 0, 0);Btree_Insert (btree, 'B', 0, 1, 0);Btree_Insert (btree, 'C', 1, 1, 0);Btree_Insert (btree, 'D', 0, 2, 0);Btree_Insert (btree, 'E', 2, 2, 0);Btree_Insert (btree, 'F', 0, 3, 0);Btree_Insert (btree, 'G', 4, 3, 0);Btree_Insert (btree, 'H', 3, 2, 0);Display (btree, printA);printf ("前序遍歷：\n");pre_order (btree->root);printf ("\n");printf ("中序遍歷：\n");mid_order (btree->root);printf ("\n");printf ("后序遍歷：\n");last_order (btree->root);printf ("\n");#if 0Delete (btree, 0, 1);printf ("刪除后--------------\n");Display (btree, printA);printf ("高度： %d\n", BTree_Height (btree));printf ("度 ：  %d\n", BTree_Degree (btree));printf ("清空后--------------\n");BTree_Clear (btree);Display (btree, printA);BTree_Destroy (&btree);//btree = NULL;
#endif  return 0;
}