树

1：创建结点

#define MAXLEN 20 typedef char DATA; typedef struct CBT { DATA data; struct CBT *left; struct CBT *right; }CBTType;

2：初始化树的根

CBTType *InitTree()//初始化树的根 { CBTType *node; if(node=(CBTType*)malloc(sizeof(CBTType))) //申请内存 { printf("请先输入一个根节点数据：\n"); scanf("%s",&node->data); node->left = NULL; node->right = NULL; if (node!=NULL)//二叉树根节点不为空 {return node;} else {return NULL;} } }

3：显示节点数据

void TreeNodeData(CBTType *p) { printf("%c",p->data); }

4：获取左子树

CBTType*TreeLeftNode(CBTType*treeNode) { if (treeNode) {return treeNode->left;} else {return NULL;} }

5：获取右子树

CBTType *TreeRightNode(CBTType *treeNode) { if (treeNode) {return treeNode->right;} else {return NULL;} }

6：判断是否为空树

int TreeIsEmpty(CBTType *treeNode) { if (treeNode) { return 0; } else { return 1; } }

7：清空树

void ClearTree(CBTType *treeNode) { if (treeNode) { ClearTree(treeNode->left); ClearTree(treeNode->right); free(treeNode); treeNode = NULL; } }

8：先序遍历

void DLR(CBTType *treeNode, void(*TreeNodeData)(CBTType *p)) { if (treeNode) { TreeNodeData(treeNode); DLR(treeNode->left, TreeNodeData); DLR(treeNode->right, TreeNodeData); } }

9：中序遍历

void LDR(CBTType *treeNode, void(*TreeNodeData)(CBTType *p)) { if (treeNode) { LDR(treeNode->left, TreeNodeData); TreeNodeData(treeNode); LDR(treeNode->right, TreeNodeData); } }

10：查找节点

CBTType *TreeFindNode(CBTType *treeNode, DATA data)//查找节点 { CBTType *ptr; if (treeNode==NULL) {return NULL;} else { if (treeNode->data==data) {return treeNode;} else { if(ptr== TreeFindNode(treeNode->left,data))//分别向左右子树递归查找 {return ptr;} else if (ptr == TreeFindNode(treeNode->right, data)) {return ptr;} else {return NULL;} } } }

11：计算二叉树深度

int TreeDepth(CBTType *treeNode) { int depleft, depright; if (treeNode == NULL) { return 0; } else { depleft = TreeDepth(treeNode->left); depright = TreeDepth(treeNode->right); if (depleft>depright) { return depleft + 1; } else { return depright + 1; } } }

12：按层遍历

void LevelTree(CBTType *treeNode,void(*TreeNodeData)(CBTType *p)) { CBTType *p; CBTType *q[MAXLEN]; //定义一个顺序栈 int head = 0, tail = 0; if (treeNode)//如果队首指针不为空 { tail = (tail+1) % MAXLEN; //计算循环队列的队尾 q[tail]= treeNode; } while (head!= tail) { head = (head + 1) % MAXLEN; p = q[head]; TreeNodeData(p); if (p->left!=NULL) { tail = (tail + 1) % MAXLEN; q[tail] = p->left; } if (p->right != NULL)/ /如果存在右子树 { tail = (tail + 1) % MAXLEN; q[tail] = p->right; } } }