首页 > 代码库 > 二叉树的实现与操作(C语言实现)
二叉树的实现与操作(C语言实现)
二叉树的定义：
上一篇的树的通用表示法太过于复杂，由此这里采用了孩子兄弟表示法来构建二叉树。
孩子兄弟表示法:
每个结点包含一个数据指针和两个结点指针
--->数据指针：指向保存于树中的数据
--->孩子结点指针：指向第一个孩子
--->兄弟结点指针：指向第一个右兄弟
二叉树是由 n( n>=0 ) 个结点组成的有限集合,该集合或者为空,或者是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。
特殊的二叉树：
定义1：满二叉树(Full Binary Tree)
如果二叉树中所有分支结点的度数都为2，且叶子结点都在同一层次上，则称做这类二叉树为满二叉树
定义2：完全二叉树
如果一颗具有N个结点的高度为K的二叉树，它的每一个结点都与高度为K的满二叉树中的编号为1---N的结点一一对应，则称这课二叉树为完全二叉树（从上到下从左到右编号）。
注：完全二叉树的叶结点仅仅出现在最下面二层，
最下面的叶结点一定出现在左边；
倒数第二层的叶结点一定出现在右边
完全二叉树中度为1的结点只有左孩子
同样结点数的二叉树，完全二叉树的高度最小
二叉树的深层性质
性质1：
在二叉树的第i层最多有2i-1个结点。（i>=1）
性质2：
深度为K的二叉树最多有2k-1个结点（k>=0）
性质3：
对任何一颗二叉树，如果其叶结点有n0个，度为2的结点的非叶结点有n2个，则有n0=n2+1
性质4：
具有n个结点的完全二叉树的高度为[log2n]+1
性质5：
一颗有n个结点的二叉树（高度为[log2n]+1），按层次对结点进行编号（从上到下，从左到右），对任意结点i有：
如果i=1,则结点i是二叉树的根，
如果i>1,则其双亲结点为[i/2]
如果2i<=n,则结点i的左孩子为2i
如果2i>n,则结点i无左孩子，
如果2i+1<=n,则结点i的右孩子为2i+1,
如果2i+1>n,则结点i无右孩子
以下是代码：
头文件：
#ifndef _BTREE_H_
#define _BTREE_H_
#define BT_LEFT 0
#define BT_RIGHT 1
typedef void BTree; //树
typedef unsigned long long BTPos; //要插入结点的位置，是一个十六进制数字
typedef struct _tag_BTreeNode BTreeNode; //定义树结点
struct _tag_BTreeNode
{
BTreeNode* left;
BTreeNode* right;
};
typedef void (BTree_Printf)(BTreeNode*);
BTree* BTree_Create();
void BTree_Destroy(BTree* tree);
void BTree_Clear(BTree* tree);
int BTree_Insert(BTree* tree, BTreeNode* node, BTPos pos, int count, int flag);
BTreeNode* BTree_Delete(BTree* tree, BTPos pos, int count);
BTreeNode* BTree_Get(BTree* tree, BTPos pos, int count);
BTreeNode* BTree_Root(BTree* tree);
int BTree_Height(BTree* tree);
int BTree_Count(BTree* tree);
int BTree_Degree(BTree* tree);
void BTree_Display(BTree* tree, BTree_Printf* pFunc, int gap, char div);
#endif
源文件：
#include "stdafx.h"
#include <stdio.h>
#include <malloc.h>
#include "BTree.h"
typedef struct _tag_BTree TBTree;
struct _tag_BTree //树的头结点定义
{
int count;
BTreeNode* root;
};
//打印函数
static void recursive_display(BTreeNode* node, BTree_Printf* pFunc, int format, int gap, char div)
{
int i = 0;
if( (node != NULL) && (pFunc != NULL) )
{
//先打印格式符号
for(i=0; i<format; i++)
{
printf("%c", div);
}
//打印树中具体的数据
pFunc(node);
printf("\n");
//如果左 或者 右结点不为空才打印
if( (node->left != NULL) || (node->right != NULL) )
{
recursive_display(node->left, pFunc, format + gap, gap, div);
recursive_display(node->right, pFunc, format + gap, gap, div);
}
}
//如果结点为空 就打印 格式符号
else
{
for(i=0; i<format; i++)
{
printf("%c", div);
}
printf("\n");
}
}
//统计树中结点的数量
static int recursive_count(BTreeNode* root)
{
int ret = 0;
if( root != NULL )
{
ret = recursive_count(root->left) + 1 + recursive_count(root->right);
}
return ret;
}
//计算树的高度
static int recursive_height(BTreeNode* root)
{
int ret = 0;
if( root != NULL )
{
int lh = recursive_height(root->left);
int rh = recursive_height(root->right);
ret = ((lh > rh) ? lh : rh) + 1;
}
return ret;
}
//计算树的度
static int recursive_degree(BTreeNode* root)
{
int ret = 0;
if( root != NULL )
{
if( root->left != NULL )
{
ret++;
}
if( root->right != NULL )
{
ret++;
}
if( ret == 1 )
{
int ld = recursive_degree(root->left);
int rd = recursive_degree(root->right);
if( ret < ld )
{
ret = ld;
}
if( ret < rd )
{
ret = rd;
}
}
}
return ret;
}
BTree* BTree_Create()
{
TBTree* ret = (TBTree*)malloc(sizeof(TBTree));
if( ret != NULL )
{
ret->count = 0;
ret->root = NULL;
}
return ret;
}
void BTree_Destroy(BTree* tree)
{
free(tree);
}
void BTree_Clear(BTree* tree)
{
TBTree* btree = (TBTree*)tree;
if( btree != NULL )
{
btree->count = 0;
btree->root = NULL;
}
}
//tree 目标树 node 要插入结点 pos 要插入位置 count 移动步数 flag 插入位置是左还是右
int BTree_Insert(BTree* tree, BTreeNode* node, BTPos pos, int count, int flag)
{
TBTree* btree = (TBTree*)tree;
int ret = (btree != NULL) && (node != NULL) && ((flag == BT_LEFT) || (flag == BT_RIGHT));
int bit = 0;
if( ret )
{
BTreeNode* parent = NULL;
BTreeNode* current = btree->root;
node->left = NULL;
node->right = NULL;
while( (count > 0) && (current != NULL) )
{
//位置最低位与1进行按位与运算，得知是往左走还是往右走
bit = pos & 1;
//表示位置的十六进制向右移动一位
pos = pos >> 1;
//parent用来挂要插入的结点
parent = current;
if( bit == BT_LEFT )
{
current = current->left;
}
else if( bit == BT_RIGHT )
{
current = current->right;
}
count--;
}
//插入的结点挂上中间被砍断的剩下的结点
if( flag == BT_LEFT )
{
node->left = current;
}
else if( flag == BT_RIGHT )
{
node->right = current;
}
//将要插入的结点挂上
if( parent != NULL )
{
if( bit == BT_LEFT )
{
parent->left = node;
}
else if( bit == BT_RIGHT )
{
parent->right = node;
}
}
else
{
btree->root = node;
}
btree->count++;
}
return ret;
}
//删除与插入基本类似，只不过将要删除的结点的父结点的left或者right指针以及所有的子节点置为NULL而已
BTreeNode* BTree_Delete(BTree* tree, BTPos pos, int count)
{
TBTree* btree = (TBTree*)tree;
BTreeNode* ret = NULL;
int bit = 0;
if( btree != NULL )
{
BTreeNode* parent = NULL;
BTreeNode* current = btree->root;
while( (count > 0) && (current != NULL) )
{
bit = pos & 1;
pos = pos >> 1;
parent = current;
if( bit == BT_LEFT )
{
current = current->left;
}
else if( bit == BT_RIGHT )
{
current = current->right;
}
count--;
}
if( parent != NULL )
{
if( bit == BT_LEFT )
{
parent->left = NULL;
}
else if( bit == BT_RIGHT )
{
parent->right = NULL;
}
}
else
{
btree->root = NULL;
}
ret = current;
btree->count = btree->count - recursive_count(ret);
}
return ret;
}
BTreeNode* BTree_Get(BTree* tree, BTPos pos, int count)
{
TBTree* btree = (TBTree*)tree;
BTreeNode* ret = NULL;
int bit = 0;
if( btree != NULL )
{
BTreeNode* current = btree->root;
while( (count > 0) && (current != NULL) )
{
bit = pos & 1;
pos = pos >> 1;
if( bit == BT_LEFT )
{
current = current->left;
}
else if( bit == BT_RIGHT )
{
current = current->right;
}
count--;
}
ret = current;
}
return ret;
}
BTreeNode* BTree_Root(BTree* tree)
{
TBTree* btree = (TBTree*)tree;
BTreeNode* ret = NULL;
if( btree != NULL )
{
ret = btree->root;
}
return ret;
}
int BTree_Height(BTree* tree)
{
TBTree* btree = (TBTree*)tree;
int ret = 0;
if( btree != NULL )
{
ret = recursive_height(btree->root);
}
return ret;
}
int BTree_Count(BTree* tree)
{
TBTree* btree = (TBTree*)tree;
int ret = 0;
if( btree != NULL )
{
ret = btree->count;
}
return ret;
}
int BTree_Degree(BTree* tree)
{
TBTree* btree = (TBTree*)tree;
int ret = 0;
if( btree != NULL )
{
ret = recursive_degree(btree->root);
}
return ret;
}
void BTree_Display(BTree* tree, BTree_Printf* pFunc, int gap, char div)
{
TBTree* btree = (TBTree*)tree;
if( btree != NULL )
{
recursive_display(btree->root, pFunc, 0, gap, div);
}
}
主函数：
// 二叉树.cpp : 定义控制台应用程序的入口点。
//
#include "stdafx.h"
#include "BTree.h"
#include <iostream>
struct Node //数据结点
{
BTreeNode header;
char v;
};
void printf_data(BTreeNode* node) //打印树
{
if( node != NULL )
{
printf("%c", ((struct Node*)node)->v);
}
}
int _tmain(int argc, _TCHAR* argv[])
{
BTree* tree = BTree_Create();
struct Node n1 = {{NULL, NULL}, 'A'};
struct Node n2 = {{NULL, NULL}, 'B'};
struct Node n3 = {{NULL, NULL}, 'C'};
struct Node n4 = {{NULL, NULL}, 'D'};
struct Node n5 = {{NULL, NULL}, 'E'};
struct Node n6 = {{NULL, NULL}, 'F'};
BTree_Insert(tree, (BTreeNode*)&n1, 0, 0, 0);
BTree_Insert(tree, (BTreeNode*)&n2, 0x00, 1, 0);
BTree_Insert(tree, (BTreeNode*)&n3, 0x01, 1, 0);
BTree_Insert(tree, (BTreeNode*)&n4, 0x00, 2, 0);
BTree_Insert(tree, (BTreeNode*)&n5, 0x02, 2, 0);
BTree_Insert(tree, (BTreeNode*)&n6, 0x02, 3, 0);
printf("Height: %d\n", BTree_Height(tree));
printf("Degree: %d\n", BTree_Degree(tree));
printf("Count: %d\n", BTree_Count(tree));
printf("Position At (0x02, 2): %c\n", ((struct Node*)BTree_Get(tree, 0x02, 2))->v);
printf("Full Tree: \n");
BTree_Display(tree, printf_data, 4, '-');
//以下是删除结点位置在0x00的结点后，树的整体状态
BTree_Delete(tree, 0x00, 1);
printf("After Delete B: \n");
printf("Height: %d\n", BTree_Height(tree));
printf("Degree: %d\n", BTree_Degree(tree));
printf("Count: %d\n", BTree_Count(tree));
printf("Full Tree: \n");
BTree_Display(tree, printf_data, 4, '-');
//以下是清空树后，树的整体状态
BTree_Clear(tree);
printf("After Clear: \n");
printf("Height: %d\n", BTree_Height(tree));
printf("Degree: %d\n", BTree_Degree(tree));
printf("Count: %d\n", BTree_Count(tree));
BTree_Display(tree, printf_data, 4, '-');
BTree_Destroy(tree);
system("pause");
return 0;
}
运行结构：
Height: 4 Degree: 2 Count: 6 Position At (0x02, 2): E Full Tree: A ----B --------D --------E ------------F ------------ ----C After Delete B: Height: 2 Degree: 1 Count: 2 Full Tree: A ---- ----C After Clear: Height: 0 Degree: 0 Count: 0 请按任意键继续. . .
如有错误，望不吝指出呀。
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。