数据结构---树

//定义二叉链式结构

#define QUEUE_MAXSIZE 50

typedef char DATA; typedef struct ChainTree {         DATA data;         struct ChainTree *left;         struct ChainTree *right; }ChainBinTree;

//初始化二叉树

ChainBinTree *BinTreeInit(ChainBinTree *node) {         if(node != NULL)                 return node;         else                 return NULL;

}

//添加结点到二叉树 int BinTreeAddNode(ChainBinTree *bt,ChainBinTree *node,int n) {         if(bt == NULL)         {                 printf("root is not here");                 return 0;         }         switch(n)         {                 case 1:                         if(bt->left)                         {                                 printf("left not null");                                 return 0;                         }                         else                                 bt->left = node;                                 break;                 case 2:                         if(bt->right)                         {                                 printf("right not null");                         }                         else                                 bt->right = node;                                 break;                 default:                         printf("arg is error");                         return 0;         }         return 1;

}

//获取左子树

ChainBinTree *BinTreeLeft(ChainBinTree *bt) {         if(bt)                 return bt->left;         else                 return NULL; }

//获取右子树

ChainBinTree *BinTreeRight(ChainBinTree *bt) {         if(bt)                 return bt->right;         else                 return NULL; }

//判断二叉树是否为空

int BinTreeIsEmpty(ChainBinTree *bt) {         if(bt)                 return 0;         else                 return 1;

}

//获取树的深度

int BinTreeDepth(ChainBinTree *bt) {         int dep1,dep2;         if(bt == NULL)         return 0;         else         {                 dep1 = BinTreeDepth(bt->left);                 dep2 = BinTreeDepth(bt->right);                  if(dep1 > dep2)                 return dep1+1;                 else                 return dep2 +1;         } }

//在树中查找

ChainBinTree *BinTreeFind(ChainBinTree *bt,DATA data) {         ChainBinTree *p;         if(bt == NULL)                 return NULL;         else         {                 if(bt->data == data)                     return bt;                 else                 {                         if(p = BinTreeFind(bt->left,data))                         return p;                         else if(p = BinTreeFind(bt->right,data))                         return p;                         else                                 return NULL;                 }         } }

//清空树

void BinTreeClear(ChainBinTree *bt) {         if(bt)         {                  BinTreeClear(bt->left);                 BinTreeClear(bt->right);                 free(bt);                 bt = NULL;         }         return; }

//先序遍历

void BinTree_DLR(ChainBinTree *bt,void(*oper)(ChainBinTree *p)) {         if(bt)         {                  oper(bt);                 BinTree_DLR(bt->left,oper);                 BinTree_DLR(bt->right,oper);         }         return;

}

//中序遍历

void BinTree_LDR(ChainBinTree *bt,void(*oper)(ChainBinTree *p)) {         if(bt)         {                 BinTree_LDR(bt->left,oper);                 oper(bt);                 BinTree_LDR(bt->right,oper);         }         return; }

//后序遍历

void BinTree_LRD(ChainBinTree *bt,void(*oper)(ChainBinTree *p)) {         if(bt)         {                 BinTree_LRD(bt->left,oper);                 BinTree_LRD(bt->right,oper);                 oper(bt);         }         return; }

//按层遍历

void BinTree_Level(ChainBinTree *bt,void(*oper)(ChainBinTree *p)) {         ChainBinTree *p;         ChainBinTree *q[QUEUE_MAXSIZE];         int head = 0,tail = 0;         if(bt)         {                 tail = (tail+1) % QUEUE_MAXSIZE;                 q[tail] = bt;         }          while(head != tail)         {                 head = (head +1) % QUEUE_MAXSIZE;                 p = q[head];                 oper(p);                 if(p->left != NULL)                 {                         tail = (tail+1) % QUEUE_MAXSIZE;                         q[tail] = p->left;                 }                 if(p->right != NULL)                 {                         tail = (tail+1) % QUEUE_MAXSIZE;                         q[tail] = p->right;                 }         }         return ; }