王道考研数据结构C语言实现——树前序中序后序层次遍历

王道考研数据结构C语言实现——树前序中序后序层次遍历

王道数据结构教材代码实现（C语言）——树前序中序后序层次遍历、寻找前驱结点

层次遍历使用了链式队列

#include <stdio.h>
#include <malloc.h>typedef char ElemType;
typedef struct BiTNode{//树ElemType data;struct  BiTNode *lchild, *rchild;//左右子树
}BiTNode, *BiTree;BiTNode *Node;                 //p指向目标结点
BiTNode *pre=NULL;          //指向当前访问结点的前驱
BiTNode  *final = NULL;     //用于记录最终结果void FindPreNode(BiTree T);void visit(BiTNode *T){printf("%c",T->data);
}
void PreOrder(BiTree T){//先序遍历if(T!=NULL){visit(T);PreOrder(T->lchild);PreOrder(T->rchild);}
}
void InOrder(BiTree T){//中序遍历if(T!=NULL){InOrder(T->lchild);visit(T);InOrder(T->rchild);}
}
void PostOrder(BiTree T){//后序遍历if(T!=NULL){PostOrder(T->lchild);PostOrder(T->rchild);visit(T);}
}
//为树的当前节点添加左子节
int addLeftChild(BiTNode* curNode, ElemType leftData)
{//分配新节点?BiTNode* leftNode = (BiTNode*)malloc(sizeof(BiTNode));//为新节点挂载数据leftNode->data = leftData;//新节点暂时无子节点?leftNode->lchild = NULL;leftNode->rchild = NULL;//将新节点挂到当前节点点?curNode->lchild = leftNode;return 1;
}//为树的当前节点添加右子节点?
int addRightChild(BiTNode* curNode, char rightData)
{//分配新节点?BiTNode* rightNode = (BiTNode*)malloc(sizeof(BiTNode));//为新节点挂载数据rightNode->data = rightData;//新节点暂时无子节点?rightNode->lchild = NULL;rightNode->rchild = NULL;//将新节点挂到当前节点点?curNode->rchild = rightNode;return 1;
}//####队列链表#####
typedef struct LinkNode{//队列BiTNode* data;struct LinkNode *next;
}LinkNode;
typedef struct {LinkNode *front,*rear;
}LinkQueue;
//####队列链表#####void InitQueue(LinkQueue *Q){//队列初始化Q->front=Q->rear=(LinkNode*)malloc(sizeof(LinkNode));//建立头结点Q->front->next=NULL;
}
void EnQueue(LinkQueue *Q,BiTNode *T){//进队LinkNode *s=(LinkNode*)malloc(sizeof(LinkNode));s->data=T;//data 数据存放结点地址(8字节)s->next=NULL;Q->rear->next=s;//将新节点入队Q->rear=s;// 将尾指针后移
}
void DeQueue(LinkQueue *Q,BiTNode* *T){//出队LinkNode * P;P=Q->front->next;*T=P->data;Q->front->next=P->next;if(P==Q->rear){Q->rear=Q->front;//如果是最后一个结点则将尾指针指向头指针，队列置空}free(P);
}
void LevelOrder(BiTree T){//层次遍历，从左往右,若要从右往左只需先右孩子先入队即可LinkQueue Q;InitQueue(&Q);EnQueue(&Q,T);//T :结点的地址BiTNode *p=NULL;while(Q.front!&#ar){DeQueue(&Q,&p); //p:树结点地址，&p:指针变量p的地址（地址的地址）printf("%c",p->data);if(p->lchild!=NULL){EnQueue(&Q,p->lchild);}if(p->rchild!=NULL){EnQueue(&Q,p->rchild);}}
}int main(){//设定根节点?BiTNode root;//根节点Aroot.data = 'A';addLeftChild(&root, 'B');addRightChild(&root, 'C');//为B节点增加子节点?addLeftChild(root.lchild, 'D');addRightChild(root.lchild, 'E');//为C节点增加子节点?hild, 'F');hild, 'G');printf("n前序遍历：");PreOrder(&root);printf("n中序遍历：");InOrder(&root);printf("n后序遍历：");PostOrder(&root);BiTree T= &root;printf("n层次遍历：");LevelOrder(T);Node= T->rchild;       //中序遍历序列DEBAFCG  p=CFindPreNode(Node);printf("n%c的前驱是%c",Node->data,final->data);return 1;
}void FindPreNode(BiTree T){//找中序遍历的前驱结点if(T!=NULL){FindPreNode(T->lchild);if(T==Node)        //如果当前结点是目标结点final=pre;  //返回该前驱elsepre=T;      //不是则指向当前结点继续遍历FindPreNode(T->rchild);}
}