BTree *Create_BTree()//创建一个二叉树
{
BTree *btree = (BTree*)malloc(sizeof(BTree)/sizeof(char));
if (btree == NULL)
return NULL;
btree->count = 0;
btree->root = NULL;
return btree;
}
int Btree_Insert(BTree *tree, BTreeData data, int pos, int count, int flag)//增加孩子
{
if (tree == NULL || (flag != BLEFT && flag != BRIGHT))
return FALSE;
BTreeNode *node = (BTreeNode*)malloc(sizeof(BTreeNode)/sizeof(char));//创建一个节点
if (node == NULL)
return FALSE;
node->data = data;
node->lchild = NULL;
node->rchild = NULL;
BTreeNode *parent = NULL;
BTreeNode *current = tree->root;
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;
if (parent != NULL)
{
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);
if (node->lchild != NULL || node->rchild != NULL)
{
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 (node == NULL || tree == NULL)
return ;
r_delete (tree, node->lchild);
// 先删除左孩子
r_delete (tree, node->rchild);
// 删除右孩子
free (node);
tree->count --;
}
int Delete (BTree *tree, int pos, int count)//删除
{
if (tree == NULL)
return FALSE;
BTreeNode* parent = NULL;
BTreeNode* current = tree->root;
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 (parent != NULL)
{
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 (node == NULL)
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 (tree == NULL)
return FALSE;
int ret = r_height(tree->root);
return ret;
}
int r_degree (BTreeNode * node)//得到度
{
if (node == NULL)
return 0;
int degree = 0;
if (node->lchild != NULL)
degree++;
if (node->rchild != NULL)
degree++;
if (degree == 1)
{
int ld = r_degree (node->lchild);
if (ld == 2)
return 2;
int rd = r_degree (node->rchild);
if (rd == 2)
return 2;
}
return degree;
}
int BTree_Degree (BTree *tree)//度
{
if (tree == NULL)
return FALSE;
int ret = r_degree(tree->root);
return ret;
}
int BTree_Clear (BTree *tree)//清空树
{
if (tree == NULL)
return FALSE;
Delete (tree, 0, 0);
tree->root = NULL;
return TRUE;
}
int BTree_Destroy (BTree **tree)//销毁树
{
if (tree == NULL)
return FALSE;
BTree_Clear(*tree);
free (*tree);
*tree = NULL;
return TRUE;
}
void pre_order (BTreeNode *node)//前序遍历
{
if (node == NULL)
return;
printf ("L", node->data);
pre_order (node->lchild);
pre_order (node->rchild);
}
void mid_order (BTreeNode *node)//中序遍历
{
if (node == NULL)
return;
mid_order (node->lchild);
printf ("L", node->data);
mid_order (node->rchild);
}
void last_order (BTreeNode *node)//后序遍历
{
if (node == NULL)
return;
last_order (node->lchild);
last_order (node->rchild);
printf ("L", node->data);
}
在计算机科学中，二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用于实现二叉查找树和二叉堆。
二叉树的每个结点至多只有二棵子树(不存在度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒。二叉树的第i层至多有2^{i-1}个结点；深度为k的二叉树至多有2^k-1个结点；对任何一棵二叉树T，如果其终端结点数为n_0，度为2的结点数为n_2，则n_0=n_2+1。
一棵深度为k，且有2^k-1个节点称之为满二叉树；深度为k，有n个节点的二叉树，当且仅当其每一个节点都与深度为k的满二叉树中，序号为1至n的节点对应时，称之为完全二叉树。
1、先序遍历：先序遍历是先输出根节点，再输出左子树，最后输出右子树。先序遍历结果就是：ABCDEF
2、中序遍历：中序遍历是先输出左子树，再输出根节点，最后输出右子树。中序遍历结果就是：CBDAEF
3、后序遍历：后序遍历是先输出左子树，再输出右子树，最后输出根节点。后序遍历结果就是：CDBFEA
