中根遍历二叉查找树所得序列一定是有序序列_带你搞定考研二叉树算法（下）...

   递归数据结构的定义   

▼▼▼

采用递归方式定义的数据结构称为递归数据结构。在递归数据结构定义中包含的递归运算称为基本递归运算。

对于二叉树&＃xff0c;采用递归数据结构的定义如下&＃xff1a;

RD &＃61; (D,Op)

其中&＃xff0c;D是所有二叉树(含空二叉树)的集合Op&＃61; {op1,op2}:

op1(b)&＃61;b ->lchild     b为含一个或一个以上节点的二叉树op2(b)&＃61;b->rchild       b为含一个或一个以上节点的二叉树

显然&＃xff0c;这两个基本的递归数据结构的运算符都是一元运算符&＃xff0c;且具有封闭性。

   二叉树的遍历算法设计   

▼▼▼

二叉树的遍历是指按照一定次序访问树中所有结点&＃xff0c;并且每个结点均被访问一次&＃xff0c;且仅被访问一次。

由二叉树的递归定义可得&＃xff1a;遍历一棵二叉树便要决定对根结点N、左子树L和右子树R的访问顺序。按照先遍历左子树再遍历右子树的原则&＃xff0c;常见的遍历次序有先序(NLR)、中序(LNR)、后序(LRN)。

常见的4中递归遍历方法如下&＃xff1a;

①先序遍历

②中序遍历

③后序遍历

④层序遍历

1先序遍历先序遍历二叉树的过程如下&＃xff1a;➤访问根结点&＃xff1b;➤先序遍历左子树&＃xff1b;➤先序遍历右子树。➤先序遍历的递归算法如下&＃xff1a;

void PreOrder(BiTree T){ if(T !&＃61; NULL) { visit(T); //访问根结点 PreOrder(T->lchild); //先序递归访问左子树 PreOrder(T->rchild); //先序递归访问右子树 }}//提示&＃xff1a;先序遍历序列中第一个结点是根结点➤先序遍历的非递归算法如下&＃xff1a;

void PreOrder(BiTree T){ InitStack(S); p &＃61; T; while(p || !StackEmpty(S)) { if(p) { visit(p->data); push(S,p); p &＃61; p->lchild; } else { pop(S,p); p &＃61; p->rchild; } } }

提示&＃xff1a;先序遍历序列中第一个结点是根结点

---

2中序遍历

中序遍历二叉树的过程如下&＃xff1a;

➤中序遍历左子树&＃xff1b;

➤访问根结点&＃xff1b;

➤中序遍历右子树。

➤中序遍历的递归算法如下&＃xff1a;

void InOrder(BiTree T){ if(T !&＃61; NULL) { InOrder(T->lchild); //中序递归访问左子树     visit(T);   //访问根结点  InOrder(T->rchild); //中序递访问右子树 }}➤中序遍历的非递归算法如下&＃xff1a;

void InOrder(BiTree T){ InitStack(S); p &＃61; T; while(p || !StackEmpty(S)) { if(p) { push(S,p); p &＃61; p->lchild; } else { pop(S,p); visit(p->data); p &＃61; p->rchild; } } }

提示&＃xff1a;中序遍历序列中&＃xff0c;若已知根结点&＃xff0c;则其前为左子树的中序遍历序列&＃xff0c;其后为右子树的中序遍历序列。

---

3后序遍历后序遍历二叉树的过程如下&＃xff1a;➤后序遍历左子树&＃xff1b;➤后序遍历右子树&＃xff1b;➤访问根结点。➤后序遍历的递归算法如下&＃xff1a;

void PostOrder(BiTree T){ if(T !&＃61; NULL) { PostOrder(T->lchild); //中序递归访问左子树    PostOrder(T->rchild);  //中序递访问右子树     visit(T);   //访问根结点  }}

➤后序遍历的非递归算法如下&＃xff1a;

void PostOrder(BiTree T){ InitStack(S); p &＃61; T; while(p || !StackEmpty(S)) { if(p) { push(S,p); p &＃61; p->lchild; } else { pop(S,p); if(p->rchild && (p->rchild).tag &＃61;&＃61; 0) { push(S,p); p &＃61; p->rchild; } else { visit(p->data); p.tag &＃61; 1; p &＃61; NULL; } } } }

说明&＃xff1a;在二叉树的存储结构中每个结点增加一个是否访问的tag域(标记)&＃xff0c;其初始值为0

---

4层次遍历

层次遍历的思路和先序遍历、中序遍历、后序遍历的方式都不一样&＃xff0c;它是按照层级的方式来进行遍历的。

先遍历第一层的所有结点&＃xff0c;再遍历第二层的所有结点&＃xff0c;依次类推进行遍历。要进行层次遍历&＃xff0c;需要借助一个队列。层次遍历的算法过程可以概括为&＃xff1a;➤先将二叉树根结点入队&＃xff0c;➤然后出队&＃xff0c;访问该出队结点&＃xff0c;➤若它有左子树&＃xff0c;则将左子树根结点入队&＃xff0c;➤若它有右子树&＃xff0c;则将右子树根结点入队&＃xff0c;➤然后出队&＃xff0c;访问出队结点......➤如此反复&＃xff0c;直到队列为空。

void LevelOrder(BiTree T){ InitQueue(Q); //初始化辅助队列 BiTree p; //p是遍历指针 EnQueue(Q,T); //将根结点入队 while(!isEmpty(Q)) //队列不为空时&＃xff0c;循环 { DeQueue(Q,p); //对头元素出队 visit(p); //访问当前p所指向结点 if(p->lchild !&＃61; NULL) EnQueue(Q,p->lchild); //若左子树不为空&＃xff0c;则左子树入队 if(p->rchild !&＃61; NULL) EnQueue(Q,p->rchild); //若右子树不为空&＃xff0c;则右子树入队 } }

提示&＃xff1a;层序遍历序列的第一个结点是根结点

---

 例题1   采用先序遍历递归算法查找值为x的节点。找到后返回其指针&＃xff0c;否则返回NULL。

➤查找节点FindNode(*b,x)

➤解&＃xff1a;其递归模型如下&＃xff1a;

BTNode *FindNode(BTNode *b,ElemType x){ BTNode *p; if(b &＃61;&＃61; NULL) return NULL; else if(b->data &＃61;&＃61; x) return b; else { p &＃61; FindNode(b->lchild,x); if(p!&＃61;NULL) return p; else return FindNode(b->rchild,x); }}

---

 例题2   假设二叉树采用二叉链存储结构&＃xff0c;设计一个算法输出值为x的结点的所有祖先。

➤解&＃xff1a;根据二叉树的中祖先的定义可知&＃xff1a;若结点p的左孩子或右孩子是结点q,则结点p是结点q的祖先&＃xff1b;若结点p的左孩子或右孩子是q结点的祖先&＃xff0c;则结点p也是结点q的祖先。➤设f(b,x)表示结点b是否为值是x的结点的祖先。若结点b是值为x的结点的祖先&＃xff0c;f(b,x)返回true;否则返回false。当f(b,x)为true时&＃xff0c;输出结点b的值。求值为x的结点的所有祖先的递归模型如下&＃xff1a;

bool ancestor(BTNode *b, ElemType x){ if(b &＃61;&＃61; NULL) return false; else if(b->lchild !&＃61;NULL && b->lchild->data &＃61;&＃61; x || b->rchild !&＃61;NULL && B->rchild->data &＃61;&＃61; x) { printf("%c",b->data); return true; } else if(ancestor(b->lchild,x) || ancestor(b->rchild,x)) { printf("%c",b->data); return true; } else return false; }

---

例题3   假设二叉树采用二叉链存储结构存储&＃xff0c;设计一个算法&＃xff0c;求先序遍历序列中第k(1≦k≦二叉树中结点个数)个结点的值。➤解:用一个全局变量n(初值为1)保存先序遍历时访问节点的序号。当二叉树b为空时返回特殊字符‘ ’ (‘ &＃39;为空格字符)&＃xff0c;当k&＃61;&＃61;n时表示找到了满足条件的节点&＃xff0c;返回b->data;当k≠n时&＃xff0c;在左子树中查找&＃xff0c;若找到了返回该值&＃xff0c;否则在右子树中查找&＃xff0c;并返回其结果。➤对应的递归模型如下:

//递归算法代码如下&＃xff1a;int n &＃61; 1; //全局变量 ElemType PreNode(BTNode *b, int k) //先序遍历第k个结点值的递归算法 { ElemType ch; if(b &＃61;&＃61; NULL) return &＃39; &＃39;; if(n &＃61;&＃61; k) return b->data; ch &＃61; PreNode(b->lchild,k); //遍历左子树 if(ch !&＃61; &＃39; &＃39;) return ch; //在左子树中找到返回 ch &＃61; PreNode(b->rchild,k); //遍历右子树 return ch; //遍历右子树的结构 } //非递归算法如下&＃xff1a;ElemType PreNode(BTNode *b, int k) //先序遍历第k个结点值的非递归算法 { BTNode *St[MaxSize], *p; int top &＃61; -1; n &＃61; 0; if(b !&＃61; NULL) { top&＃43;&＃43;; //根结点进栈 St[top] &＃61; b; while(top > -1) //栈不为空时循环 { p &＃61; St[top]; //退栈并访问该结点 top--; n&＃43;&＃43;; if(n &＃61;&＃61; k) return p->data; if(p->lchild !&＃61; NULL) //左孩子结点进栈 { top&＃43;&＃43;; St[top] &＃61; p->lchild; } if(p->rchild !&＃61; NULL) //右孩子结点进栈 { top&＃43;&＃43;; St[top] &＃61; p->rchild; } } } return &＃39; &＃39;;}

真题回顾

习题1假设二叉树采用二叉链存储结构存储&＃xff0c;设计一个算法&＃xff0c;求中序遍历序列中第k(1≦k≦二叉树中结点个数)个结点的值。➤①请写出中序遍历的递归算法&＃xff1a;➤②请写出中序遍历的非递归算法&＃xff1a;提示&＃xff1a;本题对应的解题方法和例题3类似&＃xff0c;只是把先序遍历换成中序遍历&＃xff0c;套用中序递归遍历的模型。 习题2 设二叉树T采用二叉链表存储方式&＃xff0c;根结点用T指针指示&＃xff0c;设计一个算法&＃xff0c;求指针p所指结点的双亲结点。提示&＃xff1a;先把例题2学会&＃xff0c;本题的解题思路和方法可以按照例题2的思路习题3假设二叉树采用二叉链存储结构&＃xff0c;设计一个算法把树b的左右子树进行交换。要求算法的空间复杂度为O(1).➤趣闻&＃xff1a;据说这是一道谷歌的算法面试题目

 往期推荐 

?链表递归题型大解密&＃xff0c;这类题还学不会算我输&＃xff01;

?带你搞定考研二叉树算法(上)