C语言非递归（堆栈）实现链式二叉树
并没有使用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;typedef BiTree SElemType;typedef struct{SElemType* base;//用来构造和销毁栈SElemType* top;int stacksize;}SqStack;typedef BiTree QElemType;typedef struct{QElemType* elem;//存储空间基址int queuesize;int front;int rear;}SqQueue;void visit(TElemType e){printf("%c", e);}#endif Sequential_Stack.h
/*-----------------------------------------------------------------------------Copyright (c) 2010-2011 Zidane LiUsage of this program is free for non-commercial use.-----------------------------------------------------------------------------*/#ifndef SEQUENTIAL_STACK_H#define SEQUENTIAL_STACK_H#include <stdlib.h>#include "ADT_Linked_BinaryTree.h"#define STACK_INIT_SIZE 100#define STACKINCREMENT 10#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0;#define INFEASIBLE -1#define OVERFLOW -2typedef int Status;Status InitStack_Sq(SqStack& S){S.base = (SElemType*)malloc(STACK_INIT_SIZE * sizeof(SElemType));if (!S.base){exit(OVERFLOW);}S.top = S.base;S.stacksize = STACK_INIT_SIZE;return OK;}Status DestroyStack_Sq(SqStack& S){free(S.base);return OK;}Status ClearStack_Sq(SqStack& S){S.base = NULL;S.top = S.base;S.stacksize = STACK_INIT_SIZE;return OK;}Status StackEmpty_Sq(SqStack S){return S.base == S.top;}int StackLength_Sq(SqStack S){return S.top - S.base;}SElemType GetTop_Sq(SqStack S){if (StackEmpty_Sq(S)){return ERROR;}return *(S.top - 1);}Status Push_Sq(SqStack& S, SElemType e){if (S.top - S.base >= S.stacksize){S.base = (SElemType*)realloc(S.base, (S.stacksize + STACKINCREMENT) * sizeof(SElemType));if (!S.base){exit(OVERFLOW);}S.top = S.base + S.stacksize;S.stacksize += STACKINCREMENT;}*S.top++ = e;return OK;}Status Pop_Sq(SqStack& S, SElemType& e){if (S.top == S.base){return ERROR;}e = * --S.top;return OK;}Status StackTraverse(SqStack S){//p为指向指针的指针for (SElemType* p = S.base; p != S.top; p++){visit((*p)->data);}return OK;}#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"#include "Sequential_Stack.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){SqStack S;BiTree p = T;InitStack_Sq(S);Push_Sq(S, p);while(!StackEmpty_Sq(S)){Pop_Sq(S, p);visit(p->data);if(p->rchild)Push_Sq(S, p->rchild);if(p->lchild)Push_Sq(S, p->lchild);}DestroyStack_Sq(S);return OK;}//当p所指的结点不为空时，则将该结点所在链结点的地址进栈，然后再将p指向该结点的左孩子结点；当p所指//的结点为空时，则从堆栈中退出栈顶元素，并访问该结点，然后再将p指向该结点的有孩子结点。Status InOrderTraverse(BiTree T){SqStack S;InitStack_Sq(S);Push_Sq(S, T);while (!StackEmpty_Sq(S)){SElemType p;//遍历左子树，一直遍历到左子树为空的结点while (GetTop_Sq(S)){p = GetTop_Sq(S);Push_Sq(S, p->lchild);}//删除栈顶的空结点Pop_Sq(S, p);if (!StackEmpty_Sq(S)){Pop_Sq(S, p);visit(p->data);Push_Sq(S, p->rchild);}}DestroyStack_Sq(S);return OK;}//当指针p指向某一个结点时，不能马上对它进行访问，而要先遍历它的左子树，因而要将此结点的地址进栈，//当其左子树遍历完毕后，再次搜索到该结点时，还不能对它进行访问，还需要遍历它的右子树。Status PostOrderTraverse(BiTree T){BiTree p = T, stack;//p表示当前结点，栈stack[]用来存储结点 int tag;int top = -1;do{while(p != NULL)//先处理结点的左孩子结点，把所有左孩子依次入栈 {stack[++top] = p;tag = 0;p = p->lchild;} if(top >= 0) //所有左孩子处理完毕后 {if(!tag) //如果当前结点的右孩子还没被访问 {p = stack;//输出栈顶结点 ，但不退栈 ，因为要先输出其孩子结点 p = p->rchild; //处理其右孩子结点 tag = 1; //表示栈中top位置存储的结点的右孩子被访问过了，下次轮到它退栈时可直接输出 }else //如果该结点的左右孩子都被访问过了 { visit(stack->data); //栈顶元素出栈，输出该结点，此时结点p指向NULL}}} while((p != NULL)||(top >= 0));return OK;}Status LevelOrderTraverse(BiTree T){BiTree queue, p = T;int front, rear;if (T != NULL){queue = T;front = -1;rear = 0;while (front < rear){p = queue[++front];visit(p->data);if (p->lchild != NULL)queue[++rear] = p->lchild;if (p->rchild != NULL)queue[++rear] = p->rchild;}}return OK;}#endif
页:
[1]