devbox
笔触狂放9
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

【数据结构】二叉树的遍历知识点_已知一棵二叉树的层次序列为abcdef,中序序列为badcfe,则先序序列为( )。

作者：笔触狂放9 | 2024-06-16 15:17:04

赞

踩

已知一棵二叉树的层次序列为abcdef,中序序列为badcfe,则先序序列为( )。

一、二叉树的构造

（1）在构造二叉树时，采用的是以递归的方式进行构造，递归构造二叉树的算法如下所示：

#include<stdio.h>
#include<stdlib.h>
typedef int ElemType;
typedef int Status;
typedef struct BiTNode
{
	ElemType data;
	struct BiTNode *lchild;
	struct BiTNode *rchild;
}BiTNode,*BiTree;
Status InputTree(BiTree &T)
{
	ElemType num;
	scanf("%d",&num);
	if(num==0)
		T=NULL;
	else
	{
		T=(BiTNode *)malloc(sizeof(BiTNode));
	    if(!T)
		{
		    printf("二叉树构造失败!\n");
		   exit(0);
		}
	    T->data=num;
	    InputTree(T->lchild);
	    InputTree(T->rchild);
	}
	return 0;
}
Status FistTree(BiTree &T)
{
	if(T)
	{
		printf("%d ",T->data);
		FistTree(T->lchild);
		FistTree(T->rchild);
	}
	else
		T=NULL;	
	return 0;
}
int main()
{
	BiTree T;
	printf("输入数据进入二叉树（输入数字0子树根为空）:\n");
	InputTree(T);
	printf("遍历二叉树中所有数据\n");
	FistTree(T);
	printf("\n");
	return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52

构造一颗二叉树的运行截图如下所示：
在这里插入图片描述
（2）实现二叉树的各种基本运算：查找节点、返回父节点、子节点、高度的算法如下所示：

#include<stdio.h>
#include<stdlib.h>
typedef int ElemType;
typedef int Status;
typedef struct BiTNode
{
	ElemType data;
	struct BiTNode *lchild;
	struct BiTNode *rchild;
}BiTNode,*BiTree;
Status CreateTree(BiTree &T)
{
	int number;
	scanf("%d",&number);
	if(number=='\0')
	{
		T=NULL;
	}
	else
	{
        T=(BiTNode *)malloc(sizeof(BiTNode));
	    if(!T)
		{
			printf("二叉链表创建失败!");
		    exit(0);
		}
		T->data=number;
		CreateTree(T->lchild);
		CreateTree(T->rchild);
	}
	return 0;
}
Status FindTree(BiTree &T,ElemType e)
{
	BiTree p=T;
	if(p==NULL)
		return -1;
	if(p->data==e)
	{
		printf("节点已找到:%d\n",p->data);
		return 0;
	}
	if(!FindTree(p->lchild,e))
		FindTree(p->rchild,e);
	if(!FindTree(p->rchild,e))
		FindTree(p->lchild,e);
}
Status DethTree(BiTree &T)
{
	int left=0;
	int right=0;
	if(T)
	{
		left+=1+DethTree(T->lchild);
		right+=1+DethTree(T->rchild);
		return left>right?left:right;
	}
	else
        return 0;
}
Status printTree(BiTree &T,ElemType e)
{
	BiTree p=T;
	BiTree q=NULL;
	if(p==NULL)
		return -1;
	else
	{
		if(p->data==e)
		{
			printf("该节点为:%d\n",p->data);
			if(p->lchild!=NULL)
			{
		        if(p->lchild->data!=0)
				{
			       printf("该节点的左孩子为:%d\n",p->lchild->data);
				}
		    
			}
		    if(p->rchild!=NULL)
			{
			    if(p->rchild->data!=0)
				{
			       printf("该节点的右孩子为:%d\n",p->rchild->data);
				}
			}
		}
	}
	printTree(p->lchild,e);
	printTree(p->rchild,e);
}
int main()
{
	int num1,num2;
	BiTree T;
	printf("输入数据进入二叉树（输入数字0子树根为空）:\n");
	CreateTree(T);
	printf("输入你要查找的节点:");
	scanf("%d",&num1);
	FindTree(T,num1);
	printf("输入你要查找的节点,并返回其子节点:");
    scanf("%d",&num2);
	printTree(T,num2);
	printf("树的深度:");
	printf("%d",DethTree(T));
	printf("\n");
	return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108

运行结果如下图所示：
在这里插入图片描述

二、二叉树的遍历

二叉树的遍历是指按某条搜索路径访问树中每个结点，使得每个结点均被访问一次，而且仅被访问一次。

二叉树是一种非线性结构，每个结点都可能有两颗子树，需要寻找一种规律，以便于二叉树上的结点能排列在一个线性队列上，进而便于遍历。

由二叉树的递归定义可知，遍历一颗二叉树便要决定对根结点 N，左子树 L，右子树 R 的访问顺序。常见的遍历顺序有：先序（NLR）、中序（LNR）、后序（LRN）三种遍历算法。其中“序”指的是根结点在何时被访问。

1. 先序遍历（NLR）

先序遍历的操作过程如下：
若二叉树为空，不进行遍历；否则：
（1）访问根结点；
（2）先遍历左子树；
（3）先遍历右子树；
对应的递归算法如下所示：

 void PreOrder(BiTree T){
     if(T!=null){
        visit(T);  //访问根结点
        PreOrder(T->lchild);  //访问左子树
        PreOrder(T->rchild);  //访问右子树
     }
 }

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7

下图所示的二叉树，先序遍历所得结点序列如下：
在这里插入图片描述

2. 中序遍历（LNR）

中序遍历的操作过程如下：
若二叉树为空，不进行遍历；否则：
（1）先遍历左子树；
（2）访问根结点；
（3）先遍历右子树；
对应的递归算法如下所示：

 void PreOrder(BiTree T){
     if(T!=null){
        PreOrder(T->lchild);  //访问左子树
         visit(T);  //访问根结点
        PreOrder(T->rchild);  //访问右子树
     }
 }

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7

下图所示的二叉树，中序遍历所得结点序列如下：
在这里插入图片描述

3. 后序遍历（LRN）

后序遍历的操作过程如下：
若二叉树为空，不进行遍历；否则：
（1）先遍历左子树；
（2）先遍历右子树；
（3）访问根结点；
对应的递归算法如下所示：

 void PreOrder(BiTree T){
     if(T!=null){
        PreOrder(T->lchild);  //访问左子树
        PreOrder(T->rchild);  //访问右子树
        visit(T);  //访问根结点
     }
 }

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7

下图所示的二叉树，后序遍历所得结点序列如下：
在这里插入图片描述

注意：上述三种遍历算法中，递归遍历左、右子树的顺序都是固定的，只是访问根结点的顺序不同。不管采用哪种遍历算法，每个结点访问一次且仅被访问一次，故时间复杂度都为 O(n)。

4. 层次遍历（队列）

在使用层次算法遍历二叉树时，需要借助一个队列。层次遍历的操作流程如下：
（1）先将二叉树根结点入队，然后出队，访问出队结点，若它由左子树，则将左子树根结点入队；
（2）若它有右子树，则将右子树根结点入队，然后出队，访问出队结点；
（3）如此重复上述两步，直至队列为空。

二叉树的层次遍历算法如下：

 void LevelOrder(BiTree T){
    InitQueue(Q);  //初始胡辅助队列
    BiTree p;
    EnQueue(Q,T);  //将根结点入队
    while(!isEmpty(Q)){  //队列不空则循环
       DeQueue(Q,p);  //队头结点出队
       visit(p);  //访问出队结点
       if(p->lchild!=null)
          EnQueue(Q,p->lchild);  //左子树不空，则左子树根结点入队
       if(p->rchild!=null)
          EnQueue(Q,p->rchild);  //右子树不空，则右子树根结点入队
   }
 }

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13

层次算法操作示意图如下图所示：
在这里插入图片描述

5. 由遍历二叉树构造二叉树

（1）由二叉树的先序序列和中序序列可以唯一的确定一颗二叉树。例如：已知一颗二叉树的先序遍历结果为：ABCDEF，中序遍历结果为：CBAEDF，则由先序和中序序列构造的二叉树如下图所示：
在这里插入图片描述
（2）由二叉树的后序序列和中序序列可以唯一确定一颗二叉树。例如：已知一颗二叉树的后序遍历结果为：DABEC，中序遍历结果为：DEBAC，则由后序和中序序列构造的二叉树如下图所示：
在这里插入图片描述
（3）由二叉树的层次序列和中序序列可以唯一确定一颗二叉树。例如：已知一颗二叉树的层次遍历结果为：ABCDEF，中序遍历结果为：BADCFE，则由层次和中序序列构造的二叉树如下图所示：
在这里插入图片描述

注意：若只知道二叉树的先序遍历和后序遍历，无法唯一确定一颗二叉树。

6. 三种遍历算法

（1）递归实现：实现二叉树的遍历的先序算法、中序算法和后序算法示例代码如下所示：

#include<stdio.h>
#include<stdlib.h>
typedef int ElemType;
typedef int Status;
typedef struct BiTNode
{
	ElemType data;
	struct BiTNode *lchild;
	struct BiTNode *rchild;
}BiTNode,*BiTree;
Status CreateTree(BiTree &T)
{
	int number;
	scanf("%d",&number);
	if(number=='\0')
	{
		T=NULL;
	}
	else
	{
        T=(BiTNode *)malloc(sizeof(BiTNode));
	    if(!T)
		{
			printf("二叉链表创建失败!");
		    exit(0);
		}
		T->data=number;
		CreateTree(T->lchild);
		CreateTree(T->rchild);
	}
	return 0;
}
Status FirstTree(BiTree &T)
{
	if(T)
	{
		printf("%d ",T->data);
		FirstTree(T->lchild);
		FirstTree(T->rchild);
	}
	else
	    return 0;
}
Status SecondTree(BiTree &T)
{
	if(T)
	{
		SecondTree(T->lchild);
		printf("%d ",T->data);
		SecondTree(T->rchild);
	}
	else
	    return 0;
}
Status FinalTree(BiTree &T)
{
	if(T)
	{
		FinalTree(T->lchild);
		FinalTree(T->rchild);
		printf("%d ",T->data);
	}
	else
	    return 0;
}
Status DethTree(BiTree &T)
{
	int left=0;
	int right=0;
	if(T)
	{
		left+=1+DethTree(T->lchild);
		right+=1+DethTree(T->rchild);
		return left>right?left:right;
	}
	else
        return 0;
}
int main()
{
	BiTree T;
	printf("输入数据进入二叉树（输入数字0子树根为空）:\n");
	CreateTree(T);
	printf("先序遍历:");
	FirstTree(T);
	printf("\n");
	printf("中序遍历:");
	SecondTree(T);
	printf("\n");
    printf("后序遍历:");
	FinalTree(T);
	printf("\n");
	printf("树的深度:");
	printf("%d",DethTree(T));
	printf("\n");
	return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97

三种遍历算法遍历二叉树的运行截图如下所示：
在这里插入图片描述
（2）非递归实现：实现二叉树的遍历的先序算法、中序算法和后序算法示例代码如下所示：

#include<stdio.h>
#include<stdlib.h>
#define STACK_INIT_SIZE 100
#define STACKINCERMENT 10
typedef int ElemType;
typedef int Status;
typedef struct BiTNode
{
	ElemType data;
	struct BiTNode *lchild;
	struct BiTNode *rchild;
}BiTNode,*BiTree;
typedef BiTree SElemType;
typedef struct 
{
	SElemType *base;
	SElemType *top;
	int stacksize;
}SqStack;
Status InitStack(SqStack &S)//创建栈
{
	S.base=(SElemType *)malloc(STACK_INIT_SIZE * sizeof(SElemType));
	if(!S.base)
		exit(-1);
	S.top=S.base;
	S.stacksize=STACK_INIT_SIZE;
	return 0;
}
Status push(SqStack &S,SElemType e)//入栈
{
	if(S.top-S.base>=S.stacksize)
	{
		S.base=(SElemType *)realloc(S.base,(S.stacksize+STACKINCERMENT) * sizeof(SElemType));
		if(!S.base)
			exit(0);
		S.top=S.base+S.stacksize;
		S.stacksize+=STACKINCERMENT;
	}
	*S.top++=e;
	return 0;
}
Status gettop(SqStack &S,SElemType &e)//获取栈顶元素
{
	if(S.top==S.base)
		return -1;
	e=*(S.top-1);
	return 0;
}
Status pop(SqStack &S,SElemType &e)//栈顶元素出栈
{
	if(S.top==S.base)
		return -1;
	e=*--S.top;
	return 0;
}
Status StackEmpty(SqStack &S)//判断栈是否空
{
	if(S.base==S.top)
		return true;
	else
		return false;
}
Status CreateTree(BiTree &T)
{
    int num;
	scanf("%d",&num);
	if(num=='\0')
		T=NULL;
	else
	{
		T=(struct BiTNode *)malloc(sizeof(BiTNode));
		if(!T)
			exit(-1);
		T->data=num;
		CreateTree(T->lchild);
		CreateTree(T->rchild);
	}
	return 0;
}
Status FistTree(BiTree &T)//先序遍历
{
	SqStack S;
	BiTree p=T;
	InitStack(S);
	while(p!='\0'||!StackEmpty(S))
	{
		if(p!='\0')
		{
			push(S,p);//入栈
			printf("%d ",p->data);
			p=p->lchild;
		}
		else
		{
			pop(S,p);//栈顶元素出栈
			p=p->rchild;
		}
	}
	return 0;
}
Status MiddleTree(BiTree &T)//中序遍历
{
	SqStack S;
	BiTree p=T;
	InitStack(S);
	while(p!='\0'||!StackEmpty(S))
	{
		if(p!='\0')
		{
			push(S,p);
			p=p->lchild;
			
		}
		else
		{
			pop(S,p);
			printf("%d ",p->data);
			p=p->rchild;
		}
	}
	return 0;
}


Status FinalTree(BiTree &T)//后序遍历
{ 
	SqStack S;
	InitStack(S);
	BiTree p=T;
	BiTree q;
	push(S,p);
	while(!p||!StackEmpty(S))
	{
		gettop(S,p);
		if((p->lchild==NULL&&p->rchild==NULL)||(q==p->lchild||q==p->rchild))
		{
			printf("%d ",p->data);
			pop(S,p);
			q=p;
		}
		else
		{
			if(p->rchild!=NULL)
				push(S,p->rchild);
			if(p->lchild!=NULL)
				push(S,p->lchild);
		}
	}
	return 0;
}

Status DethTree(BiTree &T)//树的深度
{
	int left=0;
	int right=0;
	if(T)
	{
		left+=1+DethTree(T->lchild);
		right+=1+DethTree(T->rchild);
		return left>right?left:right;
	}
	else
		return 0;
}
int main()
{
	BiTree T;
	printf("二叉树的创建（输入0时子树为空）:\n");
	CreateTree(T);
	printf("二叉树非递归先序遍历:\n");
	FistTree(T);
	printf("\n");
	printf("二叉树非递归中序遍历:\n");
	MiddleTree(T);
	printf("\n");
	printf("二叉树非递归后续遍历:\n");
    FinalTree(T);
	printf("\n");
	printf("二叉树的深度:%d\n",DethTree(T));
	return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120
  • 121
  • 122
  • 123
  • 124
  • 125
  • 126
  • 127
  • 128
  • 129
  • 130
  • 131
  • 132
  • 133
  • 134
  • 135
  • 136
  • 137
  • 138
  • 139
  • 140
  • 141
  • 142
  • 143
  • 144
  • 145
  • 146
  • 147
  • 148
  • 149
  • 150
  • 151
  • 152
  • 153
  • 154
  • 155
  • 156
  • 157
  • 158
  • 159
  • 160
  • 161
  • 162
  • 163
  • 164
  • 165
  • 166
  • 167
  • 168
  • 169
  • 170
  • 171
  • 172
  • 173
  • 174
  • 175
  • 176
  • 177
  • 178
  • 179
  • 180
  • 181

运行结果如下图所示：
在这里插入图片描述

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/笔触狂放9/article/detail/727132
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号