二叉树中前后序层次的递归、非递归算法

#include <stdio.h> #include <stdlib.h> #include "tree.h" /*初始化*/ void Initiate(BiTreeNode **root) //初始化建立二叉树的头结点 { *root = (BiTreeNode *)malloc(sizeof(BiTreeNode)); (*root)->leftChild = NULL; (*root)->rightChild = NULL; } /*左子树插入结点*/ BiTreeNode *InsertLeftNode(BiTreeNode *curr, DataType x) { BiTreeNode *s, *t; if(curr == NULL) return NULL; t = curr->leftChild; //保存原curr所指结点的左子树指针 s = (BiTreeNode *)malloc(sizeof(BiTreeNode)); s->data = x; s->leftChild = t; //新插入结点的左子树为原curr的左子树 s->rightChild = NULL; curr->leftChild = s; //新结点为curr的左子树 return curr->leftChild; } /*右子树插入结点*/ BiTreeNode *InsertRightNode(BiTreeNode *curr, DataType x) { BiTreeNode *s, *t; if(curr == NULL) return NULL; t = curr->rightChild; //保存原curr所指结点的右子树指针 s = (BiTreeNode *)malloc(sizeof(BiTreeNode)); s->data = x; s->rightChild = t; //新插入结点的右子树为原curr的右子树 s->leftChild = NULL; curr->rightChild = s; //新结点为curr的右子树 return curr->rightChild; } //删除左子树 BiTreeNode *DeleteLeftTree(BiTreeNode *curr) { if(curr == NULL || curr->leftChild == NULL) return NULL; Destroy(&curr->leftChild); curr->leftChild = NULL; return curr; } //删除右子树 BiTreeNode *DeleteRightTree(BiTreeNode *curr) { if(curr == NULL || curr->rightChild == NULL) return NULL; Destroy(&curr->rightChild); curr->rightChild = NULL; return curr; } void PreOrder(BiTreeNode *root, void Visit(DataType item)) /*前序遍历二叉树t，访问操作为Visit()函数*/ { if(root != NULL) { Visit(root->data); PreOrder(root->leftChild, Visit); PreOrder(root->rightChild, Visit); } } void InOrder(BiTreeNode *root, void Visit(DataType item)) /*中序遍历二叉树t */ { if(root != NULL) { InOrder(root->leftChild, Visit); Visit(root->data); InOrder(root->rightChild, Visit); } } void PostOrder(BiTreeNode *root, void Visit(DataType item)) /*后序遍历二叉树t */ { if(root != NULL) { PostOrder(root->leftChild, Visit); PostOrder(root->rightChild, Visit); Visit(root->data); } } void Destroy(BiTreeNode **root) { if((*root) != NULL && (*root)->leftChild != NULL) Destroy(&(*root)->leftChild); if((*root) != NULL && (*root)->rightChild != NULL) Destroy(&(*root)->rightChild); free(*root); } void PrintBiTree(BiTreeNode *bt, int n) { int i; if(bt == NULL) return; PrintBiTree(bt->rightChild, n+1); for(i = 0; i < n-1; i++) printf(" "); if(n > 0) { printf("---"); printf("%c\n", bt->data); } PrintBiTree(bt->leftChild, n+1); } BiTreeNode *Search(BiTreeNode *root, DataType x) { BiTreeNode *find=NULL; BiTreeNode *p; /// if(root != NULL) {if(root->data == x) find=root; //递归出口 else //查询左子树 { find = Search(root->leftChild, x); p = Search(root->rightChild, x); } } return find; } /* //层序遍算法 void LevelOrder(BiTreeNode *root) { BiTreeNode s[100]; //申请一个BiNode数组 int max,i=0; s[0]= root;//数组首元赋为根结点 while(root!=NULL)//当结点不空时 { s[2*i+1] = root.leftChild;//左孩子赋给下标为2*i+1的数组员 s[2*i+2] = root.rightChild; //右孩子赋给下标为2*i+1的数组员 i++; root = s[i];//root变为当前数组元素的值 max = i; } for( i=0;i<max;i++) { if(s[i]->data=='0') ; else cout<<"["<<s[i].data<<"]";//依次输出 } } */ void StackInit(SqStack *s) { s->top = -1; } void push(SqStack *s, BiTreeNode *p) { s->Elem[++s->top] = *p; } BiTreeNode* pop(SqStack *s) { return &s->Elem[s->top--]; } int StackEmpty(SqStack* s) { if (s->top == -1) return 1; else return 0; } void Visit(DataType item) { printf("%c ", item); } // 前序 void PreOrderUnrec(BiTreeNode *t) { SqStack s; BiTreeNode *p=t; StackInit(&s); while (p!=NULL || !StackEmpty(&s)) { while (p!=NULL) //遍历左子树 { Visit(p-> data); push(&s,p); p=p->leftChild; }//endwhile if (!StackEmpty(&s)) //通过下一次循环中的内嵌while实现右子树遍历 { p=pop(&s); p=p->rightChild; }//endif }//endwhile }//PreOrderUnrec // 中序非递归 void InOrderUnrec(BiTreeNode *t) { SqStack s; BiTreeNode *p=t; StackInit(&s); while (p!=NULL || !StackEmpty(&s)) { while (p!=NULL) //遍历左子树 { push(&s,p); p=p-> leftChild; }//endwhile if (!StackEmpty(&s)) { p=pop(&s); Visit(p-> data); //访问根结点 p=p-> rightChild; //通过下一次循环实现右子树遍历 }//endif }//endwhile }//InOrderUnrec void StackInit3(SequenceStack *s) { s->top = -1; } void push3(SequenceStack *s, stacknode *p) { s->Elem[++s->top] = *p; } stacknode* pop3(SequenceStack *s) { return &s->Elem[s->top--]; } int StackEmpty3(SequenceStack* s) { if (s->top == -1) return 1; else return 0; } // 3.后序遍历非递归算法 void PostOrderUnrec(BiTreeNode *t) { SequenceStack s; stacknode x; BiTreeNode *p=t; StackInit3(&s); do { while (p!=NULL) //遍历左子树 { x.ptr = *p; x.tag = L; //标记为左子树 push3(&s, &x); p=p-> leftChild; } while (!StackEmpty3(&s) && s.Elem[s.top].tag==R) { x = *pop3(&s); p = &x.ptr; Visit(p-> data); //tag为R，表示右子树访问完毕，故访问根结点 } if (!StackEmpty3(&s)) { s.Elem[s.top].tag =R; //遍历右子树 p = s.Elem[s.top].ptr.rightChild; } }while (!StackEmpty3(&s)); }//PostOrderUnrec