樹廣度遍歷演算法
㈠ 二叉樹廣度優先遍歷
#include<queue>
void bfs(Node*root)
{
queue<Node*> q;
Node* p;
if(root!=NULL)
{
q.push(root);
}
else return;
while(!q.empty())
{
p=q.front();
if(p->LT) q.push(p->LT);
if(p->RT) q.push(p->RT);
cout<<p->data<<endl;
q.pop();
}
}
㈡ 什麼是樹的遍歷java
樹遍歷方法:有先序遍歷、中序遍歷、後序遍歷以及廣度優先遍歷四種遍歷樹的方法
Demo:
publicclassThreeLinkBinTree<E>{
publicstaticclassTreeNode{
Objectdata;
TreeNodeleft;
TreeNoderight;
TreeNodeparent;
publicTreeNode(){
}
publicTreeNode(Objectdata){
this.data=data;
}
publicTreeNode(Objectdata,TreeNodeleft,TreeNoderight,TreeNodeparent){
this.data=data;
this.left=left;
this.right=right;
this.parent=parent;
}
}
privateTreeNoderoot;
//以默認的構造器創建二叉樹
publicThreeLinkBinTree(){
this.root=newTreeNode();
}
//以指定根元素創建二叉樹
publicThreeLinkBinTree(Edata){
this.root=newTreeNode(data);
}
/**
*為指定節點添加子節點
*
*@paramparent需要添加子節點的父節點的索引
*@paramdata新子節點的數據
*@paramisLeft是否為左節點
*@return新增的節點
*/
publicTreeNodeaddNode(TreeNodeparent,Edata,booleanisLeft){
if(parent==null){
thrownewRuntimeException(parent+"節點為null，無法添加子節點");
}
if(isLeft&&parent.left!=null){
thrownewRuntimeException(parent+"節點已有左子節點，無法添加左子節點");
}
if(!isLeft&&parent.right!=null){
thrownewRuntimeException(parent+"節點已有右子節點，無法添加右子節點");
}
TreeNodenewNode=newTreeNode(data);
if(isLeft){
//讓父節點的left引用指向新節點
parent.left=newNode;
}else{
//讓父節點的left引用指向新節點
parent.right=newNode;
}
//讓新節點的parent引用到parent節點
newNode.parent=parent;
returnnewNode;
}
//判斷二叉樹是否為空
publicbooleanempty(){
//根據元素判斷二叉樹是否為空
returnroot.data==null;
}
//返回根節點
publicTreeNoderoot(){
if(empty()){
thrownewRuntimeException("樹為空，無法訪問根節點");
}
returnroot;
}
//返回指定節點（非根節點）的父節點
publicEparent(TreeNodenode){
if(node==null){
thrownewRuntimeException("節點為null，無法訪問其父節點");
}
return(E)node.parent.data;
}
//返回指定節點（非葉子）的左子節點，當左子節點不存在時返回null
publicEleftChild(TreeNodeparent){
if(parent==null){
thrownewRuntimeException(parent+"節點為null，無法添加子節點");
}
returnparent.left==null?null:(E)parent.left.data;
}
//返回指定節點（非葉子）的右子節點，當右子節點不存在時返回null
publicErightChild(TreeNodeparent){
if(parent==null){
thrownewRuntimeException(parent+"節點為null，無法添加子節點");
}
returnparent.right==null?null:(E)parent.right.data;
}
//返回該二叉樹的深度
publicintdeep(){
//獲取該樹的深度
returndeep(root);
}
//這是一個遞歸方法：每一棵子樹的深度為其所有子樹的最大深度+1
privateintdeep(TreeNodenode){
if(node==null){
return0;
}
//沒有子樹
if(node.left==null&&node.right==null){
return1;
}else{
intleftDeep=deep(node.left);
intrightDeep=deep(node.right);
//記錄其所有左、右子樹中較大的深度
intmax=leftDeep>rightDeep?leftDeep:rightDeep;
//返回其左右子樹中較大的深度+1
returnmax+1;
}
}
//實現先序遍歷
//1、訪問根節點
//2、遞歸遍歷左子樹
//3、遞歸遍歷右子樹
publicList<TreeNode>preIterator(){
returnpreIterator(root);
}
privateList<TreeNode>preIterator(TreeNodenode){
List<TreeNode>list=newArrayList<TreeNode>();
//處理根節點
list.add(node);
//遞歸處理左子樹
if(node.left!=null){
list.addAll(preIterator(node.left));
}
//遞歸處理右子樹
if(node.right!=null){
list.addAll(preIterator(node.right));
}
returnlist;
}
//實現中序遍歷
//1、遞歸遍歷左子樹
//2、訪問根節點
//3、遞歸遍歷右子樹
publicList<TreeNode>inIterator(){
returninIterator(root);
}
privateList<TreeNode>inIterator(TreeNodenode){
List<TreeNode>list=newArrayList<TreeNode>();
//遞歸處理左子樹
if(node.left!=null){
list.addAll(inIterator(node.left));
}
//處理根節點
list.add(node);
//遞歸處理右子樹
if(node.right!=null){
list.addAll(inIterator(node.right));
}
returnlist;
}
//實現後序遍歷
//1、遞歸遍歷左子樹
//2、遞歸遍歷右子樹
//3、訪問根節點
publicList<TreeNode>postIterator(){
returnpostIterator(root);
}
privateList<TreeNode>postIterator(TreeNodenode){
List<TreeNode>list=newArrayList<TreeNode>();
//遞歸處理左子樹
if(node.left!=null){
list.addAll(postIterator(node.left));
}
//遞歸處理右子樹
if(node.right!=null){
list.addAll(postIterator(node.right));
}
//處理根節點
list.add(node);
returnlist;
}
//實現廣度優先遍歷
//廣度優先遍歷又稱為按層遍歷，整個遍歷演算法先遍歷二叉樹的第一層（根節點），再遍歷根節點的兩個子節點（第二層），以此類推
publicList<TreeNode>breadthFirst(){
Queue<TreeNode>queue=newArrayDeque<TreeNode>();
List<TreeNode>list=newArrayList<TreeNode>();
if(root!=null){
//將根元素加入「隊列」
queue.offer(root);
}
while(!queue.isEmpty()){
//將該隊列的「隊尾」的元素添加到List中
list.add(queue.peek());
TreeNodep=queue.poll();
//如果左子節點不為null，將它加入「隊列」
if(p.left!=null){
queue.offer(p.left);
}
//如果右子節點不為null，將它加入「隊列」
if(p.right!=null){
queue.offer(p.right);
}
}
returnlist;
}
}
㈢ 圖的矩陣深度和廣度遍歷演算法
圖的遍歷是指從圖中任一給定頂點出發，依次訪問圖中的其餘頂點。如果給定的圖是連通圖，則從圖中的任意一點出發，按照一個指定的順序就可以訪問到圖中的所有頂點，且每個頂點只訪問一次。這個過程稱為圖的遍歷。
圖的遍歷比樹的遍歷復雜的多。樹是一種特殊類型的圖，即無圈（無迴路）連通圖。樹中的任意兩個頂點間都有唯一的路徑相通。在一個頂點被訪問過之後，不可能又沿著另外一條路徑訪問到已被訪問過的結點。而圖中的頂點可能有邊與其他任意頂點相連
。因此在訪問了某個頂點之後，可能沿著另一條邊訪問已被訪問過的頂點。例如圖（a）中的G1，在訪問了V1，V2和V3之後，有可能沿著邊（V3，V1）訪問到V1。為了避免一頂點被多次訪問，可以設立一個集合Visited，用來記錄已被訪問過的頂點。它的初值為空
集。一旦V1被訪問過，即把V1加到集合Visited中。圖的遍厲通常有兩種:圖的深度優先
搜索和圖的廣度優先搜索。
1）圖的深度優先搜索
從圖G=（V，E）的一個頂點V0出發，在訪問了任意一個與V0相鄰且未被訪問過的頂點W1之後，再從W1出發，訪問和W1相鄰且未被訪問過的頂點W2，然後再從W2出發進行如上所述訪問，直到找到一個它相鄰的結點，都被訪問過的結點為止。然後退回到尚有相
鄰結點未被訪問過的頂點，再從該頂點出發，重復上述搜索過程，直到所有被訪問過的頂點的鄰接點都被訪問過為止。圖的這種遍歷過程就稱為圖的深度優先搜索。例如從頂點V1出發對圖3.3.5進行深度優先搜索，遍歷的順序為 V1,V2,V5,V10,V6,V7,V3,V12,V1
1,V8,V4,V9。（與鄰接表中的鄰接點排列順序有關，即p->next.vertex=v2 or v3對遍歷
順序有影響 ）
例25.(p194.c)圖的深度優先搜索。從圖G的頂點V0
發進行深度優先搜索，列印出各個頂點的遍歷順序。
解：圖的深度優先搜索法為：
（1）首先訪問V0並把V0加到集合visited中；
（2）找到與V0相鄰的頂點W，若W未進入
visited中，則以深度優先方法從W開始搜索。
（3）重復過程（2）直到所有於V0相鄰的頂點
都被訪問過為止。
下面是對用鄰接表表示的圖G進行深度優先搜索的程序
int rear=0; /*Visit和rear都為全局變數*/
int visit[500];
depth_first_search(g,v0) /*從V0開始對圖G進行深度
優先搜索*/
graphptr g[ ]; /*指針數組,為鄰接表表頭頂點指針
g[vi]...g[vn]*/
int v0; /*這里V0和W都是頂點標號,如V0=0或1*/
{ /*g[v0]是頂點V0的表頭指針*/
int w;
graphptr p; /*鏈表的結點指針*/
visit [++rear]=v0;
printf("%d\n",v0);
p=g[v0];/*指定一個頂點，通過鄰接表表頭指針
，訪問v0的鄰接頂點*/
while (p!=NULL)
{
w=p->vertex ;/*這里W是與V0相鄰的一個頂點*/
if (!visited(w))/*當V0的相鄰結點，W未被訪問時，從W開始遍厲*/
depth_first_search(g,w);
p=p->next;/*接著訪問另一個相鄰頂點*/
}
}
int visited(w) /*檢查頂點w是否進入visited(w)*/
int w ;
{
int i;
for (i=1;i<=rear;i++)
if (visit [ i ] == w) return(1);/*W在visit[]中，說明被訪問過*/
return(0); /*W不在visit[]中，說明未被訪問過，返回0*/
}
2）圖的廣度優先搜索
從圖G的一個頂點V0出發，依次訪問V0的鄰接點K1,K2...Kn。然後再順序訪問K1,K2...Kn的所有尚未被訪問過的鄰接點。如此重復，直到圖中的頂點都被訪問過為止。圖的這種搜索稱為圖的廣度優先搜索。例如：從V1出發按廣度優先搜索方法遍歷圖3.3.5,頂
點的訪問順序為V1,V2,V3,V4,V5,V6,V7,V8,V9,V10,V11,V12。
圖的廣度優先搜索類似樹的按層次遍歷，需要有一個隊列來存放還沒
有來得及處理的頂點。圖的廣度優先搜索演算法為：
（1）首先把V0放入隊列；
（2）若隊列為空則結束，否則取出隊列的頭V；
（3）訪問V並把所有與V相鄰且未被訪問的頂點插入隊列；
（4）重復（2）-（3）直到隊列為空。
上述演算法中所有已被訪問過的頂點都放在隊列中，因此只要檢查某個頂點是否在隊列中就可以判斷出該頂點是否已被訪問過。
廣度搜索法的程序如下：
broad_first_search(g,v0) /*從V0開始對圖g進行廣度優先搜索*/
graphptr g[ ]; /*為鄰接表，表頭頂點指針*/
int v0;
{
int queue[500],front =1, tail=1,v;
graphptr p;
queue [tail]=v0; /*把V0插入隊列queue*/
while (front <=tail)/*當隊列不為空*/
{
v=queue[front++]; /*取出隊列中的頂點*/
printf("%d\n",v); /*訪問該頂點*/
p=g[v]; /*從頂點V的鏈表來考慮與V相鄰的頂點*/
while (p!=NULL)
{
v=p->vertex; /*從第一個結點（即邊）中找出相鄰的頂點*/
if (!visited(queue,tail,v))/*判斷頂點是否進入隊列，如進入隊列
說明已被訪問或將要訪問*/
queue[++tail]=v;/*如果該頂點未被訪問過，將此相鄰頂點插入隊列*/
p=p-->next;/*再考慮該結點的下一個相鄰頂點*/
}
}
}
visited (q,tail,v)/*判斷頂點是否被訪問過，訪問過時，返回1，否則返回0*/
int q[ ],tail,v;/*進入隊列的頂點，在front之前的頂點已被訪問過列印輸出，
在front和tail之間的頂點是即將要訪問頂點*/
{
int i;
for(i=1;i<=tail;i++)/*掃描隊列，確定v是否在隊列中，在隊列中返回1，否則返回0*
/
if (q[i]==v)return(1);/*隊列中的頂點都認為已被訪問過*/
return(0);
}
深度優先的非遞歸演算法
/*設當前圖(或圖的某個連通分枝)的起始訪問點為p*/
NodeType stackMain,stackSec
visit(p)
p->mark=true;
do
{
for(all v isTheConnectNode of (G,p))//將當前點的鄰接點中的所有結點壓入副棧中
if(v.marked==false)
statckSec.push(v)
//將副棧中的點依次彈出，壓入主棧中，這與非遞歸演算法中使用隊列的意圖類似
while(!stackSec.isEmpty())
stackMain.push(statckSec.pop());
do//找出下一個未訪問的結點或者沒找到，直到棧為空
{
if(!stackMain.isEmpty())
{
p=stackMain.pop();
}
}while(p.marked==true&&!stackMain.isEmpty())
if(p.marked==false)//訪問未訪問結點.
{
visit(p);
p.marked=true;
}
}while(!stackMain.isEmpty())
㈣ 試分別畫出自頂點1出發進行遍歷所得的深度優先生成樹和廣度優先生成樹。
從1開始，1連接7,7連接3，3連接4,4連接5,5連接6,6連接2（1已經連過了）（2連接了3,7，但是3和7都已經連過，所以回到上一級6,6的連接是1,2都已經連過，所以再回到上一級5）5連接10 。
（10連接1,6都已經連過了，所以回到上一級5，但是5的所有連接點都連過了，所以回到上一級4）4連接9,（9連接5,10都已經連過了，所以回到上一級4,4也已經練完了，所以再回到上一級3）3連接8，至此連完。
廣度遍歷：從1開始，連接7和9，下一個是7，連接3和10 ，下一個是9，連接5，下一個是3，連接4和8，下一個是10 連接6，下一個是5，沒有什麼連接的，下一個是4，沒有什麼連接的，下一個是8，沒有什麼連接的，下一個是6，連接2，至此連完。
(4)樹廣度遍歷演算法擴展閱讀：
通用定義：
若從圖的某頂點出發，可以系統地訪問到圖中所有頂點，則遍歷時經過的邊和圖的所有頂點所構成的子圖，稱作該圖的生成樹。
（1）若G是強連通的有向圖，則從其中任一頂點v出發，都可以訪問遍G中的所有頂點，從而得到以v為根的生成樹。
（2）若G是有根的有向圖，設根為v，則從根v出發可以完成對G的遍歷，得到G的以v為根的生成樹。
（3）若G是非連通的無向圖，則要若干次從外部調用DFS(或BFS)演算法，才能完成對G的遍歷。每一次外部調用，只能訪問到G的一個連通分量的頂點集，這些頂點和遍歷時所經過的邊構成了該連通分量的一棵DFS(或BPS)生成樹。
G的各個連通分量的DFS(或BFS)生成樹組成了G的DFS(或BFS)生成森林。
（4）若G是非強連通的有向圖，且源點又不是有向圖的根，則遍歷時一般也只能得到該有向圖的生成森林。
㈤ 名詞解釋 深度遍歷 廣度遍歷 完全二叉樹
深度遍歷就是從根開始，逐個往下找，知道找不到了，就退回來，繼續往下找。結束的標志是全部都找了一遍。
廣度遍歷，從根開始，遍歷一下和根相連的所有節點，遍歷完畢之後，再遍歷其中一個節點的所有鄰居節點。就像是畫波浪一樣，一層層的。
完全二叉樹，除葉子節點之外每一個中間節點又兩個兒子。
㈥ 關於數據結構的深度優先遍歷和廣度優先遍歷以及最小生成樹 第四大題的第一題
首先看一下深度優先和廣度優先怎麼遍歷：
深度優先遍歷從某個頂點出發，首先訪問這個頂點，然後找出剛訪問這個結點的第一個未被訪問的鄰結點，然後再以此鄰結點為頂點，繼續找它的下一個新的頂點進行訪問，重復此步驟，直到所有結點都被訪問完為止。
廣度優先遍歷從某個頂點出發，首先訪問這個頂點，然後找出這個結點的所有未被訪問的鄰接點，訪問完後再訪問這些結點中第一個鄰接點的所有結點，重復此方法，直到所有結點都被訪問完為止。
在看題目，其要求按順時針方向：
深度優先序列：V1 V2 V3 V5 V4
廣度優先序列：V1 V2 V4 V3 V5
最小生成樹，有兩種方法，prim和kruskal演算法。
這題最小生成樹如下：
[(V4,V5),(V1,V4),(V2,V4),(V5,V3)],其中（V4,V5）表示V4和V5點之間連線。如下圖類似（這里簡單表示一下）。
V1 V2 V3
\ / /
V4----V5
㈦ 求設計一個程序，實現樹的深度優先與廣度優先遍歷。急急急！！
二叉樹的深度優先遍歷的非遞歸的通用做法是採用棧，廣度優先遍歷的非遞歸的通用做法是採用隊列。
為了方便程序驗證，首先構造一個如圖所示的二叉樹。
源碼：
/*************************** bintree.h文件 *****************************/
#ifndef _BINTREE_H
#define _BINTREE_H
template <class T>
class CBintree
{
public:
CBintree();
bool Depth_RF();//先根深度遍歷
bool Depth_RM();//中根深度遍歷
bool WidthFS(); //層次遍歷
protected:
private:
struct TreeNode
{
T va;
TreeNode *plchild;
TreeNode *prchild;
};
TreeNode *m_pBintree;
};
#endif
template <class T>
CBintree<T>::CBintree()
{
m_pBintree = new TreeNode;
TreeNode *pNode2 = new TreeNode;
TreeNode *pNode3 = new TreeNode;
TreeNode *pNode4 = new TreeNode;
TreeNode *pNode5 = new TreeNode;
TreeNode *pNode6 = new TreeNode;
TreeNode *pNode7 = new TreeNode;
m_pBintree->va = (T)1;
m_pBintree->plchild = pNode2;
m_pBintree->prchild = pNode3;
pNode2->va = (T)2;
pNode2->plchild = pNode4;
pNode2->prchild = pNode5;
pNode3->va = (T)3;
pNode3->plchild = NULL;
pNode3->prchild = pNode6;
pNode4->va = (T)4;
pNode4->plchild = NULL;
pNode4->prchild = NULL;
pNode5->va = (T)5;
pNode5->plchild = pNode7;
pNode5->prchild = NULL;
pNode6->va = (T)6;
pNode6->plchild = NULL;
pNode6->prchild = NULL;
pNode7->va = (T)7;
pNode7->plchild = NULL;
pNode7->prchild = NULL;
}
template <class T>
bool CBintree<T>::Depth_RF() //先根深度遍歷
{
cout << "先根遍歷序列:\n";
stack <TreeNode> s;
s.push(*m_pBintree);
while (!s.empty())
{
TreeNode node_s = s.top();
cout << node_s.va << "\n";
s.pop();
if (node_s.prchild != NULL)
{
s.push(*node_s.prchild);
}
if (node_s.plchild != NULL)
{
s.push(*node_s.plchild);
}
}
return true;
}
template <class T>
bool CBintree<T>::Depth_RM() //中根深度遍歷
{
cout << "中根遍歷序列:\n";
stack <TreeNode> s;
TreeNode *pNode = m_pBintree;
while (pNode != NULL || !s.empty())
{
while (pNode != NULL)
{
s.push(*pNode);
pNode = pNode->plchild;
}
if (!s.empty())
{
TreeNode node_s = s.top();
cout << node_s.va << "\n";
s.pop();
pNode = node_s.prchild;
}
}
return true;
}
template <class T>
bool CBintree<T>::WidthFS() //層次遍歷
{
cout << "層次遍歷序列:\n";
queue <TreeNode> q;
q.push(*m_pBintree);
while (!q.empty())
{
TreeNode *pNode = &q.front();
cout << pNode->va << "\n";
if (pNode->plchild != NULL)
{
q.push(*pNode->plchild);
}
if (pNode->prchild != NULL)
{
q.push(*pNode->prchild);
}
q.pop();
}
return true;
}
/************************ main.cpp 文件 ****************************/
#include <iostream>
#include <stack>
#include <queue>
using namespace std;
#include "bintree.h"
int main()
{
CBintree <int> bt;
bt.Depth_RF();
bt.Depth_RM();
bt.WidthFS();
return 0;
}
/***************** 教科書標准演算法及優化演算法（轉）*******************/
1.先序遍歷非遞歸演算法
void PreOrderUnrec(Bitree *t)
{
Stack s;
StackInit(s);
Bitree *p=t;
while (p!=NULL || !StackEmpty(s))
{
while (p!=NULL) //遍歷左子樹
{
visite(p->data);
push(s,p);
p=p->lchild;
}
if (!StackEmpty(s)) //通過下一次循環中的內嵌while實現右子樹遍歷
{
p=pop(s);
p=p->rchild;
}//endif
}//endwhile
}
2.中序遍歷非遞歸演算法
void InOrderUnrec(Bitree *t)
{
Stack s;
StackInit(s);
Bitree *p=t;
while (p!=NULL || !StackEmpty(s))
{
while (p!=NULL) //遍歷左子樹
{
push(s,p);
p=p->lchild;
}
if (!StackEmpty(s))
{
p=pop(s);
visite(p->data); //訪問根結點
p=p->rchild; //通過下一次循環實現右子樹遍歷
}//endif
}//endwhile
}
3.後序遍歷非遞歸演算法
typedef enum{L,R} tagtype;
typedef struct
{
Bitree ptr;
tagtype tag;
}stacknode;
typedef struct
{
stacknode Elem[maxsize];
int top;
}SqStack;
void PostOrderUnrec(Bitree t)
{
SqStack s;
stacknode x;
StackInit(s);
p=t;
do
{
while (p!=null) //遍歷左子樹
{
x.ptr = p;
x.tag = L; //標記為左子樹
push(s,x);
p=p->lchild;
}
while (!StackEmpty(s) && s.Elem[s.top].tag==R)
{
x = pop(s);
p = x.ptr;
visite(p->data); //tag為R，表示右子樹訪問完畢，故訪問根結點
}
if (!StackEmpty(s))
{
s.Elem[s.top].tag =R; //遍歷右子樹
p=s.Elem[s.top].ptr->rchild;
}
}while (!StackEmpty(s));
}//PostOrderUnrec
4.前序最簡潔非遞歸演算法
void PreOrderUnrec(Bitree *t)
{
Bitree *p;
Stack s;
s.push(t);
while (!s.IsEmpty())
{
s.pop(p);
visit(p->data);
if (p->rchild != NULL) s.push(p->rchild);
if (p->lchild != NULL) s.push(p->lchild);
}
}
5.後序演算法之二
void BT_PostOrderNoRec(pTreeT root)
{
stack<treeT *> s;
pTreeT pre=NULL;
while ((NULL != root) || !s.empty())
{
if (NULL != root)
{
s.push(root);
root = root->left;
}
else
{
root = s.top();
if (root->right!=NULL && pre!=root->right){
root=root->right;
}
else{
root=pre=s.top();
visit(root);
s.pop();
root=NULL;
}
}
}
}
㈧ JS樹結構數據的遍歷
title: JS樹結構數據的遍歷
date: 2022-04-14
description: 針對項目中出現樹形結構數據的時候，我們怎樣去操作他
項目中我們會經常出現對樹形結構的遍歷、查找和轉換的場景，比如說DOM樹、族譜、社會機構、組織架構、許可權、菜單、省市區、路由、標簽等等。那針對這些場景和數據，我們又如何去遍歷和操作，有什麼方式或者技巧可以簡化我們的實現思路。下面我們將針對常規出現的場景去總結一下我們的遍歷方式
樹的特點
1、每個節點都只有有限個子節點或無子節點；
2、沒有父節點的節點稱為根節點；
3、每一個非根節點有且只有一個父節點；
4、除了根節點外，每個子節點可以分為多個不相交的子樹；
5、樹裡面沒有環路
下面的圖片表示一顆樹
在下面的JS中我們由多棵樹組成我們的數據
在這數據中我們如何評判數據是否為葉節點（也就是最後一級），我們每個節點都會存在children屬性，如果不存在children屬性或者children不是一個數組或者children為數組且長度為0我們則認為他是一個葉節點
我們針對樹結構的操作離不開遍歷，遍歷的話又分為廣度優先遍歷、深度優先遍歷。其中深度優先遍歷可以通過遞歸和循環的方式實現，而廣度優先遍歷的話是非遞歸的
從上往下對每一層依次訪問，在每一層中，從左往右（也可以從右往左）訪問結點，訪問完一層就進入下一層，直到沒有結點可以訪問為止。即訪問樹結構的第n+1層前必須先訪問完第n層。
簡單的說，BFS是從根節點開始，沿著樹的寬度遍歷樹的節點。如果所有節點均被訪問，則演算法中止。
所以我們的實現思路是，維護一個隊列，隊列的初始值為樹結構根節點組成的列表，重復執行以下步驟直到隊列為空：
取出隊列中的第一個元素，進行訪問相關操作，然後將其後代元素（如果有）全部追加到隊列最後。
深度優先搜索演算法（英語：Depth-First-Search，DFS）是一種用於遍歷或搜索樹或圖的演算法。這個演算法會盡可能深的搜索樹的分支。當節點v的所在邊都己被探尋過，搜索將回溯到發現節點v的那條邊的起始節點。這一過程一直進行到已發現從源節點可達的所有節點為止。如果還存在未被發現的節點，則選擇其中一個作為源節點並重復以上過程，整個進程反復進行直到所有節點都被訪問為止
1、先序遍歷
訪問子樹的時候，先訪問根再訪問根的子樹
2、後序遍歷
訪問子樹的時候，先訪問子樹再訪問根
1、先序遍歷
先序遍歷與廣度優先循環實現類似，要維護一個隊列，不同的是子節點不追加到隊列最後，而是加到隊列最前面
2、後序遍歷
後序遍歷就略微復雜一點，我們需要不斷將子樹擴展到根節點前面去，執行列表遍歷，並且通過一個臨時對象維護一個id列表，當遍歷到某個節點如果它沒有子節點或者它本身已經存在於我們的臨時id列表，則執行訪問操作，否則繼續擴展子節點到當前節點前面
對於樹結構的遍歷操作，其實遞歸是最基礎，也是最容易理解的。遞歸本身就是循環的思想，所以可以用循環來改寫遞歸,以上的方式在項目中已經廊括了大部分的場景了，我們在日常開發中可以根據場景或者需要去選擇我們的遍歷方式，或者基於此對他進行調整和優化，至於每種方式的空間復雜度和時間復雜度我們在這個地方就不去嘗試了，各位感興趣可以自己去驗證。
廣度優先搜索
樹的遍歷
深度優先搜索
圖文詳解兩種演算法：深度優先遍歷（DFS）和廣度優先遍歷（BFS）
二叉樹遍歷（前序，後序，中序，層次）遞歸與迭代實現JavaScript
JS樹結構操作:查找、遍歷、篩選、樹和列表相互轉換
㈨ js廣度遍歷生成樹,樹的定義
先序，後序，中序針對二叉樹。
深度、廣度針對普通樹。深度遍歷：從樹根開始掃描，頂層掃描完了，從一層最左（也可以右）面的結點往下層掃描，直到下層已無結點，這時所有靠最左（右）的結點全部掃描完畢，從樹梢往上退一層，看這層旁有無兄弟結點，有的話還是一樣從最左（右）邊開始掃描，這是個遞歸概念，利用這一方法來遍歷整棵樹。廣度遍歷：從樹根開始掃描，頂層掃描完了，掃描一層的所有結點，掃描二層的所有結點，，掃描最底層的結點。