编程中的树的遍历分为哪三种类型

A. 扩展先序遍历序列扩展先序遍历序列

在大学计算机基础课程《数据结构与算法 C语言描述》中，扩展先序遍历序列是一个重要的知识点。它主要针对二叉树的结构进行讲解。二叉树的遍历方式有先序遍历、中序遍历和后序遍历，对于每一个二叉树，这三种遍历方式分别得到的序列是唯一且对应的，它们能准确地反映出树的结构信息。

然而，当我们需要在编程中直观且高效地构建二叉树时，层次遍历和扩展先序遍历就显得尤为重要。层次遍历，也称为广度优先遍历，按照从上到下、从左到右的顺序访问二叉树的节点，这种方式有助于我们理解树的层次结构。而扩展先序遍历则是先序遍历的变种，它在序列中不仅包含根节点，还额外包含了根节点的子节点的先序遍历序列，这种形式更便于我们在程序中构建出完整的二叉树结构。

通过扩展先序遍历，我们可以明确地按照特定顺序排列节点，这对于理解和构建复杂二叉树模型非常有帮助。总结来说，扩展先序遍历序列是理解二叉树遍历和构建的有效工具，它结合了先序遍历的直观性和层次遍历的高效性，是数据结构学习中的重要组成部分。

B. 什么是二叉树

二叉树

在计算机科学中，二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用于实现二叉查找树和二叉堆。

二叉树的每个结点至多只有二棵子树毁首好(不存在度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒。二叉树的第i层至多有2^{i-1}个结点；深度为k的二叉树至多有2^k-1个结点；对任何一棵二叉树T，如果其终端结点数为n_0，度为2的结点数为n_2，则n_0=n_2+1。

一棵深度为k，且有2^k-1个节点的二叉树，称为满二叉树。这种树的特点是每一层上的节点数都是最大节点数。而在一棵二叉树中，除最后一层外，若其余层都是满的，并且最后一层或者是满的，或者是在右边缺少连续若干节点，则此二叉树为完全二叉树。具有n个节点的完全二叉树的深度为log2n+1。深度为k的完全二叉树，至少有2^（k-1)个节点，至多有2^k-1个节点。

一、定义

二叉树在图论中是这样定义的：二叉树是一个连通的无环图，并且每一个顶点的度不大于3。有根二叉树还要满足根结点的度不大于2。有了根结点之后，每个顶点定义了唯一的父结点，和最多2个子结点。然而，没有足够的信息来区分左结点和右结点。如果不考虑连通性，允许图中有多个连通分量，这样的结构叫做森林。

二、基本概念

二叉树是递归定义的，其结点有左右子树之分，逻辑上二叉树有五种基本形态：

(1)空二叉树——如图(a)；

线索二叉树的存储结构

在中序线索树找结点后继的规律是：若其右标志为1，则右链为线索，指示其后继，否则遍历其右子树时访问的第一个结点（右子树最左下的结点）为其后继；找结点前驱的规律是：若其左标志为1，则左链为线索，指示其前驱，否则遍历左子树时最后访问的一个结点（左子树中最右下的结点）为其前驱。

在后序线索树中找到结点的后继分三种情况：

若结点是二叉树的根，则其后继为空；若结点是其双亲的右孩子，或是其双亲的左孩子且其双亲没有右子树，则其后继即为双亲结点；若结点是其双亲的左孩子，且其双亲有右子树，则其后继为双亲右子树上按后序遍历列出的第一个结点。

数据结构定义为：

/*二叉线索存储表示*/typedefenum{Link,Thread}PointerTag;/* Link(0)：指针，Thread(1)：线索*/typedefstruct BiThrNode{ TElemType data;struct BiThrNode *lchild,*rchild;/*左右孩子指针*/PointerTag LTag,RTag;/* 左右标志 */}BiThrNode,*BiThrTree;

八、实现演示

范例二叉树：

A

B C

D E

此树的顺序结构为：ABCD##E

intmain()
{

node*p=newnode;

node*p=head;

head=p;

stringstr;

cin>>str;

creat(p,str,0)//默认根节点在str下标0的位置

return0;

}

//p为树的根节点（已开辟动态内存）,str为二叉树的顺序存储数组ABCD##E或其他顺序存储数组，r当前结点所在顺序存储数组位置.

intmain()

{

node*p=newnode;

node*p=head;

head=p;

stringstr;

cin>>str;

creat(p,str,0)//默认根节点在str下标0的位置

return0;

}

//p为树的根节点（已开辟动态内存）,str为二叉树的顺序存储数组ABCD##E或其他顺序存储数组，r当前结点所在顺序存储数组位置。

voidcreat(node*p,stringstr,intr)

{

p->data=str[r];

if(str[r*2+1]=='#'||r*2+1>str.size()-1)p->lch=NULL;

else

{

p->lch=newnode;

creat(p->lch,str,r*2+1);

}

if(str[r*2+2]=='#'||r*2+2>str.size()-1)p->rch=NULL;

else

{

p->rch=newnode;

creat(p->rch,str,r*2+2);

}

}