数据结构二叉树遍历算法

Ⅰ 什么是二叉树数的遍历

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

遍历方案
从二叉树的递归定义可知，一棵非空的二叉树由根结点及左、右子树这三个基本部分组成。因此，在任一给定结点上，可以按某种次序执行三个操作：访问结点本身（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．后（根）序遍历得递归算法定义：
若二叉树非空，则依次执行如下操作：
⑴遍历左子树；
⑵遍历右子树；
⑶访问根结点。

Ⅱ 计算机二级二叉树前序中序后序

二叉树遍历方式是数据结构的基础知识，作为计算贺团机专业的大学生，我的理解如下：

1、 前序遍历

它的遍历顺序是：先访问根结点，再进入这个根结点的左子树；以上述方式遍历完所有左子树后，再进入它的右子树，以同样的方式遍历右子树中的结点，即根结禅大橘点→左子树→右子树。下图中1为主根结点，245为左子树，367为右子树；在左子树中，2为根结点，4为左子树，5为右子树；在右子树中，3为根结点，6为左子树，7为右子树。依次将每个树中的根结点、左子树以及右子树分清，只到子树中只剩一个元素为止。综上可知，结果为1→2→4→5→3→6→7。

例题

前序遍历：A→B→D→F→G→H→I→E→C

中序遍历：F→D→H→G→I→B→E→A→C

后序遍历：F→H→I→G→D→E→B→C→A

Ⅲ 数据结构题目二叉树遍历，哪位大神帮忙解答下，谢谢！

本题考察二叉树的遍历

二叉树的遍历一共有4中

1. 前序遍历
   

2. 中序遍历

3. 后序遍历

4. 层序遍历

略

Ⅳ 如何用二叉树遍历所有可能

关于如何使用二叉树遍历所有可能（即：所有数据节点）的话，那么非常简单：就是在编写程序的时候设计一个数据结构正确的递归子函数，然后使用二卖行叉树算法遍历所有数据节点。
但中此哗是这里要注意的就是：如果想今后使用二叉树（或者是遍历别的数据结构，例如：单链表、双链表、或者是多叉树等），那么在对数据进行存储时，就必须要把将来需要访问遍历的数据保存成相应的数据格式（例如：单链扒旦表、双链表、或者是多叉树等）。否则的话，如果数据格式不匹配的话，那是无法使用相对应的遍历算法进行遍历的。
关于树的各种遍历问题，以根节点位置为标准，包括：前序（根左右）、中序（左根右）、后序（左右根），这个是数据结构上的问题。只要你的数据格式保存正确得当，至于说使用哪一种具体的遍历方式，那么肯定都是可以正确访问的。

Ⅳ 数据结构二叉树遍历问题，遍历方法中右根左(RNL)遍历的方法可以叫中序遍历吗

没冲弊有右根左的遍历，只有三种遍历：
前序遍历（根左右）：
1.访问根节点
2.前序遍历左子树
3.前序遍历右子树肢饥
中序遍历（左根右）：
1.中序遍历左子树
2.访问根节点
3.中序遍历历判返右子树
后序遍历（左右根）：
1.后序遍历左子树
2.后序遍历右子树
3.访问根节点

Ⅵ 中序递归遍历二叉树的算法（数据结构）

有哪位高手帮忙分析下以下程序：#include"iostream.h"
#define
maxnode
100
typedef
char
datatype;
typedef
struct
bitnode{
datatype
data;//存储数据信息的信息域
struct
bitnode
*lchild,*rchild;//左右孩子指针
}bitnode,*bitree;void
createbitree(bitree
*t){//创建一棵已生成左右子树的二叉树的算法char
ch;cin>>ch;if(ch=='0')(*t)=null;else{(*t)=new
bitnode;
(*t)->data=ch;
createbitree(&(*t)->lchild);
createbitree(&(*t)->rchild);}}int
inorderout(bitree
bt)
{//非递归中序遍历二叉树
bitree
stack[maxnode],p;int
top;if(bt==null)
return
1;//空树
top=-1;//栈顶指针初始化p=bt;while(!(p==null&&top==-1))
{
while(p!=null)
{
if(top
lchild;//指针指向p的左孩子结点}if(top==-1)
return
1;//栈空时结束else{p=stack[top];//从栈中弹出栈顶元素
cout<
data;top--;p=p->rchild;//指针指向p的右孩子结点}}}void
main()
//主函数{bitree
bt;int
n;cout<<"
***************二叉树***************"<
>n;switch(n){case
0:break;
case
1:createbitree(&bt);break;case
2:cout<<"中序遍历输出二叉树为：";

Ⅶ 二叉树的遍历算法实现为何要采用递归

树的结构定义本来就是递归思想！

Ⅷ 数据结构二叉树中，如果m是n的祖先,哪种遍历找到m到n的路径

后序遍历。

在后序遍历退回时访问根结点，就可以从下向上把从n到m的路径咐庆上的结点输出出来，如果采用非递归算法。

当后序遍历访问到n时，栈中把从根到n的父指针的路径上的结点都记忆下来，也可以找到从m到n的路径。其他遍历方式都不方便。

二叉树是n个有限元素的集合，该集合或者为空、或者由一个称为根的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成，是有序树。

(8)数据结构二叉树遍历算法扩展阅读：

从根结点开始，假设根结点为第1层，根结点的子节点为第2层，依此类推，如果某一个结点位于第L层，则其子节点位于第L+1层。

按一定的规则和顺序走遍二叉树的所有结点，使每一个结点都被访旁拍问一次，而且只被访问一次。由衡启握于二叉树是非线性结构，因此，树的遍历实质上是将二叉树的各个结点转换成为一个线性序列来表示。

Ⅸ 数据结构与算法-二叉树(Binary Tree)

    名词解释

        节点: 每个元素

        父子关系: 用来连线相邻节点之间的关系

        父节点: A节点就是B节点的父节点

        子节点:  B节点就是A节点的子节点

        兄弟节点: B、C、D这三个节点的父节点是同一个节点

        根结点: 没有父节点的节点

        叶子结点: 没有子节点的节点

        节点的高度: 节点到叶子结点到最长路径(边数)  (计数起点为0, 从下往上)

        节点的深度: 根节点到这个节点经历过的边个数  (计数起点为0, 从上往下)

        节点的层数:     节点到深度 + 1  (计数起点为1)

        树的高度: 根节点的高度

    特点

        最常用的树数据结构

       裂颂 每个节点最多有两个子节点(左子节点、右子节点)

         满二叉树: 叶子节点全都在最底层，除了叶子节点之外，每个节点都有左右两个子节点

         完全二叉树:  叶子节点都在最底下两层，最后一层的叶子节点都 靠左排列 ，并且除了最后一层，其他层的节点个数都要达到最大

        二叉树存储方式

            数组顺序存储法

                通过数组下标来顺序存储数据 (i表示当前节点深度,从0开始)

                根节点: i = 1，左节点:2 * i，右节点: 2 * i + 1，父节点: i / 2

                完全二叉树采用此方式节省内存空间

            链式存储法

                每个节点需要存储三分数据:当前节点数据、左节点指针、右节点指针,比较占用空间                

            遍历

                常用方式

                前序遍历: 树任意节点，先打印当前节点，再打印它的左子树，最后打印它的右子树

                中序遍历: 树任意节点，先打印它的左子树，再打印当前节点，最后打印它的右子树

                后序遍历: 树任意节点，先打印它的左子树，再打印它的右子树，最后打印当前节肆谨郑点

                二叉树的前、中、后序遍历就是一个递归的过程

                时间复杂度是O(n)

                    每个节点最多被访问两次，遍历操作的时间复杂度跟节点的个数n成正比

特点

    二叉查找树为实现快速查找而生，支持快速查找一个数据、快速插入、快速删除一个数据

    特殊结构: 其左子树每个节点的值 < 树的任意一个节点的值 < 其右子树每个节点的值

            先取根节点，如果它等于要查找的数据，那就返回。

            如果要查找的数据比根节点的值小，那就在左子树中递归查找；

            如果要查找的数据比根节点晌悄的值大，那就在右子树中递归查找

            一般插入的数据在叶子节点上，从根节点开始依次比较要插入的数据和节点的大小关系

            如果插入数据比节点的数值大，并且节点的右子树为空，将新数据插到右子节点位置；

            如果不为空，就再递归遍历右子树，查找插入位置。

            如果插入数据比节点的数值小，并且节点的左子树为空，将新数据插到左子节点位置；

            如果不为空，就再递归遍历左子树，查找插入位置。

        针对要删除节点的子节点个数的不同，需分三种情况来处理

        1.如果要删除的节点没有子节点，步骤如下: (如图中的删除节点55)

            只需将父节点中指向要删除节点的指针置为null

        2.如果要删除的节点只有一个子节点，步骤如下: (如图中删除节点13)

            只需将父节点中指向要删除节点的指针，让它指向要删除节点的子节点即可

        3.如果要删除的节点有两个子节点，步骤如下: (如图中的删除节点18)

            首先，需要找到这个节点的右子树中的最小节点，把它替换到要删除的节点上；

            然后，再删除掉这个最小节点，因为最小节点肯定没有左子节点        

            删除操作，有个优化方案: 就是单纯将要删除的节点标记为“已删除”，

            这种方案删除操作就变简单很多，但是比较浪费内存空间

        支持快速地查找最大节点和最小节点、前驱节点和后继节点

        另外一种重要特性: 

            中序遍历二叉查找树，可以输出有序的数据序列，时间复杂度为O(n)

            因此，二叉查找树也叫作二叉排序树

        以上几种操作都默认树中节点存储的都是数字，而且都是不存在键值相同的情况

        实际应用场景中采用对象的某个字段作为键值来构建二叉查找树，其他字段称为卫星数据

        如果存储的两个对象键值相同，两种解决方案

        1.把值相同的数据都存储在同一个节点(采用链表或支持动态扩容的数组等数据结构)   

        2.每个节点只存储一个数据，把这个新插入的数据当作大于这个节点的值来处理，如下图:

        查找操作

            当查找数据时遇到值相同的节点，继续在右子树中查找，直到遇到叶子节点才停止。

            这样就把键值等于要查找值的所有节点都查找出来        

            删除操作

                先查找到每个要删除的节点，然后再按前面讲的删除操作的方法，依次删除

        对于同一组数据可构造不同二叉查找树。查找、插入、删除操作的执行效率都不一样

        图最左边树，根节点的左右子树极度不平衡，退化成链表，查找时间复杂度为O(n)

        最理想的情况，二叉查找树是一棵完全二叉树（或满二叉树）

        时间复杂度都跟树的高度成正比，也就是O(height)

        树的高度就等于最大层数减一，为了方便计算，我们转换成层来表示

        满二叉树: 下一层节点个数是上一层的2倍，第K层包含节点个数就是2^(K-1)

        完全二叉树: 假设最大层数是L，总的节点个数n，它包含的节点个数在1个到2^(L-1)个之间

            L的范围是[ , +1]，完全二叉树的高度小于等于

            极度不平衡的二叉查找树，它的查找性能肯定不能满足我们的需求

        平衡二叉查找树: 树的高度接近logn，时间复杂度较稳定为O(logn)

    1.排序对比

        散列表中的数据是无序存储的，如果要输出有序的数据，需要先进行排序

        二叉查找树只需要中序遍历，就可以在O(n)的时间复杂度内，输出有序的数据序列

    2.性能稳定性对比

        散列表扩容耗时很多，而且当遇到散列冲突时，性能不稳定

        最常用的平衡二叉查找树的性能非常稳定，时间复杂度稳定在O(logn)

    3.时间复杂度对比

        散列表查找等操作时间复杂度是常量级，因存在哈希冲突，这个常量不一定比logn小

        另外加上哈希函数的耗时，也不一定就比平衡二叉查找树的效率高

    4.结构设计对比

        散列表构造比较复杂，需要考虑:散列函数设计、冲突解决办法、扩容、缩容等

        平衡二叉查找树只需要考虑平衡性，而且目前这个的解决方案较成熟、固定

    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 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]