二叉树本身是一种递归的数据类型,二叉树的许多操作离不开递归。非递归遍历包括结点入栈,先访问右子树,再访问根节点,访问左子树,先序和后序的非递归算法有待调试。
#include<stdlib.h> #include<stdbool.h> typedef char TElemtype; typedef struct BiTNode { TElemtype Data; struct BiTNode* Lchild, * Rchild; }BiTNode; typedef BiTNode* BiTree; typedef BiTNode ElemType; typedef struct { ElemType* base; int top; int SatckSize; }Stack; typedef Stack* PStack; void PrintTree(BiTree Tree) { printf("%c", Tree->Data); } void PreOrder(BiTree Tree, void(*Visit)(BiTree)) { if (Tree) { Visit(Tree); PreOrder(Tree->Lchild, Visit); PreOrder(Tree->Rchild, Visit); } } void InOrder(BiTree Tree, void(*Visit)(BiTree)) { if (Tree) { InOrder(Tree->Lchild, Visit); Visit(Tree); InOrder(Tree->Rchild, Visit); } } void PostOrder(BiTree Tree, void (*Visit)(BiTree)) { if (Tree) { PostOrder(Tree, Visit); PostOrder(Tree, Visit); Visit(Tree); } } void Array_InOrder(BiTree Tree, void(*Visit)(BiTree)) { PStack S; InitStack(S, 100); BiTree p = Tree; while (p || !IsEmpty(S)) { if (p) { Push(S, *p); p = p->Lchild; } else { Pop(S, p); Visit(p); p->Rchild; } } } }
附上栈的一些操作
void InitStack(PStack S, int size) { if (!S) exit(1); if (size > 0) S->base = (ElemType*)malloc(sizeof(ElemType) * size); if (!S->base)exit(1); S->SatckSize = size; S->top = 0; } bool Pop(PStack S, ElemType* PopItem) { if (S->top <= 0) { printf("Stack is empty\n"); return false; } S->top--; *PopItem = *(S->base + S->top); return true; } bool Push(PStack S, ElemType PushItem) { if (S->top >= S->SatckSize) { printf("Stack is full\n"); return false; } *(S->base + S->top) = PushItem; S->top++; return true; } ElemType GetTop(PStack S, ElemType* TopItem) { if (S->top <= 0) { printf("NO Item\n"); } *TopItem = *(S->base + S->top - 1); return *TopItem; } bool IsEmpty(PStack S) { if (S->top == 0) return true; else return false; }