2024年10月二叉树的遍历算法图解（二叉树的遍历）
⑴二叉树的遍历算法图解（二叉树的遍历
⑵．遍历方案从二叉树的递归定义可知，一棵非空的二叉树由根结点及左、右子树这三个基本部分组成。因此，在任一给定结点上，可以按某种次序执行三个操作：（访问结点本身(N)，（遍历该结点的左子树(L)，（遍历该结点的右子树(R)。以上三种操作有六种执行次序：NLR、LNR、LRN、NRL、RNL、RLN。注意：前三种次序与后三种次序对称，故只讨论先左后右的前三种次序。．三种遍历的命名根据访问结点操作发生位置命名：①NLR：前序遍历(PreorderTraversal亦称(先序遍历))——访问结点的操作发生在遍历其左右子树之前。②LNR：中序遍历(InorderTraversal)——访问结点的操作发生在遍历其左右子树之中(间)。③LRN：后序遍历(PostorderTraversal)——访问结点的操作发生在遍历其左右子树之后。注意：由于被访问的结点必是某子树的根，所以N(Node)、L(Leftsubtlee)和R(Rightsubtree)又可解释为根、根的左子树和根的右子树。NLR、LNR和LRN分别又称为先根遍历、中根遍历和后根遍历。遍历算法．中序遍历的递归算法定义：若二叉树非空，则依次执行如下操作：()遍历左子树；()访问根结点；()遍历右子树。．先序遍历的递归算法定义：若二叉树非空，则依次执行如下操作：()访问根结点；()遍历左子树；()遍历右子树。．后序遍历得递归算法定义：若二叉树非空，则依次执行如下操作：()遍历左子树；()遍历右子树；()访问根结点。
⑶c++二叉树的几种遍历算法
⑷遍历二叉树的所有结点且仅访问一次。按照根节点位置的不同分为前序遍历，中序遍历，后序遍历（除此之外还有层次遍历，但不常用，此处不做解释。
⑸前序遍历：根节点-》左子树-》右子树（根节点在前面。
⑹中序遍历：左子树-》根节点-》右子树（根节点在中间。
⑺后序遍历：左子树-》右子树-》根节点（根节点在后边。
⑻例如：求下面树的三种遍历：
⑼前序遍历：abdefgc；
⑽中序遍历：debgfac；
⑾后序遍历：edgfbca。
⑿遍历二叉树二叉树是一种非线性的数据结构，在对它进行操作时，总是需要逐一对每个数据元素实施操作，这样就存在一个操作顺序问题，由此提出了二叉树的遍历操作。所谓遍历二叉树就是按某种顺序访问二叉树中的每个结点一次且仅一次的过程。这里的访问可以是输出、比较、更新、查看元素内容等等各种操作。二叉树的遍历方式分为两大类：一类按根、左子树和右子树三个部分进行访问；另一类按层次访问。下面我们将分别进行讨论。、按根、左子树和右子树三部分进行遍历遍历二叉树的顺序存在下面种可能：TLR（根左右,TRL（根右左LTR（左根右,RTL（右根左LRT（左右根,RLT（右左根其中，TRL、RTL和RLT三种顺序在左右子树之间均是先右子树后左子树，这与人们先左后右的习惯不同，因此，往往不予采用。余下的三种顺序TLR、LTR和LRT根据根访问的位置不同分别被称为先序遍历、中序遍历和后序遍历。（先序遍历若二叉树为空，则结束遍历操作；否则访问根结点；先序遍历左子树；先序遍历右子树。（中序遍历若二叉树为空，则结束遍历操作；否则中序遍历左子树；访问根结点；中序遍历右子树。（后序遍历若二叉树为空，则结束遍历操作；否则后序遍历左子树；后序遍历右子树；访问根结点。例如。以下是一棵二叉树及其经过三种遍历所得到的相应遍历序列二叉树的两种遍历方法：（对一棵二叉树中序遍历时，若我们将二叉树严格地按左子树的所有结点位于根结点的左侧，右子树的所有结点位于根右侧的形式绘制，就可以对每个结点做一条垂线，映射到下面的水平线上，由此得到的顺序就是该二叉树的中序遍历序列（任何一棵二叉树都可以将它的外部轮廓用一条线绘制出来，我们将它称为二叉树的包线，这条包线对于理解二叉树的遍历过程很有用。由此可以看出：（遍历操作实际上是将非线性结构线性化的过程，其结果为线性序列，并根据采用的遍历顺序分别称为先序序列、中序序列或后序序列；（遍历操作是一个递归的过程，因此，这三种遍历操作的算法可以用递归函数实现。（先序遍历递归算法voidPreOrder(BTreeBT){if(BT){Visit(BT);PreOrder(BT-》Lchild);PreOrder(BT-》Rchild);}（中序遍历递归算法voidInOrder(BTreeBT){if(BT){InOrder(BT-》Lchild);Visit(BT);InOrder(BT-》Rchild);}}（后序遍历递归算法voidPostOrder(BTreeBT){if(BT){PostOrder(BT-》Lchild);PostOrder(BT-》Rchild);Visit(BT);}}、按层次遍历二叉树实现方法为从上层到下层，每层中从左侧到右侧依次访问每个结点。下面我们将给出一棵二叉树及其按层次顺序访问其中每个结点的遍历序列。voidLevelOreder(QBTreeBT){for(i=;i《=BT.n;i++)if(BT.elem[i]!=’#’)Visite(BT.elem[i]);}二叉树用链式存储结构表示时，按层遍历的算法实现访问过程描述如下：访问根结点，并将该结点记录下来；若记录的所有结点都已处理完毕，则结束遍历操作；否则重复下列操作。取出记录中第一个还没有访问孩子的结点，若它有左孩子，则访问左孩子，并将记录下来；若它有右孩子，则访问右孩子，并记录下来。在这个算法中，应使用一个队列结构完成这项操作。所谓记录访问结点就是入队操作；而取出记录的结点就是出队操作。这样一来，我们的算法就可以描述成下列形式：（访问根结点，并将根结点入队；（当队列不空时，重复下列操作：从队列退出一个结点；若其有左孩子，则访问左孩子，并将其左孩子入队；若其有右孩子，则访问右孩子，并将其右孩子入队；voidLevelOrder(BTree*BT){if(!BT)exit;InitQueue(Q);p=BT;//初始化Visite(p);EnQueue(&Q,p);//访问根结点，并将根结点入队while(!QueueEmpty(Q)){//当队非空时重复执行下列操作DeQueue(&Q,&p);//出队if(!p-》Lchild){Visite(p-》Lchild);EnQueue(&Q,p-》Lchild);//处理左孩子《br》if(!p-》Rchild){Visite(p-》Rchild);EnQueue(&Q,p-》Rchild);//处理右孩子《br》}}五、典型二叉树的操作算法、输入一个二叉树的先序序列，构造这棵二叉树为了保证唯一地构造出所希望的二叉树，在键入这棵树的先序序列时，需要在所有空二叉树的位置上填补一个特殊的字符，比如，’#’。在算法中，需要对每个输入的字符进行判断，如果对应的字符是’#’，则在相应的位置上构造一棵空二叉树；否则，创建一个新结点。整个算法结构以先序遍历递归算法为基础，二叉树中结点之间的指针连接是通过指针参数在递归调用返回时完成。算法：BTreePre_Create_BT(){getch(ch);if(ch==’#’)returnNULL;//构造空树else{BT=(BTree)malloc(sizeof(BTLinklist));//构造新结点BT-》data=ch;BT-》lchild=Pre_Create_BT();//构造左子树BT-》rchild=Pre_Create_BT();//构造右子树returnBT;}}、计算一棵二叉树的叶子结点数目这个操作可以使用三种遍历顺序中的任何一种，只是需要将访问操作变成判断该结点是否为叶子结点，如果是叶子结点将累加器加即可。下面这个算法是利用中序遍历实现的。算法：voidLeaf(BTreeBT,int*count){if(BT){Leaf(BT-》child,&count);//计算左子树的叶子结点个数if(BT-》lchild==NULL&&BT-》rchild==NULL)(*count)++;Leaf(BT-》rchild,&count);//计算右子树的叶子结点个数}}、交换二叉树的左右子树许多操作可以利用三种遍历顺序的任何一种，只是某种遍历顺序实现起来更加方便一些。而有些操作则不然，它只能使用其中的一种或两种遍历顺序。将二叉树中所有结点的左右子树进行交换这个操作就属于这类情况。算法：voidchange_left_right(BTreeBT){if(BT){change_left_right(BT-》lchild);change_left_right(BT-》rchild);BT-》lchild《-》BT-》rchild;}}、求二叉树的高度这个操作使用后序遍历比较符合人们求解二叉树高度的思维方式。首先分别求出左右子树的高度，在此基础上得出该棵树的高度，即左右子树较大的高度值加。算法：inthight(BTreeBT){//h和h分别是以BT为根的左右子树的高度if(BT==NULL)return;else{h=hight(BT-》lchild);h=hight(BT-》right);returnmax{h,h}+;}}六、树、森林与二叉树的转换、树、森林转换成二叉树将一棵树转换成二叉树的方法：将一棵树转换成二叉树实际上就是将这棵树用孩子兄弟表示法存储即可，此时，树中的每个结点最多有两个指针：一个指针指向第一个孩子，另一个指针指向右侧第一个兄弟。当你将这两个指针看作是二叉树中的左孩子指针和孩子右指针时，就是一棵二叉树了。特点：一棵树转换成二叉树后，根结点没有右孩子。将森林转换成二叉树的方法与一棵树转换成二叉树的方法类似，只是把森林中所有树的根结点看作兄弟关系，并对其中的每棵树依依地进行转换。、二叉树还原成树或森林这个过程实际上是树、森林转换成二叉树的逆过程，即将该二叉树看作是树或森林的孩子兄弟表示法。比如，若二叉树为空，树也为空；否则，由二叉树的根结点开始，延右指针向下走，直到为空，途经的结点个数是相应森林所含树的棵数；若某个结点的左指针非空，说明这个结点在树中必有孩子，并且从二叉树中该结点左指针所指结点开始，延右指针向下走，直到为空，途经的结点个数就是这个结点的孩子数目。第节哈夫曼树及其应用、哈夫曼树的定义及特点在二叉树中，一个结点到另一个结点之间的分支构成这两个结点之间的路径。这三棵二叉树的带权路径长度分别为：WPL=*+*+*+*+*+*=WPL=*+*+*+*+*+*=WPL=*+*+*+*+*+*=哈夫曼树的一个重要特点是：没有度为的结点。、构造哈夫曼树的过程：（将给定的n个权值{w,w,...,wn}作为n个根结点的权值构造一个具有n棵二叉树的森林{T,T,...,Tn}，其中每棵二叉树只有一个根结点；（在森林中选取两棵根结点权值最小的二叉树作为左右子树构造一棵新二叉树，新二叉树的根结点权值为这两棵树根的权值之和；（在森林中，将上面选择的这两棵根权值最小的二叉树从森林中删除，并将刚刚新构造的二叉树加入到森林中；（重复上面（和（，直到森林中只有一棵二叉树为止。这棵二叉树就是哈夫曼树。例如：假设有一组权值{,,,,,,,}，下面我们将利用这组权值演示构造哈夫曼树的过程。它的带权的路径长度为：WPL=(+)*+(+)*+(+++)*=．判定树在很多问题的处理过程中，需要进行大量的条件判断，这些判断结构的设计直接影响着程序的执行效率。例如，编制一个程序，将百分制转换成五个等级输出。大家可能认为这个程序很简单，并且很快就可以用下列形式编写出来：if(socre《)printf(“bad“);elseif(socre《)printf(“pass“);elseif(score《)printf(“general“);elseif(score《)printf(“good“);esleprintf(“verygood“);在实际应用中，往往各个分数段的分布并不是均匀的。下面就是在一次考试中某门课程的各分数段的分布情况：．前缀编码在电文传输中，需要将电文中出现的每个字符进行二进制编码。在设计编码时需要遵守两个原则：（发送方传输的二进制编码，到接收方解码后必须具有唯一性，即解码结果与发送方发送的电文完全一样；（发送的二进制编码尽可能地短。下面我们介绍两种编码的方式。（等长编码这种编码方式的特点是每个字符的编码长度相同（编码长度就是每个编码所含的二进制位数。假设字符集只含有个字符A，B，C，D，用二进制两位表示的编码分别为，，，。若现在有一段电文为：ABADA，则应发送二进制序列：，总长度为位。当接收方接收到这段电文后，将按两位一段进行译码。这种编码的特点是译码简单且具有唯一性，但编码长度并不是最短的。（不等长编码在传送电文时，为了使其二进制位数尽可能地少，可以将每个字符的编码设计为不等长的，使用频度较高的字符分配一个相对比较短的编码，使用频度较低的字符分配一个比较长的编码。例如，可以为A，B，C，D四个字符分别分配，，，，并可将上述电文用二进制序列：发送，其长度只有个二进制位，但随之带来了一个问题，接收方接到这段电文后无法进行译码，因为无法断定前面个是个A，个B、个A，还是个B，即译码不唯一，因此这种编码方法不可使用。（利用字符集中每个字符的使用频率作为权值构造一个哈夫曼树；（从根结点开始，为到每个叶子结点路径上的左分支赋予，右分支赋予，并从根到叶子方向形成该叶子结点的编码。假设有一个电文字符集中有个字符，每个字符的使用频率分别为{.,.,.,.,.,.,.,.}，现以此为例设计哈夫曼编码。哈夫曼编码设计过程为：（为方便计算，将所有字符的频度乘以，使其转换成整型数值集合，得到{,,,,,,,}；（以此集合中的数值作为叶子结点的权值构造一棵哈夫曼树，如图-所示；（由此哈夫曼树生成哈夫曼编码，如图-所示。最后得出每个字符的编码为：比如，发送一段编码：，接收方可以准确地通过译码得到：⑥⑥⑦⑤②⑧。
⒀这里有二叉树先序、中序、后序三种遍历的非递归算法，此三个算法可视为标准算法。.先序遍历非递归算法#definemaxsizetypedefstruct{BitreeElem[maxsize];inttop;}SqStack;voidPreOrderUnrec(Bitreet){SqStacks;StackInit(s);p=t;while(p!=null||!StackEmpty(s)){while(p!=null)//遍历左子树{visite(p-》data);push(s,p);p=p-》lchild;}//endwhileif(!StackEmpty(s))//通过下一次循环中的内嵌while实现右子树遍历{p=pop(s);p=p-》rchild;}//endif}//endwhile}//PreOrderUnrec.中序遍历非递归算法#definemaxsizetypedefstruct{BitreeElem[maxsize];inttop;}SqStack;voidInOrderUnrec(Bitreet){SqStacks;StackInit(s);p=t;while(p!=null||!StackEmpty(s)){while(p!=null)//遍历左子树{push(s,p);p=p-》lchild;}//endwhileif(!StackEmpty(s)){p=pop(s);visite(p-》data);//访问根结点p=p-》rchild;//通过下一次循环实现右子树遍历}//endif}//endwhile}//InOrderUnrec.后序遍历非递归算法#definemaxsizetypedefenum{L,R}tagtype;typedefstruct{Bitreeptr;tagtypetag;}stacknode;typedefstruct{stacknodeElem[maxsize];inttop;}SqStack;voidPostOrderUnrec(Bitreet){SqStacks;stacknodex;StackInit(s);p=t;do{while(p!=null)//遍历左子树{x.ptr=p;x.tag=L;//标记为左子树push(s,x);p=p-》lchild;}while(!StackEmpty(s)&&s.Elem[s.top].tag==R){x=pop(s);p=x.ptr;visite(p-》data);//tag为R，表示右子树访问完毕，故访问根结点}if(!StackEmpty(s)){s.Elem[s.top].tag=R;//遍历右子树p=s.Elem[s.top].ptr-》rchild;}}while(!StackEmpty(s));}//PostOrderUnrec
⒁二叉树先序遍历算法流程图怎么画，学的是数据结构c语言
⒂在计算机软件专业中，数据结构、以及C语言这两门课程是非常重要的两门课程。最为重要的是：如果将来想做计算机软件开发工作的话，那么对C语言中的指针编程、以及递归的概念是必须要熟练精通掌握的，因为它和数据结构课程中的链表、二叉树等内容的关系实在是太紧密了。但是这个编程技能必须要依靠自己多上机实践才能够真正彻底掌握的。首先要搞明白二叉树的几种遍历方法：（、先序遍历法：根左右；（、中序遍历法：左根右；（、后序遍历法：左右根。其中根：表示根节点；左：表示左子树；右：表示右子树。至于谈到如何画先序遍历的流程图，可以这样考虑：按照递归的算法进行遍历一棵二叉树。程序首先访问根节点，如果根节点的值为空（NULL，则停止访问；如果根节点的值非空，则递归访问二叉树的左子树（left，然后是依然判断二叉树下面的左子树下面的根节点是否为空（NULL，如果根节点的值为空（NULL，则返回上一层，再访问二叉树的右子树（right。依此类推。
⒃二叉树的层次遍历算法
⒄二叉树的层次遍历算法有如下三种方法：
⒅给定一棵二叉树，要求进行分层遍历，每层的节点值单独打印一行，下图给出事例结构：
⒆对此二叉树遍历的结果应该是：
⒇第一种方法，就是利用递归的方法，按层进行打印，我们把根节点当做第层，之后层次依次增加，如果我们想打印第二层怎么办呢，利用递归的代码如下：
⒈[cpp]viewplaincopy
⒉intprint_at_level(TreeT,intlevel){
⒊if(!T||level《)
⒋if(==level){
⒌cout《《T-》data《《““;
⒍returnprint_at_level(T-》lchild,level-)+print_at_level(T-》rchild,level-);
⒎如果我们成功的打印了给定的层次，那么就返回非的正值，如果失败返回。有了这个思路，我们就可以应用一个循环，来打印这颗树的所有层的节点，但是有个问题就是我们不知道这棵二叉树的深度，怎么来控制循环使其结束呢，仔细看一下print_at_level，如果指定的Tree是空的，那么就直接返回，当返回的时候，我们就结束循环，说明没有节点可以打印了。
⒏[cpp]viewplaincopy
⒐voidprint_by_level_(TreeT){
⒑for(i=;;i++){
⒒if(!print_at_level(T,i))
⒓cout《《endl;
⒔以上的方法可以很清楚的看出，存在重复访问的情况，就是第层访问的次数最多，第层次之。所以这个递归的方法不是很有效的方法。
⒕第二种方法：我们可以设置两个队列，想象一下队列的特点，就是先进先出，首先把第层保存在一个队列中，然后按节点访问，并把已经访问节点的左右孩子节点放在第二个队列中，当第一个队列中的所有节点都访问完成之后，交换两个节点。这样重复下去，知道所有层的节点都被访问，这样做的代价就是空间复杂度有点高。
⒖[cpp]viewplaincopy
⒗voidprint_by_level_(TreeT){
⒘deque《tree_node_t*》q_first,q_second;
⒙q_first.push_back(T);
⒚while(!q_first.empty()){
⒛while(!q_first.empty()){
tree_node_t*temp=q_first.front();
q_first.pop_front();
cout《《temp-》data《《““;
if(temp-》lchild)
q_second.push_back(temp-》lchild);
if(temp-》rchild)
q_second.push_back(temp-》rchild);
cout《《endl;
q_first.swap(q_second);
第三种方法就是设置双指针，一个指向访问当层开始的节点，一个指向访问当层结束节点的下一个位置：
这是第一层访问的情况，当访问第层之后的结构如下，把第层的所有子节点加入之后：
之后大家就可以自己画图了，下面给出程序代码：
[cpp]viewplaincopy
voidprint_by_level_(TreeT){
vector《tree_node_t*》vec;
vec.push_back(T);
while(cur《vec.size()){
end=vec.size();
while(cur《end){
cout《《vec[cur]-》data《《““;
if(vec[cur]-》lchild)
vec.push_back(vec[cur]-》lchild);
if(vec[cur]-》rchild)
vec.push_back(vec[cur]-》rchild);
cout《《endl;
最后给出完成代码的测试用例：#########
[cpp]viewplaincopy
#include《iostream》
#include《vector》
#include《deque》
usingnamespacestd;
typedefstructtree_node_s{
structtree_node_s*lchild;
structtree_node_s*rchild;
}tree_node_t,*Tree;
voidcreate_tree(Tree*T){
charc=getchar();
if(c==’#’){
*T=(tree_node_t*)malloc(sizeof(tree_node_t));
(*T)-》data=c;
create_tree(&(*T)-》lchild);
create_tree(&(*T)-》rchild);
voidprint_tree(TreeT){
cout《《T-》data《《““;
print_tree(T-》lchild);
print_tree(T-》rchild);
intprint_at_level(TreeT,intlevel){
if(!T||level《)
if(==level){
cout《《T-》data《《““;
returnprint_at_level(T-》lchild,level-)+print_at_level(T-》rchild,level-);
voidprint_by_level_(TreeT){
for(i=;;i++){
if(!print_at_level(T,i))
cout《《endl;
voidprint_by_level_(TreeT){
deque《tree_node_t*》q_first,q_second;
q_first.push_back(T);
while(!q_first.empty()){
while(!q_first.empty()){
tree_node_t*temp=q_first.front();
q_first.pop_front();
cout《《temp-》data《《““;
if(temp-》lchild)
q_second.push_back(temp-》lchild);
if(temp-》rchild)
q_second.push_back(temp-》rchild);
cout《《endl;
q_first.swap(q_second);
voidprint_by_level_(TreeT){
vector《tree_node_t*》vec;
vec.push_back(T);
while(cur《vec.size()){
end=vec.size();
while(cur《end){
cout《《vec[cur]-》data《《““;
if(vec[cur]-》lchild)
vec.push_back(vec[cur]-》lchild);
if(vec[cur]-》rchild)
vec.push_back(vec[cur]-》rchild);
cout《《endl;
intmain(intargc,char*argv){
TreeT=NULL;
create_tree(&T);
print_tree(T);
cout《《endl;
print_by_level_(T);
cin.get();
cin.get();
遍历方案：．遍历方案从二叉树的递归定义可知，一棵非空的二叉树由根结点及左、右子树这三个基本部分组成。因此，在任一给定结点上，可以按某种次序执行三个操作：（访问结点本身(N)，（遍历该结点的左子树(L)，（遍历该结点的右子树(R)。以上三种操作有六种执行次序：NLR、LNR、LRN、NRL、RNL、RLN。注意：前三种次序与后三种次序对称，故只讨论先左后右的前三种次序。．三种遍历的命名根据访问结点操作发生位置命名：①NLR：前序遍历(PreorderTraversal亦称(先序遍历))——访问结点的操作发生在遍历其左右子树之前。②LNR：中序遍历(InorderTraversal)——访问结点的操作发生在遍历其左右子树之中(间)。③LRN：后序遍历(PostorderTraversal)——访问结点的操作发生在遍历其左右子树之后。注意：由于被访问的结点必是某子树的根，所以N(Node)、L(Leftsubtree)和R(Rightsubtree)又可解释为根、根的左子树和根的右子树。NLR、LNR和LRN分别又称为先根遍历、中根遍历和后根遍历。遍历算法．中序遍历的递归算法定义：若二叉树非空，则依次执行如下操作：()遍历左子树；()访问根结点；()遍历右子树。．先序遍历的递归算法定义：若二叉树非空，则依次执行如下操作：()访问根结点；()遍历左子树；()遍历右子树。．后序遍历得递归算法定义：若二叉树非空，则依次执行如下操作：()遍历左子树；()遍历右子树；()访问根结点。．中序遍历的算法实现用二叉链表做为存储结构，中序遍历算法可描述为：voidInOrder(BinTreeT){//算法里①~⑥是为了说明执行过程加入的标号①if(T){//如果二叉树非空②InOrder(T-》lchild)；③printf(“％c“，T-》data)；//访问结点④InOrder(T-》rchild);⑤}⑥}//InOrder遍历序列．遍历二叉树的执行踪迹三种递归遍历算法的搜索路线相同（如下图虚线所示。具体线路为：从根结点出发，逆时针沿着二叉树外缘移动，对每个结点均途径三次，最后回到根结点。．遍历序列A/BC//DEF图（中序序列（inordertraversal中序遍历二叉树时，对结点的访问次序为中序序列【例】中序遍历上图所示的二叉树时，得到的中序序列为：DBAECF（先序序列（preordertraversal先序遍历二叉树时，对结点的访问次序为先序序列【例】先序遍历上图所示的二叉树时，得到的先序序列为：ABDCEF（后序序列（postordertraversal后序遍历二叉树时，对结点的访问次序为后序序列【例】后序遍历上图所示的二叉树时，得到的后序序列为：DBEFCA（层次遍历（leveltraversal二叉树的操作定义为：若二叉树为空，则退出，否则，按照树的结构，从根开始自上而下，自左而右访问每一个结点，从而实现对每一个结点的遍历注意：（在搜索路线中，若访问结点均是第一次经过结点时进行的，则是前序遍历；若访问结点均是在第二次(或第三次)经过结点时进行的，则是中序遍历(或后序遍历)。只要将搜索路线上所有在第一次、第二次和第三次经过的结点分别列表，即可分别得到该二叉树的前序序列、中序序列和后序序列。（上述三种序列都是线性序列，有且仅有一个开始结点和一个终端结点，其余结点都有且仅有一个前趋结点和一个后继结点。为了区别于树形结构中前趋(即双亲)结点和后继(即孩子)结点的概念，对上述三种线性序列，要在某结点的前趋和后继之前冠以其遍历次序名称。【例】上图所示的二叉树中结点C，其前序前趋结点是D，前序后继结点是E；中序前趋结点是E，中序后继结点是F；后序前趋结点是F，后序后继结点是A。但是就该树的逻辑结构而言，C的前趋结点是A，后继结点是E和F。二叉链表的构造．基本思想基于先序遍历的构造，即以二叉树的先序序列为输入构造。注意：先序序列中必须加入虚结点以示空指针的位置。【例】建立上图所示二叉树，其输入的先序序列是：ABD∮∮∮CE∮∮F∮∮。．构造算法假设虚结点输入时以空格字符表示，相应的构造算法为：voidCreateBinTree(BinTree*T){//构造二叉链表。T是指向根指针的指针，故修改*T就修改了实参(根指针)本身charch；if((ch=getchar())==’’)*T=NULL；//读人空格，将相应指针置空else{//读人非空格*T=(BinTNode*)malloc(sizeof(BinTNode))；//生成结点(*T)-》data=ch；CreateBinTree(&(*T)-》lchild)；//构造左子树CreateBinTree(&(*T)-》rchild)；//构造右子树}}注意：调用该算法时，应将待建立的二叉链表的根指针的地址作为实参。【例】设root是一根指针(即它的类型是BinTree)，则调用CreateBinTree(&root)后root就指向了已构造好的二叉链表的根结点。二叉树建立过程见下面是关于二叉树的遍历、查找、删除、更新数据的代码(递归算法):[code]#include《iostream》usingnamespacestd;typedefintT;classbst{structNode{Tdata;Node*L;Node*R;Node(constT&d,Node*lp=NULL,Node*rp=NULL):data(d),L(lp),R(rp){}};Node*root;intnum;public:bst():root(NULL),num(){}voidclear(Node*t){if(t==NULL)return;clear(t-》L);clear(t-》R);deletet;}~bst(){clear(root);}voidclear(){clear(root);num=;root=NULL;}boolempty(){returnroot==NULL;}intsize(){returnnum;}TgetRoot(){if(empty())throw“emptytree“;returnroot-》data;}voidtravel(Node*tree){if(tree==NULL)return;travel(tree-》L);cout《《tree-》data《《’’;travel(tree-》R);}voidtravel(){travel(root);cout《《endl;}intheight(Node*tree){if(tree==NULL)return;intlh=height(tree-》L);intrh=height(tree-》R);return+(lh》rh?lh:rh);}intheight(){returnheight(root);}voidinsert(Node*&tree,constT&d){if(tree==NULL)tree=newNode(d);elseif(ddata)insert(tree-》L,d);elseinsert(tree-》R,d);}voidinsert(constT&d){insert(root,d);num++;}Node*&find(Node*&tree,constT&d){if(tree==NULL)returntree;if(tree-》data==d)returntree;if(ddata)returnfind(tree-》L,d);elsereturnfind(tree-》R,d);}boolfind(constT&d){returnfind(root,d)!=NULL;}boolerase(constT&d){Node*&pt=find(root,d);if(pt==NULL)returnfalse;bine(pt-》L,pt-》R);Node*p=pt;pt=pt-》R;deletep;num--;returntrue;}voidbine(Node*lc,Node*&rc){if(lc==NULL)return;if(rc==NULL)rc=lc;elsebine(lc,rc-》L);}boolupdate(constT&od,constT&nd){Node*p=find(root,od);if(p==NULL)returnfalse;erase(od);insert(nd);returntrue;}};intmain(){bstb;cout《《“inputsomeintegers:“;for(;;){intn;cin》》n;b.insert(n);if(cin.peek()==’
’)break;}b.travel();for(;;){cout《《“inputdatapair:“;intod,nd;cin》》od》》nd;if(od==-&&nd==-)break;b.update(od,nd);b.travel();}}[/code]
什么叫遍历算法(最好有例子)
遍历算法：所谓遍历(Traversal)，是指沿着某条搜索路线，依次对树中每个结点均做一次且仅做一次访问。访问结点所做的操作依赖于具体的应用问题。遍历是二叉树上最重要的运算之一，是二叉树上进行其它运算之基础。当然遍历的概念也适合于多元素集合的情况，如数组。
图遍历：图遍历又称图的遍历，属于数据结构中的内容。指的是从图中的任一顶点出发，对图中的所有顶点访问一次且只访问一次。图的遍历操作和树的遍历操作功能相似。图的遍历是图的一种基本操作，图的许多其它操作都是建立在遍历操作的基础之上。
遍历二叉树搜索路线：
从二叉树的递归定义可知，一棵非空的二叉树由根结点及左、右子树这三个基本部分组成。因此，在任一给定结点上，可以按某种次序执行三个操作：⑴访问结点本身（N，⑵遍历该结点的左子树（L，⑶遍历该结点的右子树（R。以上三种操作有六种执行次序：NLR、LNR、LRN、NRL、RNL、RLN。前三种次序与后三种次序对称。
遍历二叉树的执行踪迹三种递归遍历算法的搜索路线相同（如下图虚线所示。具体线路为：从根结点出发，逆时针沿着二叉树外缘移动，对每个结点均途径三次，最后回到根结点。
什么是二叉树数的遍历
二叉树遍历（Traversal是指沿着某条搜索路线，依次对树中每个结点均做一次且仅做一次访问。访问结点所做的操作依赖于具体的应用问题。遍历是二叉树上最重要的运算之一，是二叉树上进行其它运算之基础。遍历方案从二叉树的递归定义可知，一棵非空的二叉树由根结点及左、右子树这三个基本部分组成。因此，在任一给定结点上，可以按某种次序执行三个操作：访问结点本身（N，遍历该结点的左子树（L，遍历该结点的右子树（R。以上三种操作有六种执行次序：NLR、LNR、LRN、NRL、RNL、RLN。注意：前三种次序与后三种次序对称遍历命名根据访问结点操作发生位置命名：①NLR：前序遍历(PreorderTraversal亦称（先序遍历——访问根结点的操作发生在遍历其左右子树之前。②LNR：中序遍历(InorderTraversal)——访问根结点的操作发生在遍历其左右子树之中（间。③LRN：后序遍历(PostorderTraversal)——访问根结点的操作发生在遍历其左右子树之后。注意：由于被访问的结点必是某子树的根，所以N(Node、L(Leftsubtree和R(Rightsubtree又可解释为根、根的左子树和根的右子树。NLR、LNR和LRN分别又称为先根遍历、中根遍历和后根遍历。遍历算法．先（根序遍历的递归算法定义：若二叉树非空，则依次执行如下操作：⑴访问根结点；⑵遍历左子树；⑶遍历右子树。．中（根序遍历的递归算法定义：若二叉树非空，则依次执行如下操作：⑴遍历左子树；⑵访问根结点；⑶遍历右子树。．后（根序遍历得递归算法定义：若二叉树非空，则依次执行如下操作：⑴遍历左子树；⑵遍历右子树；⑶访问根结点。
遍历算法．中序遍历的递归算法定义：若二叉树非空，则依次执行如下操作：()遍历左子树；()访问根结点；()遍历右子树。．先序遍历的递归算法定义：若二叉树非空，则依次执行如下操作：()访问根结点；()遍历左子树；()遍历右子树。．后序遍历得递归算法定义：若二叉树非空，则依次执行如下操作：()遍历左子树；()遍历右子树；()访问根结点。