遍历二叉树的算法分析（二叉树算法）

本文目录

• 二叉树算法
• 先序遍历二叉树的递归算法怎样理解
• 怎么用递归算法遍历二叉树的前序序列
• 二叉树遍历算法，就是给定两种遍历结果求另一种遍历顺序
• 求c#前中后序遍历二叉树的算法及思想

二叉树算法

二叉树的算法主要分为三种：先序遍历，中序遍历和后序遍历。二叉树（Binary Tree）是n（n》=0）个节点的有限集合，该集合或者空集（称为空二叉树），或者由一个根节点和两棵互不相交的，分别称为根节点的左子树和右子树的二叉树组成。

扩展资料

　　二叉树的每个结点至多只有二棵子树(不存在度大于2的结点)，二叉树的’子树有左右之分，次序不能颠倒。二叉树的第i层至多有2^（i 1）个结点;深度为k的二叉树至多有2^k 1个结点;对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0 = n2 + 1。二叉树算法常被用于实现二叉查找树和二叉堆。

　　概念

　　 语音

　　二叉树是每个节点最多有两个子树的有序树。通常子树被称作“左子树”(left subtree)和“右子树”(right subtree)。二叉树常被用于实现二叉查找树和二叉堆。

　　基本形态：

　　二叉树也是递归定义的，其结点有左右子树之分，逻辑上二叉树算法有五种基本形态：

　　(1)空二叉树——(a)

　　(2)只有一个根结点的二叉树——(b);

　　(3)右子树为空的二叉树——(c);

　　(4)左子树为空的二叉树——(d);

　　(5)完全二叉树——(e)

　　注意：尽管二叉树与树有许多相似之处，但二叉树不是树的特殊情形。

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

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

怎么用递归算法遍历二叉树的前序序列

先序列号为这个，那么在的时候，可以先进行用顺序的方式，然后再进行。

后序序列是CBA。根据前序，可以确定A为根，A在中序中的位置，可以确定CB为A的左子树上的结点，没有右子树。确定A之后，再看中序第二值为B，查看B在中序中的位置，C在B左边，确定C为B的左子树。

扩展资料：

从二叉树的递归定义可知，一棵非空的二叉树由根结点及左、右子树这三个基本部分组成。因此，在任一给定结点上，可以按某种次序执行三个操作：

（1）访问结点本身(N)，

（2）遍历该结点的左子树(L)，

（3）遍历该结点的右子树(R)。

二叉树遍历算法，就是给定两种遍历结果求另一种遍历顺序

假设某二叉树的先序遍历序列是abdgcefh，中序遍历序列是dgbaechf，画出二叉树，并给出其后序遍历序列。
分析过程：

以下面的例题为例进行讲解：

已知一棵二叉树的先序遍历序列和中序遍历序列分别是abdgcefh、dgbaechf，求二叉树及后序遍历序列。

分析：先序遍历序列的第一个字符为根结点。对于中序遍历，根结点在中序遍历序列的中间，左边部分是根结点的左子树的中序遍历序列，右边部分是根结点的右子树的中序遍历序列。
先序：abdgcefh --》 a bdg cefh

中序：dgbaechf --》 dgb a echf

得出结论：a是树根，a有左子树和右子树，左子树有bdg结点，右子树有cefh结点。
先序：bdg --》 b dg

中序：dgb --》 dg b

得出结论：b是左子树的根结点，b无右子树，有左子树。
先序：dg --》 d g

中序：dg --》 d g

得出结论：d是b的左子树的根结点，d无左子树，有右子树。
先序：cefh --》 c e fh

中序：echf --》 e c hf

得出结论：c是右子树的根结点，c有左子树(只有e结点)，有右子树(有fh结点)。
先序：fh --》 f h

中序：hf --》 h f

得出结论：f是c的左子树的根结点，f有左子树(只有h结点)，无右子树。
还原二叉树为：

a

b c

d e f

g h
后序遍历序列：gdbehfca

前序遍历是什么

这个是二叉树里面的一种遍历情况，前序遍历也叫做先根遍历，可记做根左右。

前序遍历首先访问根结点然后遍历左子树，最后遍历右子树。在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。

求c#前中后序遍历二叉树的算法及思想

下面简单介绍一下几种算法和思路：
先序遍历：
1. 访问根结点
2. 按先序遍历左子树;
3. 按先序遍历右子树;
4. 例如：遍历已知二叉树结果为：A-》B-》D-》G-》H-》C-》E-》F
中序遍历：
1. 按中序遍历左子树;
2. 访问根结点;
3. 按中序遍历右子树;
4. 例如遍历已知二叉树的结果：B-》G-》D-》H-》A-》E-》C-》F
后序遍历：
1. 按后序遍历左子树;
2. 按后序遍历右子树;
3. 访问根结点;
4. 例如遍历已知二叉树的结果：G-》H-》D-》B-》E-》F-》C-》A
层次遍历：
1.从上到下,从左到右遍历二叉树的各个结点(实现时需要借辅助容器);
2.例如遍历已知二叉树的结果：A-》B-》C-》D-》E-》F-》G-》H

附加代码：
二叉遍历算法解决方案
using System;
using ********.Generic;
using *****;
namespace structure
{
class Program
{
二叉树结点数据结构的定义#region 二叉树结点数据结构的定义
//二叉树结点数据结构包括数据域,左右结点以及父结点成员;
class nodes《T》
{
T data;
nodes《T》 Lnode, Rnode, Pnode;
public T Data
{
set { data = value; }
get { return data; }
}
public nodes《T》 LNode
{
set { Lnode = value; }
get { return Lnode; }
}
public nodes《T》 RNode
{
set { Rnode = value; }
get { return Rnode; }
}
public nodes《T》 PNode
{
set { Pnode = value; }
get { return Pnode; }
}
public nodes()
{ }
public nodes(T data)
{
***** = data;
}
}
#endregion
#region 先序编历二叉树
static void PreOrder《T》(nodes《T》 rootNode)
{
if (rootNode != null)
{
C********(*****);
PreOrder《T》(*****);
PreOrder《T》(*****);
}
}

#endregion