二叉树的层序遍历算法（JS中的二叉树遍历）

本文目录

• JS中的二叉树遍历
• 试完成二叉树按层次（同一层自左至右）遍历的算法
• 2． 已知二叉树的先序遍历序列是EABDCFHGIKJ，中序遍历序列是ABCDEFGHIJK，请构造二叉树，并写出其层次遍
• 以二叉连表做存储结构，试编写按层次顺序遍历二叉树的算法
• 二叉树中的层序遍历
• 《漫画算法》—— 【3】树
• 假设一棵二叉树的按层次遍历序列为abcdefghij,中序遍历序列为dbgehjacif,请画出该树 求方法

JS中的二叉树遍历

栈、队列、链表等数据结构，都是顺序数据结构。而树是非顺序数据结构。树型结构是一类非常重要的非线性结构。直观地，树型结构是以分支关系定义的层次结构。

二叉树（Binary Tree）是另一种树型结构，它的特点是每个结点至多只有两棵子树（即二叉树中不存在度大于2的结点），并且，二叉树的子树有左右之分（其次序不能任意颠倒。）

遍历二叉树(Traversing Binary Tree)：是指按指定的规律对二叉树中的每个结点访问一次且仅访问一次。

二叉树有深度遍历和广度遍历， 深度遍历有前序、 中序和后序三种遍历方法。二叉树的前序遍历可以用来显示目录结构等；中序遍历可以实现表达式树，在编译器底层很有用；后序遍历可以用来实现计算目录内的文件及其信息等。

上述二叉树(a+b*c)-d/e在js中可以用对象的形式表示出来：

先递归遍历左子树，从最左的一个左子树存入数组；然后回溯遍历双亲结点，再是右子树，这样递归循环。

将当前结点压入栈，然后将左子树当做当前结点，如果当前结点为空，将双亲结点取出来，将值保存进数组，然后将右子树当做当前结点，进行循环。

先走左子树，当左子树没有孩子结点时，将此结点的值放入数组中，然后回溯遍历双亲结点的右结点，递归遍历。

广度优先遍历二叉树(层序遍历)是用队列来实现的，广度遍历是从二叉树的根结点开始，自上而下逐层遍历；在同一层中，按照从左到右的顺序对结点逐一访问。

js 中二叉树的深度遍历与广度遍历(递归实现与非递归实现)
二叉树与JavaScript

试完成二叉树按层次（同一层自左至右）遍历的算法

#include "iostream.h"
#include "stdlib.h"
#include "stdio.h"
typedef char ElemType;//定义二叉树结点值的类型为字符型
const int MaxLength=10;//结点个数不超过10个
typedef struct BTNode{
ElemType data;
struct BTNode *lchild,*rchild;
}BTNode,* BiTree;
void CreateBiTree(BiTree &T){//按先序次序输入，构造二叉链表表示的二叉树T，空格表示空树
// if(T) return;
char ch;
ch=getchar(); //不能用cin来输入，在cin中不能识别空格。
if(ch==’ ’) T=NULL;
else{
if(!(T=(BTNode *)malloc(sizeof(BTNode)))) cout《《"malloc fail!";
T-》data=ch;
CreateBiTree(T-》lchild);
CreateBiTree(T-》rchild);
}
}
void PreOrderTraverse(BiTree T){//先序遍历
if(T){
cout《《T-》data《《’ ’;
PreOrderTraverse(T-》lchild);
PreOrderTraverse(T-》rchild);
}
}
void InOrderTraverse(BiTree T){//中序遍历
if(T){
InOrderTraverse(T-》lchild);
cout《《T-》data《《’ ’;
InOrderTraverse(T-》rchild);
}
}
void PostOrderTraverse(BiTree T){//后序遍历
if(T){
PostOrderTraverse(T-》lchild);
PostOrderTraverse(T-》rchild);
cout《《T-》data《《’ ’;
}
}
void LevelOrderTraverse(BiTree T){//层序遍历
BiTree Q;
int front=0,rear=0;
BiTree p;
if(T){ //根结点入队
Q=T;
rear=(rear+1)%MaxLength;
}
while(front!=rear){
p=Q; //队头元素出队
front=(front+1)%MaxLength;
cout《《p-》data《《’ ’;
if(p-》lchild){ //左孩子不为空，入队
Q=p-》lchild;
rear=(rear+1)%MaxLength;
}
if(p-》rchild){ //右孩子不为空，入队
Q=p-》rchild;
rear=(rear+1)%MaxLength;
}
}
}
//非递归的先序遍历算法
void NRPreOrder(BiTree bt)
{ BiTree stack,p;
int top;
if (bt!=NULL){
top=0;p=bt;
while(p!=NULL||top》0)
{ while(p!=NULL)
{
cout《《p-》data;
stack=p;
top++;
p=p-》lchild;
}
if (top》0)
{ top--; p=stack; p=p-》rchild; }
}
}
}
//非递归的中序遍历算法
void NRInOrder(BiTree bt)
{ BiTree stack,p;
int top;
if (bt!=NULL){
top=0;p=bt;
while(p!=NULL||top》0)
{ while(p!=NULL)
{
stack=p;
top++;
p=p-》lchild;
}
if (top》0)
{ top--; p=stack;cout《《p-》data; p=p-》rchild; }
}
}
}
//非递归的后序遍历算法
/*bt是要遍历树的根指针，后序遍历要求在遍历完左右子树后，再访问根。
需要判断根结点的左右子树是否均遍历过。
可采用标记法，结点入栈时，配一个标志tag一同入栈
(1：遍历左子树前的现场保护，2：遍历右子树前的现场保护)。
首先将bt和tag(为1)入栈，遍历左子树；
返回后，修改栈顶tag为2，遍历右子树；最后访问根结点。*/
typedef struct
{
BiTree ptr;
int tag;
}stacknode;
void NRPostOrder(BiTree bt)
{
stacknode s,x;
BiTree p=bt;
int top;
if(bt!=NULL){
top=0;p=bt;
do
{
while (p!=NULL) //遍历左子树
{
s.ptr = p;
s.tag = 1; //标记为左子树
top++;
p=p-》lchild;
}
while (top》0 && s.tag==2)
{
x = s;
p = x.ptr;
cout《《p-》data; //tag为R，表示右子树访问完毕，故访问根结点
}
if (top》0)
{
s.tag =2; //遍历右子树
p=s.ptr-》rchild;
}
}while (top》0);}
}//PostOrderUnrec
int BTDepth(BiTree T){//求二叉树的深度
if(!T) return 0;
else{
int h1=BTDepth(T-》lchild);
int h3=BTDepth(T-》rchild);
if(h1》h3) return h1+1;
else return h3+1;
}
}
int Leaf(BiTree T){//求二叉树的叶子数
if(!T) return 0;
else if(!T-》lchild&&!T-》rchild) return 1;
else return(Leaf(T-》lchild)+Leaf(T-》rchild));
}
int NodeCount(BiTree T){//求二叉树的结点总数
if(!T) return 0;
else return NodeCount(T-》lchild)+NodeCount(T-》rchild)+1;
}
void main(){
BiTree T;
T=NULL;
int select;
//cout《《"请按先序次序输入各结点的值，以空格表示空树(输入时可连续输入):"《《endl;
// CreateBiTree(T);
while(1){
cout《《"\n\n请选择要执行的操作:\n";
cout《《"1.创建二叉树\n";
cout《《"2.二叉树的递归遍历算法（前、中、后）\n";
cout《《"3.二叉树的层次遍历算法\n";
cout《《"4.求二叉树的深度\n";
cout《《"5.求二叉树的叶子结点\n";
cout《《"6.求二叉树的结点总数\n";
cout《《"7.二叉树的非递归遍历算法（前、中、后）\n"; //此项可选做
cout《《"0.退出\n";
cin》》select;
switch(select){
case 0:return;
case 1:
cout《《"请按先序次序输入各结点的值，以空格表示空树(输入时可连续输入):"《《endl;
CreateBiTree(T);
break;
case 2:
if(!T) cout《《"未建立树，请先建树！";
else{
cout《《"\n先序遍历:\n";
PreOrderTraverse(T);
cout《《"\n中序遍历:\n";
InOrderTraverse(T);
cout《《"\n后序遍历:\n";
PostOrderTraverse(T);
}
break;
case 3:
cout《《"\n层序遍历:\n";
LevelOrderTraverse(T);
break;
case 4:
cout《《"二叉树的深度为:\n";
cout《《BTDepth(T);
break;
case 5:
cout《《"\n叶子节点数:\n";
cout《《Leaf(T);
break;
case 6:
cout《《"总节点数:\n";
cout《《NodeCount(T);
break;
case 7:
if(!T) cout《《"未建立树，请先建树！";
else{
cout《《"\n先序遍历:\n";
NRPreOrder(T);
cout《《"\n中序遍历:\n";
NRInOrder(T);
cout《《"\n后序遍历:\n";
NRPostOrder(T);
}
break;
default:
cout《《"请确认选择项:\n";
}//end switch
}//end while
}
参考资料：找来的，你看看吧！

2． 已知二叉树的先序遍历序列是EABDCFHGIKJ，中序遍历序列是ABCDEFGHIJK，请构造二叉树，并写出其层次遍

层次遍历 EAFBHDGICKJ

后序遍历 CDBAGJKIHFE

画法：根E，E左A右F，A右B，B右D，D左C，F右H，H左G右I，I右K，K左J

先看先序，其第一个为树的根，先序遍历是先根再左子树最后右子树，第一个肯定是树的根，先画A，A再中序遍历中左右都有，说明A有左子树也有右子树。

先看左孩子一边，先序下一个为B,故它为根的左孩子，且中序中A在B的前边，所以A为B的左孩子，再看先序中的D，它就是B的右孩子，且中序中C在D的前面，所以C为D的左孩子，根的左枝完事。右边同理。

扩展资料：

除了先序遍历、中序遍历、后序遍历外，还可以对二叉树进行层序遍历。设二叉树的根节点所在层数为1，层序遍历就是从所在二叉树的根节点出发，首先访问第一层的树根节点，然后从左到右访问第2层上的节点，接着是第三层的节点，以此类推，自上而下，自左至右逐层访问树的结点的过程就是层序遍历。

以二叉连表做存储结构，试编写按层次顺序遍历二叉树的算法

//二叉树，按层次访问
//引用如下地址的思想，设计一个算法层序遍历二叉树（同一层从左到右访问）。思想：用一个队列保存被访问的当前节点的左右孩子以实现层序遍历。
***隐藏网址***
typedef struct tagMyBTree
{
int data;
struct tagMyBTree *left,*right;
}MyBTree;
void visitNode(MyBTree *node)
{
if (node)
{
printf("%d ", node-》data);
}

}
void visitBTree(queue《MyBTree*》 q);
void createBTree(MyBTree **tree)
{
int data = 0;
static int initdata = {1,2,4,0,0,5,0,0,3,6,0,0,7,0,0};//构造成满二叉树，利于查看结果
static int i = 0;
//scanf("%d", &data);
data = initdata;
if (data == 0)
{
*tree = NULL;
}
else
{
*tree = (MyBTree*)malloc(sizeof(MyBTree));
if (*tree == NULL)
{
return;
}
(*tree)-》data = data;

createBTree(&(*tree)-》left);

createBTree(&(*tree)-》right);

}
}
void visitBTreeTest()
{
queue《MyBTree*》 q;
MyBTree *tree;
createBTree(&tree);
q.push(tree);
visitBTree(q);
}
void visitBTree(queue《MyBTree*》 q)
{
if (!q.empty())
{
MyBTree *t = q.front();
q.pop();
visitNode(t);
if (t-》left)
{
q.push(t-》left);
}
if (t-》right)
{
q.push(t-》right);
}
visitBTree(q);
}
}

二叉树中的层序遍历

层次遍历就是按二叉树的每一层的顺序来遍历，也就是先访问根结果，然后访问第一层，接着访问第二层...
38题应选:B。大致是先从层次上看出二叉树的根结点为然后从中序中可以看出DBA为左边的结点，CE为右边的结点。然后结合两个可以发现D、E分别是第二层的左右子结点。而B，A则分别为第三层第四层的右结点，C是第三层上的左结点。

《漫画算法》—— 【3】树

在树的结构中，树的定义如下。
树（tree）是n（n》=0）个节点的有限集，当n=0时，称为空树。在任意一个非空树中，有如下特点：

1、有且仅有一个特定的称为根的节点。
2、当n》1时，其余节点可分为m(m》0)个互不相交的有限集，每一个集合本身又是一个树，并称为根的子树。

【相关节点】

树的最大层级树，被称为树的高度或深度。

树的每个节点最多有2个孩子节点。
树的一种特殊形式。树的每个节点 最多有2个孩子节点 。

二叉树的两个孩子节点，一个被称为 左孩子 ，一个被称为 右孩子 。这两个孩子节点的顺序是固定的。

二叉树有两种特殊形式：满二叉树、完全二叉树。

满二叉树 ：一个二叉树的所有非叶子节点都存在左右孩子，并且所有叶子节点都在同一层接上。简言之，满二叉树的每一个分支都是满的。

完全二叉树 ：对一个有n个节点的二叉树，按层级顺序编号，则所有节点的编号为从1到n。如果这个树所有节点和同样深度的满二叉树的编号为从1到n的节点位置相同，则这个二叉树为完全二叉树。

一棵树，若为满二叉树，那么一定是完全二叉树。反之，不一定。

在内存中存储 ：

为什么这么设计？可以更方便的定位孩子节点、父节点。
若父节点的下标是parent，那么左孩子节点下标是2 parent+1，右孩子节点下标是2 parent+2。
反之，若左孩子节点下标是leftChild,那么父节点下标是(leftChild - 1)/2。
稀疏二叉树，用数组表示会很浪费空间。

二叉树的应用：查找操作、维持相对顺序。

1、查找

二叉查找树在二叉树的基础上增加了以下几个条件：

如果左子树不为空，则左子树上所有节点的值均小于根节点的值；
如果右子树不为空，则右子树上所有节点的值均大于根节点的值；
左、右子树也都是二叉查找树。

对于一个节点分布相对均衡的二叉查找树来说，如果节点总数是n，那么搜索节点的 时间复杂度都是O(logn) ，和树的深度是一样的。

2、维持相对顺序（插入）

二叉查找树的特性保证了二叉树的有序性，因此还有另外一个名字：二叉排序树。

插入的过程中，可能会出现需要二叉树进行自平衡，例如下图的情况：

如图所示，不只是树的外观看起来怪异，查询节点的时间复杂度也退化成了O(n)。

二叉树的自平衡的方式有很多种，如红黑树、AVL树、树堆等。

二叉树的遍历：
从节点之间位置关系的角度：
* 前序遍历：输出顺序：根节点、左子树、右子树
* 中序遍历：输出顺序：左子树、根节点、右子树
* 后序遍历：输出顺序：左子树、右子树、根节点
* 层序遍历：按照从根节点到叶子节点的层级关系，一层一层横向遍历各个节点。

从更宏观的角度:
* 深度优先遍历(前、中、后序遍历，前中后是相对根节点)
* 广度优先遍历(层序遍历)

二叉堆：本质上是一种完全二叉树。
二叉堆本质上是一种完全二叉树，分为2个类型：

最大堆 ：任何一个父节点的值，都大于或等于它左、右孩子节点的值；
最小堆 ：任何一个父节点的值，都小于或等于它左、右孩子节点的值。
二叉堆的根节点，叫作 堆顶 。最大堆的堆顶是整个堆中最大元素，最小堆的堆顶是整个堆中最小元素。
二叉堆虽然是一个完全二叉树，但它的存储方式并不是链式存储，而是顺序存储，如下图所示：

假设父节点的下标是parent，那么它的左孩子的下标就是 2 * parent + 1 ，右孩子的下标就是 2 * parent + 2 。

二叉堆的3种操作（假设是最小堆）：
1、插入节点：时间复杂度O(logn)
插入节点是通过“上浮”操作完成的：当二叉堆插入节点时，插入位置是完全二叉树的最后一个位置，将该节点与它的父节点进行比较，如果该节点小于它的父节点，那么该与它的父节点交换位置，直到比较到堆顶位置。
2、删除节点：时间复杂度O(logn)
删除节点是通过“下沉”操作完成的：将要删除的节点看作是堆顶，只看该节点及它下面的部分。因为堆顶元素要进行删除，将最后一个节点元素替换堆顶元素，将替换后的元素与它的左、右子树进行比较，如果左、右孩子节点中最小的一个比该节点小，那么该节点“下沉”，直到叶子节点。
3、构建二叉堆：时间复杂度O(n)
构建二叉堆，也就是把一个无序的完全二叉树调整为二叉堆，本质就是让所有非叶子节点一次“下沉”。

优先队列不再遵循先入先出的原则，而是分为两种情况：

最大优先队列 ，无论入队顺序如何，都是当前最大的元素优先出队；
最小优先队列 ，无论入队顺序如何，都是当前最小的元素优先出队。

二叉堆节点的“上浮”和“下沉”的时间复杂度都是O(logn)，所以优先队列入队和出队的时间复杂度也是O(logn)。

***隐藏网址***

假设一棵二叉树的按层次遍历序列为abcdefghij,中序遍历序列为dbgehjacif,请画出该树 求方法

层序遍历为二叉树的根，看中序遍历，a左边的是a的左子树的节点，右边的是右子树节点，看层序，b是a的左子树的根，c是a的右子树的跟（因为c本身就是a的右子树，由第一步可知）依次类推。

一棵空树，或者是具有下列性质的二叉树：

（1）若左子树不空，则左子树上所有结点的值均小于或等于它的根结点的值；

（2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值；

（3）左、右子树也分别为二叉排序树；

扩展资料：

性质1：二叉树的第i层上至多有2i-1（i≥1）个节点

性质2：深度为h的二叉树中至多含有2h-1个节点

性质3：若在任意一棵二叉树中，有n0个叶子节点，有n2个度为2的节点，则必有n0=n2+1

性质4：具有n个节点的完全二叉树深为log2x+1（其中x表示不大于n的最大整数）

性质5：若对一棵有n个节点的完全二叉树进行顺序编号（1≤i≤n）