创建二叉树

二叉树在结构上不依赖组织链表

指路法通过根节点与目标节点的相对位置进行定位

#define BT_LEFT 0 #define BT_RIGHT 1 typedef unsigned long long BTPos;

结点指针域定义

typedef struct tag_BTressNode BTressNode; struct tag_BTressNode { BTreeNode* left; BTreeNode* right; };

头结点定义

typedef struct tag_BTree BTree; struct tag_BTree { int count; BTreeNode* root; };

数据元素定义：

struct Node { BTreeNode header; char v; }

定位：

while((count > 0)&&(current !=NULL)) { bit = pos & 1; pos = pos >> 1; count--; parent = current; if(bit == BT_LEFT) { current = current->left; } else if(bit == BT_RIGHT) { current = current->right; } }

位运算是是实现指路法的基础

#ifndef BTREE_H #define BTREE_H #define BT_LEFT 0 #define BT_RIGHT 1 typedef void BTree; typedef unsigned long long BTPos; typedef void (BTree_Printf)(BTreeNode*); typedef struct tag_BTressNode BTressNode; struct tag_BTressNode { BTreeNode* left; BTreeNode* right; }; BTree* BTree_Create(); void BTree_Destroy(BTree* tree); void BTree_Clear(BTree* tree); int BTree_Insert(BTree* tree,BTree* node,BTPos pos,int count,int flag);//pos:二进制表示方向，例如110（左右右） //flag：标示被替换的结点是插入结点的左子树还是右子树 BTreeNode* BTree_Delete(BTree* tree,BTPos pos,int count); BTreeNode* BTree_Get(BTree* tree,BTPos pos,int count);//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