C语言递归实现链式二叉树
ADT_Linked_BinaryTree.h
/*-----------------------------------------Copyright (c) 2010-2011 Zidane LiUsage of this program is free for non-commercial use.-----------------------------------------*/#ifndef ADT_LINKED_BINARY_TREE_H#define ADT_LINKED_BINARY_TREE_H#define LEFT 0#define RIGHT 1#define SPACE 32typedef char TElemType;typedef struct BiTNode{TElemType data;struct BiTNode *lchild, *rchild;}*BiTree;void visit(TElemType e){printf("%c", e);}#endif??
Linked_BinaryTree.h
/*-----------------------------------------Copyright (c) 2010-2011 Zidane LiUsage of this program is free for non-commercial use.-----------------------------------------*//*二叉链表的实现*/#ifndef LINKED_BINARYTREE_H#define LINKED_BINARYTREE_H#include <stdlib.h>#include <string.h>#include "ADT_Linked_BinaryTree.h"#define TRUE 1#define FALSE 0#define OK 1 #define ERROR 0;#define INFEASIBLE -1#define OVERFLOW -2typedef int Status;Status InitBiTree_Sq(BiTree& T){T = NULL;return OK;}BiTNode* LocateElemType(BiTree T, TElemType e){BiTree temp = T;if (T->data == e){return T;}if (T->lchild != NULL){temp = LocateElemType(T->lchild, e);if (temp->data == e){return temp;}}if (T->rchild != NULL){temp = LocateElemType(T->rchild, e);if (temp->data == e){return temp;}}return temp;}//初始条件：二叉树T存在，p指向T中某个结点，LR为0或1，非空二叉树c与T不相交且右子树为空。//操作结果：根据LR为0或1，插入c为T中p所指结点的左或右子树。p所指结点的原有左子树或右子树则成c的右子树。Status InsertChild(BiTree& T, BiTNode* p, int LR, BiTree C){if (C->rchild){return ERROR;}BiTree temp = (!LR) ? p->lchild : p->rchild;//需要考虑操作符优先级((!LR) ? p->lchild : p->rchild) = C;C->rchild = temp;return OK;}//初始条件：二叉树T存在，p指向T中某个结点，LR为0或1。//操作结果：根据LR为0或1，删除T中p所指结点的左或右子树。Status DeleteChild(BiTree T, BiTNode* p, int LR){//子树需要删除并且存在if (!LR && p->lchild){DeleteChild(T, p->lchild, LEFT);DeleteChild(T, p->lchild, RIGHT);}else if(LR && p->rchild){DeleteChild(T, p->rchild, LEFT);DeleteChild(T, p->rchild, RIGHT);}free((!LR) ? p->lchild : p->rchild);//指针free后的是野指针，值是不确定的，所以应该重新赋为NULL。((!LR) ? p->lchild : p->rchild) = NULL;return OK;}Status DestoryBiTree_Sq(BiTree& T){if (T->lchild != NULL){DestoryBiTree_Sq(T->lchild);}if (T->rchild != NULL){DestoryBiTree_Sq(T->rchild);}free(T);return OK;}Status ClearBiTree(BiTree& T){DestoryBiTree_Sq(T);T = NULL;return OK;}//根据读入的字符串创建二叉树Status CreateBiTree(BiTree& T){char ch;scanf("%c", &ch);//空格代表空结点if (ch==' '){T = NULL;}else {if (!(T = (BiTNode *)malloc(sizeof(BiTNode)))) return ERROR;T->data = ch; // 生成根结点CreateBiTree(T->lchild); // 构造左子树CreateBiTree(T->rchild); // 构造右子树}return OK;}Status BiTreeEmpty(BiTree T){return T == NULL;}//通过求每个叶子结点的深度，求出其中最大值，即为树的深度int BiTreeDepth(BiTree T){int lchildh, rchildh;//遍历到最深的叶子结点并返回0if(T == NULL)return 0;else{lchildh = BiTreeDepth(T->lchild );rchildh = BiTreeDepth(T->rchild );return (lchildh > rchildh) ? (lchildh + 1) : (rchildh + 1);}}BiTree Root(BiTree T){return T;}Status Assign(BiTree T, TElemType e, TElemType value){LocateElemType(T, e)->data = value;return OK;}BiTree Parent(BiTree T, TElemType e){BiTree temp = T;if (T->lchild){if (T->lchild->data == e){return T;}}if (T->rchild){if (T->rchild->data == e){return T;}}if (T->lchild != NULL){temp = Parent(T->lchild, e);}if (T->rchild != NULL){temp = Parent(T->rchild, e);}return temp;}BiTree LeftChild(BiTree T, TElemType e){return LocateElemType(T, e)->lchild;}BiTree RightChild(BiTree T, TElemType e){return LocateElemType(T, e)->rchild;}BiTree LeftSibling(BiTree T, TElemType e){return Parent(T, e)->lchild;}BiTree RightSibling(BiTree T, TElemType e){return Parent(T, e)->rchild;}Status PreOrderTraverse(BiTree T){visit(T->data);if (T->lchild){PreOrderTraverse(T->lchild);}if (T->rchild){PreOrderTraverse(T->rchild);}return OK;}Status InOrderTraverse(BiTree T){if (T->lchild){InOrderTraverse(T->lchild);}visit(T->data);if (T->rchild){InOrderTraverse(T->rchild);}return OK;}Status PostOrderTraverse(BiTree T){if (T->lchild){PostOrderTraverse(T->lchild);}if (T->rchild){PostOrderTraverse(T->rchild);}visit(T->data);return OK;}#endif??