7.5、二叉树的遍历
- 先序遍历:根左右(NLR)
- 中序遍历:左根右(LNR)
- 后序遍历:左右根(LRN)
- 层次遍历:一层从左到右遍历
代码实现
//访问结点
void Vist(TreeNode *node){
printf("%d , ",node->data);
}
//先序遍历
void PreOrder(LinkTree T){
if(T != NULL){
Vist(T);
PreOrder(T->lchild);
PreOrder(T->rchild);
}
}
//中序遍历
void InOrder(LinkTree T){
if(T != NULL){
InOrder(T->lchild);
Vist(T);
InOrder(T->rchild);
}
}
//后序遍历
void PostOrder(LinkTree T){
if(T != NULL){
PostOrder(T->lchild);
PostOrder(T->rchild);
Vist(T);
}
}
//求一个二叉树的深度
int TreeDepth(LinkTree T){
if(T == NULL){
return 0;
}else{
int l = TreeDepth(T->lchild);
int r = TreeDepth(T->rchild);
return l > r? l+1:r+1;
}
}
测试
int main(){
LinkTree root;
InitTree(&root,1);
AddLeftChild(2,root);
AddRightChild(3,root);
AddLeftChild(4,root->lchild);
AddRightChild(5,root->lchild);
AddLeftChild(6,root->rchild);
AddRightChild(7,root->rchild);
printf("先序遍历:");
PreOrder(root);
printf("\n");
printf("中序遍历:");
InOrder(root);
printf("\n");
printf("后序遍历:");
PostOrder(root);
printf("\n 二叉树的深度为:%d \n",TreeDepth(root));
}
//结果:
先序遍历:1 , 2 , 4 , 5 , 3 , 6 , 7 ,
中序遍历:4 , 2 , 5 , 1 , 6 , 3 , 7 ,
后序遍历:4 , 5 , 2 , 6 , 7 , 3 , 1 ,
二叉树的深度为:3
层次遍历
借助队列来操作
//结点
typedef struct LinkNode{
TreeNode *data;
struct LinkNode *next;
}LinkNode;
//链队列定义
typedef struct{
LinkNode *front,*rear;//*front 队头指针, *rear 队尾指针
}LinkQueue;
//初始化带头结点的队列
int InitLinkQueue(LinkQueue *Q){
(*Q).front = (*Q).rear = (LinkNode *)malloc(sizeof(LinkNode));
if((*Q).front == NULL || (*Q).rear == NULL) return false;
(*Q).front->next = NULL;
return true;
};
//带头结点判断是否为空
int IsEmpty(LinkQueue Q){
if(Q.front == Q.rear) return true;
else return false;
}
//带头结点入队操作
int EnQueue(LinkQueue *Q,TreeNode *e){
LinkNode *p = (LinkNode *)malloc(sizeof(LinkNode));
if(p==NULL) return false;//分配内存失败
p->data = e;
p->next = NULL;
Q->rear->next = p;
Q->rear = p;
}
//带头结点出队操作
int DeQueue(LinkQueue *Q,TreeNode **e){
if(Q->front == Q->rear) return false;//队列为空,出队失败
LinkNode *p = Q->front->next;
*e = p->data;
Q->front->next = p->next;
if(Q->rear == p){ //如果出队的元素是对尾元素,需要特殊处理
Q->rear = Q->front;
}
free(p);//释放片
return true;
}
//访问结点
void Vist(TreeNode *node){
printf("%d , ",node->data);
}
//层次遍历
void LevelOrder(LinkTree T){
LinkQueue Q;
InitLinkQueue(&Q);
TreeNode *node;
EnQueue(&Q,T);
while(!IsEmpty(Q)){
DeQueue(&Q,&node);
Vist(node);
if(node->lchild != NULL) EnQueue(&Q,node->lchild);
if(node->rchild != NULL) EnQueue(&Q,node->rchild);
}
}
测试
int main(){
printf("层次遍历:");
LevelOrder(root);
}
//结果:
层次遍历:1 , 2 , 3 , 4 , 5 , 6 , 7 ,
知道遍历恢复二叉树,
必须需要知道其中之一:
-
中序 + 前序
-
中序 + 后序
-
中序 + 层次
可以得到一个唯一的二叉树
标签:node,遍历,LinkNode,代码,NULL,front,数据结构,root From: https://www.cnblogs.com/shuisanya/p/16849418.html