由于二叉树非递归遍历实现时,需要用到栈和队列,因此,也将这部分代码这个头文件中了。
#include2 *.cpp源文件中调用#include //定义数据元素类型 typedef char ElemType; typedef struct BitNode{ ElemType data; struct BitNode* lchild;//左孩子指针 struct BitNode* rchild;//右孩子指针 }BitNode,BitTree; typedef BitNode NodeType; typedef struct TqStack{ NodeType* data;//数据域 struct TqStack* next;//指针域 }SNode,TqStack; typedef struct TNode{ NodeType* data;//数据域 struct TNode* next;//指针域 }TNode; typedef struct TqQueue{ TNode* front;//队头 TNode* rear;//队尾 }TqQueue; int InitTqStack(TqStack** S){ *S=(SNode*)malloc(sizeof(SNode)); if (*S==NULL) return 0; (*S)->data=NULL; (*S)->next=NULL; return 1; } int IsEmptyTqStack(TqStack* S){ return S->next==NULL?1:0; } NodeType* GetTopElemTqStack(TqStack* S){ return S->next!=NULL?S->next->data:NULL; } int PushTqStack(TqStack** S,NodeType* e){ SNode* p=*S;//辅助指针 SNode* node=NULL;//新结点 //查找尾结点 //while (p->next!=NULL) p=p->next; //创建新结点 node=(SNode*)malloc(sizeof(SNode)); if (node==NULL) return 0; node->data=e; node->next=NULL; //printf("%dn",node); //插入结点 node->next=p->next; p->next=node; return 1; } int PopTqStack(TqStack** S,NodeType** e){ SNode* p=*S; SNode* delNode=NULL; if (p->next==NULL) return 0; //记录被删除结点 delNode=p->next; *e=delNode->data; //删除结点 p->next=delNode->next; free(delNode); return 1; } int InitTqQueue(TqQueue* Q){ Q->front=Q->rear=(TNode*)malloc(sizeof(TNode)); Q->front->next=NULL; Q->rear->next=NULL; return 1; } int IsEmptyTqQueue(TqQueue* Q){ return Q->front==Q->rear?1:0; } int EnTqQueue(TqQueue* Q,NodeType* e){ TNode* node=NULL;//新结点 //创建新结点 node=(TNode*)malloc(sizeof(TNode)); if (node==NULL) return 0; node->data=e; node->next=NULL; //printf("%dn",node); //插入结点 Q->rear->next=node; Q->rear=node;; return 1; } int DeTqQueue(TqQueue* Q,NodeType** e){ TNode* delNode=NULL; if (IsEmptyTqQueue(Q)) return 0; delNode=Q->front->next;//记录被删除结点 *e=delNode->data; //删除结点 Q->front->next=delNode->next; if (Q->rear==delNode) Q->rear=Q->front; free(delNode); return 1; } int InitBitTree(BitTree** T,ElemType e){ *T=(BitNode*)malloc(sizeof(BitNode)); if (*T==NULL) return 0; (*T)->data=e; (*T)->lchild=NULL; (*T)->rchild=NULL; return 1; } int IsEmptyBitTree(BitTree* T){ return T==NULL?1:0; } void visitBitNode(BitNode* node){ if (node==NULL) return; printf("【 %d 】t",node->data); } void levelOrderBitTree(BitTree* T){ TqQueue Q; InitTqQueue(&Q); //根节点入队 EnTqQueue(&Q,T); while (IsEmptyTqQueue(&Q)!=1) { //队头元素出队 DeTqQueue(&Q,&T); visitBitNode(T);//按层序顺序依次访问结点 //判断左右子结点是否需要入队 if (T->lchild!=NULL) EnTqQueue(&Q,T->lchild); if (T->rchild!=NULL) EnTqQueue(&Q,T->rchild); } } void preOrderBitTree(BitTree* T){ if (T!=NULL) { preOrderBitTree(T->lchild); visitBitNode(T); preOrderBitTree(T->rchild); } } void inOrderBitTree(BitTree* T){ if (T!=NULL) { visitBitNode(T); inOrderBitTree(T->lchild); inOrderBitTree(T->rchild); } } void postOrderBitTree(BitTree* T){ if (T!=NULL) { postOrderBitTree(T->lchild); postOrderBitTree(T->rchild); visitBitNode(T); } } void preOrderBitTreeUnRecursion(BitTree* T){ TqStack* S; InitTqStack(&S); //非递归遍历 while (T!=NULL||IsEmptyTqStack(S)!=1) { if (T!=NULL) { visitBitNode(T); PushTqStack(&S,T); T=T->lchild; }else { PopTqStack(&S,&T); T=T->rchild; } } if (S!=NULL) free(S); } void inOrderBitTreeUnRecursion(BitTree* T){ TqStack* S; InitTqStack(&S); while (T!=NULL||IsEmptyTqStack(S)!=1) { if (T!=NULL) { PushTqStack(&S,T); T=T->lchild; } else { PopTqStack(&S,&T); visitBitNode(T); T=T->rchild; } } if(S!=NULL){ free(S); } } void postOrderBitTreeUnRecursion(BitTree* T){ BitNode* pre=NULL;//记录最近一次访问过的结点 TqStack *S; InitTqStack(&S); //非递归遍历 while (T!=NULL||IsEmptyTqStack(S)!=1) { if (T!=NULL) { PushTqStack(&S,T); T=T->lchild; }else { T=GetTopElemTqStack(S);//获取栈顶结点 if (T->rchild!=NULL&&T->rchild!=pre) T=T->rchild; else { PopTqStack(&S,&T); visitBitNode(T); pre=T; T=NULL; } } } //释放内存空间 if (S!=NULL) free(S); } void printBitTreeInfo(BitTree* T){ printf("Is Empty?%sn",(IsEmptyBitTree(T)?"Yes":"No")); printf("the left-son Tree is %x,the right-son Tree is %x.n",T->lchild,T->rchild); printf("preOrder sequence are as followings:n["); preOrderBitTree(T); printf("]n"); printf("inOrder sequence are as followings:n["); inOrderBitTree(T); printf("]n"); printf("postOrder sequence are as followings:n["); postOrderBitTree(T); printf("]n"); printf("preOrder sequence with no-recursion are as followings:n["); preOrderBitTreeUnRecursion(T); printf("]n"); printf("inOrder sequence with no-recursion are as followings:n["); inOrderBitTreeUnRecursion(T); printf("]n"); printf("postOrder sequence with no-recursion are as followings:n["); postOrderBitTreeUnRecursion(T); printf("]n"); printf("levelOrder sequence with no-recursion are as followings:n["); levelOrderBitTree(T); printf("]n"); }
包含了部分链式栈和链式队列的测试代码,就还是保留着吧了。另外,树的结构可以按着tree_test()中的左右子树设置顺序画一下(T为根节点),就不贴图了。
#include "BitTree.h" void tree_test(){ BitTree* T; InitBitTree(&T,1); //创建结点 BitNode* t_2=(BitNode*)malloc(sizeof(BitNode)); t_2->data=2; t_2->lchild=NULL;t_2->rchild=NULL; BitNode* t_3=(BitNode*)malloc(sizeof(BitNode)); t_3->data=3; t_3->lchild=NULL;t_3->rchild=NULL; BitNode* t_4=(BitNode*)malloc(sizeof(BitNode)); t_4->data=4; t_4->lchild=NULL;t_4->rchild=NULL; BitNode* t_5=(BitNode*)malloc(sizeof(BitNode)); t_5->data=5; t_5->lchild=NULL;t_5->rchild=NULL; BitNode* t_6=(BitNode*)malloc(sizeof(BitNode)); t_6->data=6; t_6->lchild=NULL;t_6->rchild=NULL; //set tree ndoes T->lchild=t_2; T->rchild=t_3; t_2->rchild=t_4; t_4->lchild=t_6; t_3->rchild=t_5; //前序遍历 printBitTreeInfo(T); } void stack_test(){ TqStack* S; BitNode* t=(BitNode*)malloc(sizeof(BitNode)); BitNode* t_2=(BitNode*)malloc(sizeof(BitNode)); t_2->data=2; t_2->lchild=NULL;t_2->rchild=NULL; BitNode* t_3=(BitNode*)malloc(sizeof(BitNode)); t_3->data=3; t_3->lchild=NULL;t_3->rchild=NULL; InitTqStack(&S); PushTqStack(&S,t_2); PushTqStack(&S,t_3); printf("is stack empty?%dn",IsEmptyTqStack(S)); PopTqStack(&S,&t); printf("is stack empty?%dn",IsEmptyTqStack(S)); //printf("%x,%x=%dn",S,S->next,S->next->data->data); printf("%dn",t->data); PopTqStack(&S,&t); printf("is stack empty?%dn",IsEmptyTqStack(S)); //printf("%x,%x=%dn",S,S->next,S->next->data->data); printf("%dn",t->data); } void queue_test(){ TqQueue Q; BitNode* t=(BitNode*)malloc(sizeof(BitNode)); BitNode* t_2=(BitNode*)malloc(sizeof(BitNode)); t_2->data=2; t_2->lchild=NULL;t_2->rchild=NULL; BitNode* t_3=(BitNode*)malloc(sizeof(BitNode)); t_3->data=3; t_3->lchild=NULL;t_3->rchild=NULL; InitTqQueue(&Q); EnTqQueue(&Q,t_2); EnTqQueue(&Q,t_3); printf("is Empty?%dn",IsEmptyTqQueue(&Q)); DeTqQueue(&Q,&t); printf("is Empty?%dn",IsEmptyTqQueue(&Q)); printf("%dn",t->data); DeTqQueue(&Q,&t); printf("is Empty?%dn",IsEmptyTqQueue(&Q)); printf("%dn",t->data); printf("front=%x,rear=%xn",Q.front,Q.rear); } int main(int argc,char** argv){ tree_test(); //stack_test(); //queue_test(); return 0; }
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)