二叉树遍历的算法实现
2024-05-04 18:43
1. 二叉树遍历的算法实现
从二叉树的递归定义可知，一棵非空的二叉树由根结点及左、右子树这三个基本部分组成。因此，在任一给定结点上，可以按某种次序执行三个操作：⑴访问结点本身（N），⑵遍历该结点的左子树（L），⑶遍历该结点的右子树（R）。以上三种操作有六种执行次序：NLR、LNR、LRN、NRL、RNL、RLN。注意：前三种次序与后三种次序对称，故只讨论先左后右的前三种次序。 根据访问结点操作发生位置命名：① NLR：前序遍历(PreorderTraversal亦称（先序遍历））——访问根结点的操作发生在遍历其左右子树之前。② LNR：中序遍历(InorderTraversal)——访问根结点的操作发生在遍历其左右子树之中（间）。③ LRN：后序遍历(PostorderTraversal)——访问根结点的操作发生在遍历其左右子树之后。注意：由于被访问的结点必是某子树的根，所以N(Node）、L(Left subtree）和R(Right subtree）又可解释为根、根的左子树和根的右子树。NLR、LNR和LRN分别又称为先根遍历、中根遍历和后根遍历。 1．先（根）序遍历的递归算法定义：若二叉树非空，则依次执行如下操作：⑴ 访问根结点；⑵ 遍历左子树；⑶ 遍历右子树。2．中（根）序遍历的递归算法定义：若二叉树非空，则依次执行如下操作：⑴遍历左子树；⑵访问根结点；⑶遍历右子树。3．后（根）序遍历得递归算法定义：若二叉树非空，则依次执行如下操作：⑴遍历左子树；⑵遍历右子树；⑶访问根结点。 用二叉链表做为存储结构，中序遍历算法可描述为：void InOrder(BinTree T){ //算法里①~⑥是为了说明执行过程加入的标号① if(T) { // 如果二叉树非空② InOrder(T->lchild）；③ printf(%c，T->data）； // 访问结点④ InOrder(T->rchild);⑤ }⑥ } // InOrder 计算中序遍历拥有比较简单直观的投影法，如图 ⑴在搜索路线中，若访问结点均是第一次经过结点时进行的，则是前序遍历；若访问结点均是在第二次（或第三次）经过结点时进行的，则是中序遍历（或后序遍历）。只要将搜索路线上所有在第一次、第二次和第三次经过的结点分别列表，即可分别得到该二叉树的前序序列、中序序列和后序序列。⑵上述三种序列都是线性序列，有且仅有一个开始结点和一个终端结点，其余结点都有且仅有一个前驱结点和一个后继结点。为了区别于树形结构中前驱（即双亲）结点和后继（即孩子）结点的概念，对上述三种线性序列，要在某结点的前驱和后继之前冠以其遍历次序名称。【例】上图所示的二叉树中结点C，其前序前驱结点是D，前序后继结点是E；中序前驱结点是E，中序后继结点是F；后序前驱结点是F，后序后继结点是A。但是就该树的逻辑结构而言，C的前驱结点是A，后继结点是E和F。二叉链表基本思想基于先序遍历的构造，即以二叉树的先序序列为输入构造。注意：先序序列中必须加入虚结点以示空指针的位置。【例】建立上图所示二叉树，其输入的先序序列是：ABD∮∮∮CE∮∮F∮∮。构造算法假设虚结点输入时以空格字符表示，相应的构造算法为：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就指向了已构造好的二叉链表的根结点。二叉树建立过程见下面是关于二叉树的遍历、查找、删除、更新数据的代码（递归算法）： #include#include#include#include#include#include#include#include#include#include#include#include#include#include#includeusing 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 data R); } void travel() { travel(root); cout 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 > n; b.insert(n); if(cin.peek()=='\n') break; }for(;;) { cout > od >> nd; if(od==-1&&nd==-1） break; b.update(od,nd); }}
2. 二叉树的三种遍历方法
3. 二叉树遍历问题
1．中序遍历的递归算法定义： 若二叉树非空，则依次执行如下操作： (1)中序遍历左子树； (2)访问根结点； (3)中序遍历右子树。 在遍历子树的时候，依然递归这三个步骤。 2．后序遍历得递归算法定义： 若二叉树非空，则依次执行如下操作： (1)后序遍历左子树； (2)后序遍历右子树； (3)访问根结点。 这些都是递归。 例如，中序遍历，先中序遍历左子树 BDE ,然后访问根节点A，然后是右子树CF。 左子树 中序遍历时，先中序左子树 D，然后是访问左子树的根节点B，然后是右子树E. 同理右子树的遍历 所以结果为 DBEAFC
4. 2叉树遍历
很显然你还不懂的遍历一棵二叉树的原理
当你拿到一棵二叉树，无论它的形状如何的千奇百怪
我们都可以将它按照如下的方式划分
根
/ \
左子树 右子树
一棵有很多个节点的二叉树可以划分为以上的形式
也可以这么理解，只要是按以上形式组合的都可以称为是二叉树
一个仅仅只有根节点的二叉树也可以划分成以上的形式，只不过他的左右子树都为空罢了
所以，我们发现，二叉树的定义其实是一个递归定义的过程
大的二叉树是由小的二叉树构建而成的
所以，当我们考虑要遍历一棵二叉树时
也是首选递归的遍历
遍历二叉树
它的基本思想是先按照上面的形式把整棵二叉树划分为3部分
哪么接下来的工作就很简单了
我们只需要将这3部分都遍历一遍就可以了（这里用到了分而治之的思想）
而对于这3部分来说
根节点的遍历无疑是最方便的，直接访问就ok了
而对于左右子树呢？
我们不难发现，左右子树其实分别成为了两棵完整的树
他们拥有各自独立的根节点，左子树和右子树
对他们的遍历，很显然应该与刚才的遍历方法一致便可
（如果上面的都理解了，那么这个题就是小菜一碟了，如果觉得无法理解，可以按照下面的方法自己多分解几棵树）
对于这个题目，中序遍历这可二叉树
先看根节点
1
/ \
左子树 右子树
我们应该先遍历左子树
也就是下面这棵树
2
/ \
4 5
对于这棵树在进行中序遍历
我们应先遍历她的左子树
他只有一个根节点4，左右子树都为空
哪么遍历这个只有一个根节点的二叉树
先访问她的左子树，为空
返回
访问该树的根节点4
在访问右子树也为空
此时，这棵树已经被完全的遍历了
我们需要返回上一层也就是
2
/ \
4 5
这棵树
此时，她的左子树已经被访问完毕
根据中序遍历的规则
需要访问此树的根节点2
此时的访问顺序是4-2
访问了根节点
在访问右子树只有一个根节点的5（具体过程看4的访问）
5访问完毕
也就意味着
2
/ \
4 5
这棵树已经访问完了
需要返回上一层
也就是1为根的树
此时这棵树的左子树已经访问完毕
此时访问的顺序是4-2-5应该没有问题
接下来访问根节点1
在访问右子树
3
/ \
4 7
是不是觉得似曾相识？？？
她的访问应该跟
2
/ \
4 5
一致
哪么最终遍历的顺序也出来了
4-2-5-1-6-3-7
5. 二叉树的遍历
1．遍历方案 从二叉树的递归定义可知，一棵非空的二叉树由根结点及左、右子树这三个基本部分组成。因此，在任一给定结点上，可以按某种次序执行三个操作： （1）访问结点本身(N)， （2）遍历该结点的左子树(L)， （3）遍历该结点的右子树(R)。以上三种操作有六种执行次序： NLR、LNR、LRN、NRL、RNL、RLN。 注意： 前三种次序与后三种次序对称，故只讨论先左后右的前三种次序。 2．三种遍历的命名 根据访问结点操作发生位置命名： ① NLR：前序遍历(PreorderTraversal亦称(先序遍历)) ——访问结点的操作发生在遍历其左右子树之前。 ② LNR：中序遍历(InorderTraversal) ——访问结点的操作发生在遍历其左右子树之中(间)。 ③ LRN：后序遍历(PostorderTraversal) ——访问结点的操作发生在遍历其左右子树之后。 注意： 由于被访问的结点必是某子树的根，所以N(Node)、L(Left subtlee)和R(Right subtree)又可解释为根、根的左子树和根的右子树。NLR、LNR和LRN分别又称为先根遍历、中根遍历和后根遍历。 遍历算法 1．中序遍历的递归算法定义： 若二叉树非空，则依次执行如下操作： (1)遍历左子树； (2)访问根结点； (3)遍历右子树。 2．先序遍历的递归算法定义： 若二叉树非空，则依次执行如下操作： (1) 访问根结点； (2) 遍历左子树； (3) 遍历右子树。 3．后序遍历得递归算法定义： 若二叉树非空，则依次执行如下操作： (1)遍历左子树； (2)遍历右子树； (3)访问根结点。 ~
6. 二叉树三种遍历技巧
在二叉树的前序遍历，中序遍历，后序遍历这三种遍历方式中，有两个相同的特点就是左子树总是在右子树的之前遍历。还有他们的遍历都可以用递归的方式来描述。 前序遍历的方式是：首先访问根节点，然后访问左子树，最后访问右子树。 中序遍历的方式是：首先访问左子树，接着访问根结点，最后访问右子树。 后序遍历的方式是：首先访问左子树，接着访问右子树，最后访问根结点。
7. 二叉树遍历演示
四、 遍历二叉树 二叉树是一种非线性的数据结构，在对它进行操作时，总是需要逐一对每个数据元素实施 操作，这样就存在一个操作顺序问题，由此提出了二叉树的遍历操作。所谓遍历二叉树就 是按某种顺序访问二叉树中的每个结点一次且仅一次的过程。这里的访问可以是输出、比 较、更新、查看元素内容等等各种操作。
二叉树的遍历方式分为两大类：一类按根、左子树和右子树三个部分进行访问；另一类按 层次访问。下面我们将分别进行讨论。
1、 按根、左子树和右子树三部分进行遍历 遍历二叉树的顺序存在下面6种可能： TLR（根左右）, TRL（根右左） LTR（左根右）, RTL（右根左） LRT（左右根）, RLT（右左根） 其中，TRL、RTL和RLT三种顺序在左右子树之间均是先右子树后左子树，这与人们先左后右的习惯不同，因此，往往不予采用。余下的三种顺序TLR、LTR和LRT根据根访问的位置不同分别被称为先序遍历、中序遍历和后序遍历。（1）先序遍历若二叉树为空，则结束遍历操作；否则访问根结点；先序遍历左子树；先序遍历右子树。（2）中序遍历若二叉树为空，则结束遍历操作；否则中序遍历左子树；访问根结点；中序遍历右子树。（3）后序遍历若二叉树为空，则结束遍历操作；否则后序遍历左子树；后序遍历右子树；访问根结点。例如。以下是一棵二叉树及其经过三种遍历所得到的相应遍历序列二叉树的两种遍历方法：（1）对一棵二叉树中序遍历时，若我们将二叉树严格地按左子树的所有结点位于根结点的左侧，右子树的所有结点位于根右侧的形式绘制，就可以对每个结点做一条垂线，映射到下面的水平线上，由此得到的顺序就是该二叉树的中序遍历序列
（2）任何一棵二叉树都可以将它的外部轮廓用一条线绘制出来，我们将它称为二叉树的包线，这条包线对于理解二叉树的遍历过程很有用。 由此可以看出：（1）遍历操作实际上是将非线性结构线性化的过程，其结果为线性序列，并根据采用的遍历顺序分别称为先序序列、中序序列或后序序列；（2）遍历操作是一个递归的过程，因此，这三种遍历操作的算法可以用递归函数实现。（1）先序遍历递归算法
void PreOrder(BTree BT) {
if (BT) { Visit(BT);
PreOrder(BT->Lchild);
PreOrder(BT->Rchild);
}（2）中序遍历递归算法
void InOrder(BTree BT) {
if (BT) {
InOrder(BT->Lchild);
Visit(BT);
InOrder(BT->Rchild);
}
}（3）后序遍历递归算法
void PostOrder(BTree BT) {
if (BT) {
PostOrder(BT->Lchild);
PostOrder(BT->Rchild);
Visit(BT);
}
} 2 、按层次遍历二叉树 实现方法为从上层到下层，每层中从左侧到右侧依次访问每个结点。下面我们将给出一棵二叉树及其按层次顺序访问其中每个结点的遍历序列。
void LevelOreder(QBTree BT) {
for (i=1;i<=BT.n;i++)
if (BT.elem[i]!='#') Visite(BT.elem[i]);
}二叉树用链式存储结构表示时，按层遍历的算法实现访问过程描述如下：访问根结点，并将该结点记录下来；若记录的所有结点都已处理完毕，则结束遍历操作；否则重复下列操作。取出记录中第一个还没有访问孩子的结点，若它有左孩子，则访问左孩子，并将记录下来；若它有右孩子，则访问右孩子，并记录下来。 在这个算法中，应使用一个队列结构完成这项操作。所谓记录访问结点就是入队操作； 而取出记录的结点就是出队操作。这样一来，我们的算法就可以描述成下列形式：（1）访问根结点，并将根结点入队；（2）当队列不空时，重复下列操作：从队列退出一个结点；若其有左孩子，则访问左孩子，并将其左孩子入队；若其有右孩子，则访问右孩子，并将其右孩子入队；void LevelOrder(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); //处理左孩子 if (!p->Rchild) {Visite(p->Rchild);EnQueue(&Q,p->Rchild); //处理右孩子 }
}
五、典型二叉树的操作算法 1、 输入一个二叉树的先序序列，构造这棵二叉树 为了保证唯一地构造出所希望的二叉树，在键入这棵树的先序序列时，需要在所有空二叉 树的位置上填补一个特殊的字符，比如，'#'。在算法中，需要对每个输入的字符进行判 断，如果对应的字符是'#'，则在相应的位置上构造一棵空二叉树；否则，创建一个新结 点。整个算法结构以先序遍历递归算法为基础，二叉树中结点之间的指针连接是通过指针 参数在递归调用返回时完成。算法：BTree Pre_Create_BT( ) {
getch(ch);
if (ch=='#') return NULL; //构造空树
else { BT=(BTree)malloc(sizeof(BTLinklist)); //构造新结点
BT->data=ch;
BT->lchild =Pre_Create_BT( ); //构造左子树
BT->rchild =Pre_Create_BT( ); //构造右子树
return BT;
}
} 2、 计算一棵二叉树的叶子结点数目 这个操作可以使用三种遍历顺序中的任何一种，只是需要将访问操作变成判断该结点是否 为叶子结点，如果是叶子结点将累加器加1即可。下面这个算法是利用中序遍历实现的。算法：void Leaf(BTree BT,int *count) {
if (BT) {
Leaf(BT->child,&count); //计算左子树的叶子结点个数
if (BT->lchild==NULL&&BT->rchild==NULL) (*count)++;
Leaf(BT->rchild,&count); //计算右子树的叶子结点个数
}
} 3、 交换二叉树的左右子树 许多操作可以利用三种遍历顺序的任何一种，只是某种遍历顺序实现起来更加方便一 些。而有些操作则不然，它只能使用其中的一种或两种遍历顺序。将二叉树中所有结点的左右子树进行交换这个操作就属于这类情况。算法：void change_left_right(BTree BT) {
if (BT) {
change_left_right(BT->lchild);
change_left_right(BT->rchild);
BT->lchildBT->rchild;
}
} 4 、求二叉树的高度 这个操作使用后序遍历比较符合人们求解二叉树高度的思维方式。首先分别求出左右子树 的高度，在此基础上得出该棵树的高度，即左右子树较大的高度值加1。算法：int hight(BTree BT) { //h1和h2分别是以BT为根的左右子树的高度
if (BT==NULL) return 0;
else {
h1=hight(BT->lchild);
h2=hight(BT->right);
return max{h1,h2}+1;
}
} 六、树、森林与二叉树的转换 1、 树、森林转换成二叉树 将一棵树转换成二叉树的方法： 将一棵树转换成二叉树实际上就是将这棵树用孩子兄弟表示法存储即可，此时，树中的每个结点最多有两个指针：一个指针指向第一个孩子，另一个指针指向右侧第一个兄弟。当你将这两个指针看作是二叉树中的左孩子指针和孩子右指针时，就是一棵二叉树了。 特点：一棵树转换成二叉树后，根结点没有右孩子。 将森林转换成二叉树的方法与一棵树转换成二叉树的方法类似，只是把森林中所有树的根 结点看作兄弟关系，并对其中的每棵树依依地进行转换。 2 、二叉树还原成树或森林 这个过程实际上是树、森林转换成二叉树的逆过程，即将该二叉树看作是树或森林的孩子兄弟表示法。比如，若二叉树为空，树也为空；否则，由二叉树的根结点开始，延右指针向下走，直到为空，途经的结点个数是相应森林所含树的棵数；若某个结点的左指针非空，说明这个结点在树中必有孩子，并且从二叉树中该结点左指针所指结点开始，延右指针向下走，直到为空，途经的结点个数就是这个结点的孩子数目。
第 3 节 哈夫曼树及其应用 1、哈夫曼树的定义及特点
在二叉树中，一个结点到另一个结点之间的分支构成这两个结点之间的路径。这三棵二叉树的带权路径长度分别为：WPL1=10*2+11*2+3*3+6*3+7*3+9*3=117WPL2=3*1+6*2+7*3+9*4+10*5+11*5=177WPL3=9*1+7*2+6*3+3*4+10*5+11*5=158哈夫曼树的一个重要特点是：没有度为1的结点。
2、构造哈夫曼树的过程：
（1）将给定的n个权值{w1,w2,...,wn}作为n个根结点的权值构造一个具有n棵二叉树的森林{T1,T2,...,Tn}，其中每棵二叉树只有一个根结点；（2）在森林中选取两棵根结点权值最小的二叉树作为左右子树构造一棵新二叉树，新二叉树的根结点权值为这两棵树根的权值之和；（3）在森林中，将上面选择的这两棵根权值最小的二叉树从森林中删除，并将刚刚新构造的二叉树加入到森林中；（4）重复上面（2）和（3），直到森林中只有一棵二叉树为止。这棵二叉树就是哈夫曼树。 例如： 假设有一组权值{5,29,7,8,14,23,3,11}，下面我们将利用这组权值演示构造哈夫曼树的过程。
它的带权的路径长度为：WPL=(23+29)*2+(11+14)*3+(3+5+7+8)*4=2713．判定树 在很多问题的处理过程中，需要进行大量的条件判断，这些判断结构的设计直接影响着 程序的执行效率。例如，编制一个程序，将百分制转换成五个等级输出。大家可能认为 这个程序很简单，并且很快就可以用下列形式编写出来：if (socre<60) printf("bad");
else if (socre<70) printf("pass");
else if (score<80) printf("general");
else if (score<90) printf("good");
esle printf("very good"); 在实际应用中，往往各个分数段的分布并不是均匀的。下面就是在一次考试中某门课程的各分数段的分布情况：
4．前缀编码 在电文传输中，需要将电文中出现的每个字符进行二进制编码。在设计编码时需要遵守两 个原则：（1）发送方传输的二进制编码，到接收方解码后必须具有唯一性，即解码结果与发送方发送的电文完全一样；（2）发送的二进制编码尽可能地短。下面我们介绍两种编码的方式。
（1）等长编码 这种编码方式的特点是每个字符的编码长度相同（编码长度就是每个编码所含的二进制位 数）。假设字符集只含有4个字符A，B，C，D，用二进制两位表示的编码分别为00，01，10，11。若现在有一段电文为：ABACCDA，则应发送二进制序列：00010010101100，总长度为14位。当接收方接收到这段电文后，将按两位一段进行译码。这种编码的特点是译码简单且具有唯一性，但编码长度并不是最短的。（2）不等长编码 在传送电文时，为了使其二进制位数尽可能地少，可以将每个字符的编码设计为不等长的，使用频度较高的字符分配一个相对比较短的编码，使用频度较低的字符分配一个比较长的编码。例如，可以为A，B，C，D四个字符分别分配0，00，1，01，并可将上述电文用二进制序列：000011010发送，其长度只有9个二进制位，但随之带来了一个问题，接收方接到这段电文后无法进行译码，因为无法断定前面4个0是4个A，1个B、2个A，还是2个B，即译码不唯一，因此这种编码方法不可使用。（1）利用字符集中每个字符的使用频率作为权值构造一个哈夫曼树；（2）从根结点开始，为到每个叶子结点路径上的左分支赋予0，右分支赋予1，并从根到叶子方向形成该叶子结点的编码。假设有一个电文字符集中有8个字符，每个字符的使用频率分别为{0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11}，现以此为例设计哈夫曼编码。
哈夫曼编码设计过程为：
（1）为方便计算，将所有字符的频度乘以100，使其转换成整型数值集合，得到{5,29,7,8,14,23,3,11}；
（2）以此集合中的数值作为叶子结点的权值构造一棵哈夫曼树，如图5-27所示；
（3）由此哈夫曼树生成哈夫曼编码，如图5-28所示。
最后得出每个字符的编码为：比如，发送一段编码：0000011011010010， 接收方可以准确地通过译码得到：⑥⑥⑦⑤②⑧。
8. 二叉树遍历
中序遍历的顺序应该是：4 2 1 7 5 3 6
最新文章
热门文章
推荐阅读