二叉树实现机制

二叉树是由 n ( n ≥0 ) 个结点组成的有限集 合，该集合或者为空，或者是由一个根结点加 上两棵分别称为左子树和右子树的、互不相交 的二叉树组成。

Btreee.h

#ifndef __BTREE_H__ #define __BTREE_H__ #define TRUE 1 #define FALSE 0 #define BLEFT 0 #define BRIGHT 1 typedef char BTreeData; typedef struct _btreenode { BTreeData data; struct _btreenode * lchild; struct _btreenode * rchild; }BTreeNode; typedef struct _btree { struct _BTreeNode * root; int count; }BTree; //创建二叉树 BTree * Create_BTree(); //插入二叉树 int Insert_BTree(BTree * btree, BTreeData data, int pos, int count, int flag); //打印二叉树 void Display(BTree * btree); //删除二叉树结点 int Delete(BTree * btree, int pos, int count); #endif

btree.c

#include "Btree.h" #include <stdio.h> #include <stdlib.h> //创建二叉树 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 Insert_BTree(BTree * btree, BTreeData data, int pos, int count, int flag) { if (btree == 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 = btree->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 { btree->root = node; } btree->count++; return TRUE; } //打印二叉树 void r_Display(BTreeNode * node, int gap) { if (node == NULL) return; printf ("%c\n",node->data); if (node->lchild != NULL || node->rchild != NULL) { r_Display(node->lchild,gap+4); r_Display(node->lchild,gap+4); } } void Display(BTree * btree) { if (btree == NULL) { return; } void r_Display (btree->root,0) } //删除二叉树结点 int r_Delete(BTree * btree,BTreeNode * node) { if (node == NULL || btree == NULL) { r_Delete(btree,node->lchild); r_Delete(btree,node->lchild); free(node); btree->count--; } } int Delete(BTree * btree, int pos, int count) { if (btree == NULL) { return FALSE; } BTreeNode * parent = NULL; BTreeNode * current = btree->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 { btree->root = NULL; } r_Delete(btree, current); return TRUE; }

main.c

#include "Btree.h" #include <stdio.h> int main () { BTree * btree = Create_BTree(); if (btree == NULL) { printf ("创建失败\n"); } else { printf ("创建成功\n"); } Insert_ETree(btree,'A',0,0,0); Insert_ETree(btree,'B',0,1,0); Insert_ETree(btree,'C',1,1,0); Insert_ETree(btree,'D',0,2,0); Insert_ETree(btree,'E',2,2,0); Insert_ETree(btree,'F',0,3,0); Insert_ETree(btree,'G',4,3,0); return 0; }