二叉树的遍历递归算法

⑴ 二叉树的遍历

遍历概念

所谓遍历(Traversal)是指沿着某条搜索路线 依次对树中每个结点均做一次且仅做一次访问 访问结点所做的操作依赖于具体的应用问题 遍历是二叉树上最重要的运算之一 是二叉树上进行其它运算之基础

遍历方案

．遍历方案 从二叉树的递归定义可知 一棵非空的二叉树由根结点及左 右子树这三个基本部分组成 因此 在任一给定结点上 可以按某种次序执行三个操作 （ ）访问结点本身(N) （ ）遍历该结点的左子树(L) （ ）遍历该结点的右子树(R) 以上三种操作有六种执行次序 NLR LNR LRN NRL RNL RLN 注意 前三种次序与后三种次序对称 故只讨论先左后右的前三种次序

．三种遍历的命名 根据访问结点操作发生位置命名 ① NLR 前序遍历(PreorderTraversal亦称(先序遍历))——访问结点的操作发生在遍历其左右子树之前 ② LNR 中序遍历(InorderTraversal)——访问结点的操作发生在遍历其左右子树之中(间) ③ LRN 后序遍历(PostorderTraversal)——访问结点的操作发生在遍历其左右子树之后 注意 由于被访问的结点必是某子树的根 所以N(Node) L(Left subtlee)和R(Right subtree)又可解释为根 根的左子树和根的右子树 NLR LNR和LRN分别又称为先根遍历 中根遍历和后根遍历

遍历算法

．中序遍历的递归算法定义 若二叉树非空 则依次执行如下操作 ( )遍历左子树 ( )访问根结点 ( )遍历右子树

．先序遍历的递归算法定义 若二叉树非空 则依次执行如下操作 ( ) 访问根结点 ( ) 遍历左子树 ( ) 遍历右子树

．后序遍历得递归算法定义 若二叉树非空 则依次执行如下操作 ( )遍历左子树 ( )遍历右子树 ( )访问根结点

．中序遍历的算法实现 用二叉链表做为存储结构 中序遍历算法可描述为 void InOrder(BinTree T) { //算法里①~⑥是为了说明执行过程加入的标号 ① if(T) { // 如果二叉树非空 ② InOrder(T >lchild) ③ printf( ％c T >data) // 访问结点 ④ InOrder(T >rchild); ⑤ } ⑥ } // InOrder

遍历序列

．遍历二叉树的执行踪迹 三种递归遍历算法的搜索路线相同（如下图虚线所示） 具体线路为 从根结点出发 逆时针沿着二叉树外缘移动 对每个结点均途径三次 最后回到根结点 ．遍历序列 （ ） 中序序列 中序遍历二叉树时 对结点的访问次序为中序序列【例】中序遍历上图所示的二叉树时 得到的中序序列为 D B A E C F （ ） 先序序列 先序遍历二叉树时 对结点的访问次序为先序序列【例】先序遍历上图所示的二叉树时 得到的先序序列为 蔽拿衡 A B D C E F （ ） 后序序列 后宏做序遍历二叉树时 对结点的访问次序为后序序列【例】后序遍历上图所示的二叉树时 得到的后序序列为 D B E F C A 注意 （ ） 在搜索路线中 若访问结点均是第一次经过结点时进行的 则是前序遍历 若访问结点均是在第二次(或第三次)经过结点时进行敏羡的 则是中序遍历(或后序遍历) 只要将搜索路线上所有在第一次 第二次和第三次经过的结点分别列表 即可分别得到该二叉树的前序序列 中序序列和后序序列 （ ） 上述三种序列都是线性序列 有且仅有一个开始结点和一个终端结点 其余结点都有且仅有一个前趋结点和一个后继结点 为了区别于树形结构中前趋(即双亲)结点和后继(即孩子)结点的概念 对上述三种线性序列 要在某结点的前趋和后继之前冠以其遍历次序名称 【例】上图所示的二叉树中结点C 其前序前趋结点是D 前序后继结点是E 中序前趋结点是E 中序后继结点是F 后序前趋结点是F 后序后继结点是A 但是就该树的逻辑结构而言 C的前趋结点是A 后继结点是E和F

二叉链表的构造

． 基本思想 基于先序遍历的构造 即以二叉树的先序序列为输入构造 注意 先序序列中必须加入虚结点以示空指针的位置 【例】建立上图所示二叉树 其输入的先序序列是 ABD∮∮CE∮∮F∮∮

⑵ 先序遍历二叉树的递归算法怎样理解（严蔚敏主编）

先序调用的时候，递归函数，先序函数会一直递归，直到t->next为空，即t为叶节点，需要注意的是当t->next 为空时，函数的实参没有传过去，所以t指向叶结点的父节点，更要注意的是，先序调用的递归函数还没执行完，在先序调用的最里层，要执行这个函数的最后一个语句，即先序访问右子树。
在了解递归函数时，要注意函数是一层一层执行的，把没有调用的函数看作哦是第一层，第一次调用的时候，，势必会第二次遇到调用函数，变成第二层，，，，

⑶ 遍历二叉树

遍历方案：
1．遍历方案
从二叉树的递归定义可知，一棵非空的二叉树由根结点及左、右子树这三个基本部分组成。因此，在任一给定结点上，可以按某种次序执行三个操作：
（1）访问结点本身(N)，
（2）遍历该结点的左子树(L)，
（3）遍历该结点的右子树(R)。
以上三种操作有六种执行次序：
NLR、LNR、LRN、NRL、RNL、RLN。
注意：
前三种次序与后三种次序对称，故只讨论先左后右的前三种次序。
2．三种遍历的命名
根据访问结点操作发生位置命名：
① NLR：前序遍历(PreorderTraversal亦称(先序遍历))
——访问结点的操作发生在遍历其左右子树之前。
② LNR：中序遍历(InorderTraversal)
——访问结点的操作发生在遍历其左右子树之中(间)。
③ LRN：后序遍历(PostorderTraversal)
——访问结点的操作发生在遍历其左右子树之后。
注意：
由于被访问的结点必是某子树的根，所以N(Node)、L(Left subtree)和R(Right subtree)又可解释为根、根的左子树和根的右子树。NLR、LNR和LRN分别又称为先根遍历、中根遍历和后根遍历。
遍历算法
1．中序遍历的递归算法定义：
若二叉树非空，则依次执行如下操作：
(1)遍历左子树；
(2)访问根结点；
(3)遍历右子树。
2．先序遍历的递归算法定义：
若二叉树非空，则依次执行如下操作：
(1) 访问根结点；
(2) 遍历左子树；
(3) 遍历右子树。
3．后序遍历得递归算法定义：
若二叉树非空，则依次执行如下操作：
(1)遍历左子树；
(2)遍历右子树；
(3)访问根结点。
4．中序遍历的算法实现
用二叉链表做为存储结构，中序遍历算法可描述为：
void InOrder(BinTree T)
{ //算法里①~⑥是为了说明执行过程加入的标号
① if(T) { // 如果二叉树非空
② InOrder(T->lchild)；
③ printf("％c"，T->data)； // 访问结点
④ InOrder(T->rchild);
⑤ }
⑥ } // InOrder
遍历序列
1．遍历二叉树的执行踪迹
三种递归遍历算法的搜索路线相同（如下图虚线所示）。
具体线路为：
从根结点出发，逆时针沿着二叉树外缘移动，对每个结点均途径三次，最后回到根结点。
2．遍历序列
A
/ \
B C
/ / \
D E F
图
（1） 中序序列（inorder traversal）
中序遍历二叉树时，对结点的访问次序为中序序列
【例】中序遍历上图所示的二叉树时，得到的中序序列为：
D B A E C F
（2） 先序序列（preorder traversal）
先序遍历二叉树时，对结点的访问次序为先序序列
【例】先序遍历上图所示的二叉树时，得到的先序序列为：
A B D C E F
（3） 后序序列（postorder traversal）
后序遍历二叉树时，对结点的访问次序为后序序列
【例】后序遍历上图所示的二叉树时，得到的后序序列为：
D B E F C A
（4）层次遍历（level traversal）二叉树的操作定义为：若二叉树为空，则退出，否则，按照树的结构，从根开始自上而下，自左而右访问每一个结点，从而实现对每一个结点的遍历
注意：
（1）在搜索路线中，若访问结点均是第一次经过结点时进行的，则是前序遍历；若访问结点均是在第二次(或第三次)经过结点时进行的，则是中序遍历(或后序遍历)。只要将搜索路线上所有在第一次、第二次和第三次经过的结点分别列表，即可分别得到该二叉树的前序序列、中序序列和后序序列。
（2）上述三种序列都是线性序列，有且仅有一个开始结点和一个终端结点，其余结点都有且仅有一个前趋结点和一个后继结点。为了区别于树形结构中前趋(即双亲)结点和后继(即孩子)结点的概念，对上述三种线性序列，要在某结点的前趋和后继之前冠以其遍历次序名称。
【例】上图所示的二叉树中结点C，其前序前趋结点是D，前序后继结点是E；中序前趋结点是E，中序后继结点是F；后序前趋结点是F，后序后继结点是A。但是就该树的逻辑结构而言，C的前趋结点是A，后继结点是E和F。
二叉链表的构造
1． 基本思想
基于先序遍历的构造，即以二叉树的先序序列为输入构造。
注意：
先序序列中必须加入虚结点以示空指针的位置。
【例】
建立上图所示二叉树，其输入的先序序列是：ABD∮∮∮CE∮∮F∮∮。
2． 构造算法
假设虚结点输入时以空格字符表示，相应的构造算法为：
void CreateBinTree (BinTree *T)
{ //构造二叉链表。T是指向根指针的指针，故修改*T就修改了实参(根指针)本身
char ch；
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就指向了已构造好的二叉链表的根结点。
二叉树建立过程见http://student.zjzk.cn/course_ware/data_structure/web/flashhtml/erchashujianli.htm
下面是关于二叉树的遍历、查找、删除、更新数据的代码(递归算法):
[code]
#include <iostream>
using namespace std;
typedef int T;
class bst{
struct Node{
T data;
Node* L;
Node* R;
Node(const T& d, Node* lp=NULL, Node* rp=NULL):data(d),L(lp),R(rp){}
};
Node* root;
int num;
public:
bst():root(NULL),num(0){}
void clear(Node* t){
if(t==NULL) return;
clear(t->L);
clear(t->R);
delete t;
}
~bst(){clear(root);}
void clear(){
clear(root);
num = 0;
root = NULL;
}
bool empty(){return root==NULL;}
int size(){return num;}
T getRoot(){
if(empty()) throw "empty tree";
return root->data;
}
void travel(Node* tree){
if(tree==NULL) return;
travel(tree->L);
cout << tree->data << ' ';
travel(tree->R);
}
void travel(){
travel(root);
cout << endl;
}
int height(Node* tree){
if(tree==NULL) return 0;
int lh = height(tree->L);
int rh = height(tree->R);
return 1+(lh>rh?lh:rh);
}
int height(){
return height(root);
}
void insert(Node*& tree, const T& d){
if(tree==NULL)
tree = new Node(d);
else if(ddata)
insert(tree->L, d);
else
insert(tree->R, d);
}
void insert(const T& d){
insert(root, d);
num++;
}
Node*& find(Node*& tree, const T& d){
if(tree==NULL) return tree;
if(tree->data==d) return tree;
if(ddata)
return find(tree->L, d);
else
return find(tree->R, d);
}
bool find(const T& d){
return find(root, d)!=NULL;
}
bool erase(const T& d){
Node*& pt = find(root, d);
if(pt==NULL) return false;
combine(pt->L, pt->R);
Node* p = pt;
pt = pt->R;
delete p;
num--;
return true;
}
void combine(Node* lc, Node*& rc){
if(lc==NULL) return;
if(rc==NULL) rc = lc;
else combine(lc, rc->L);
}
bool update(const T& od, const T& nd){
Node* p = find(root, od);
if(p==NULL) return false;
erase(od);
insert(nd);
return true;
}
};
int main()
{
bst b;
cout << "input some integers:";
for(;;){
int n;
cin >> n;
b.insert(n);
if(cin.peek()=='\n') break;
}
b.travel();
for(;;){
cout << "input data pair:";
int od, nd;
cin >> od >> nd;
if(od==-1&&nd==-1) break;
b.update(od, nd);
b.travel();
}
}
[/code]

⑷ 先序遍历二叉树的递归算法怎样理解

二叉树的结点结构是:
1、根结点（存放结点数据）
2、左子树指针
3、右子树指计
对二叉树的遍历就是访问各个结点中根结点里存放的数据。例如：
如果结点A有左结点B，右结点C，记作A(B,C)，不同结点我用"\"隔开。那么有这样一个(BitTree)二叉树表A(B,C) \B（D,E)\E(F.G)\C(空,H)\H(I.空)， 自己画出来，不然我后面白讲了。
要想把所有的数据都访问到则必需按照一定的原则，即当前结点的下一个结点是哪个结点。
无论是先、中还是后序算法都是先将左结点视为下一个结点，当左结点不存在（即为空时）才将右结点视作下一个结点，如果右结点也不存在就返回当前结点的上层结点再向右访问，如此类推。
于是对二叉树的遍历问题就被抽象成三个基本步骤:
1、访问根结点。
2、访问该点的所有左子树。
3、访问该点的所有右子树。
先序遍历的策略是按123的步骤执行，中序是按213来，后序则是231,它们之间的不同只是“访问根结点”在这三个步骤中的位置。
看着你刚画好的那个BitTree跟着我的思路走。在先序遍历算法PriorOrder中,先将BitTree的头结点A传进来，按步骤123的处理。123是抽象实现，记住所表达的思想，下面是具体实现。为了避免混乱用中文数字记录步骤。
一、即是读取结点A的数据内容A（此时A为当前函数处理结点)，将A的右结点C放入栈S中，S中的内容为S（C）[注意这一步是算法的一个辅助，并不是先向右访问,下同]，将左结点B传给PriorOrder处理。此时读取了A
二、读取B的内容B（此时B为当前结点），将B的右结点E放入S中，S中的内容为S(C,E),将B的左结点D传给PriorOrder处理。此时读取了AB
三、D为当前结点，D的右为空没有东西放入S，S中的内容仍为S(C,E)，D的左也为空，没有访问可访问的。此时就从S中取出E(因为栈是先进后出的所以取的就是E，此时S中的内容为S(C),正好是上一层没访问过的右子树)，将E传给PriorOrder处理。此时读取了AB D
四、E为当前结点，对于结点E类似的有S(C,G),读取了ABDE,将F传入PriorOrder
五、F为当前结点，右为空，左也为空，读取了ABDEF,从栈中取出G传给PriorOrder处理,S的内容为S(C);
六、类似的读取了ABDEFG,从S中取出了C，传给PriorOrder处理。此时S（）。
七、当前结点为C，从将C的右结点放入S，S中内容为S(H),C的左为空，从S取出H，将H传给PriorOrder处理。此时S为S().于是就读取了ABDEFGC
八，类似的读取了ABDEFGCH
九，最后ABDEFGCHF
你再对照的书上的算法想想，画画就应该能明白点。特别要理角的一点是为什么用递归算法时计算机能按这样的方式是因为函数调用是“先调用，后执行完”，或者说“后调用，先执行完”。注意我加一个“完”字