求设计一个程序,实现树的深度优先与广度优先遍历。急急急!!
发布网友
发布时间：2022-05-02 16:11
共3个回答
懂视网
时间：2022-05-14 18:55
本篇文章给大家带来的内容是关于JavaScript实现DOM树的深度优先遍历和广度优先遍历（代码实例），有一定的参考价值，有需要的朋友可以参考一下，希望对你有所帮助。
深度优先遍历
// 非递归,首次传入的node值为DOM树中的根元素点，即html
// 调用：deep(document.documentElement)
function deep (node) {
var res = []; // 存储访问过的节点
if (node != null) {
var nodeList = []; // 存储需要被访问的节点
nodeList.push(node);
while (nodeList.length > 0) {
var currentNode = nodeList.pop(); // 当前正在被访问的节点
res.push(currentNode);
var childrens = currentNode.children;
for (var i = childrens.length - 1; i >= 0; i--) {
nodeList.push(childrens[i]);
}
}
}
return res;
}
// 使用递归
var res = []; // 存储已经访问过的节点
function deep (node) {
if (node != null) { // 该节点存在
res.push(node);
// 使用childrens变量存储node.children，提升性能，不使用node.children.length，从而不必在for循环遍历时每次都去获取子元素
for (var i = 0, childrens = node.children; i < childrens.length; i++) {
deep(childrens[i]);
}
}
return res;
}广度优先遍历
// 递归
var res = [];
function wide (node) {
if (res.indexOf(node) === -1) {
res.push(node); // 存入根节点
}
var childrens = node.children;
for (var i = 0; i < childrens.length; i++) {
if (childrens[i] != null) {
res.push(childrens[i]); // 存入当前节点的所有子元素
}
}
for (var j = 0; j < childrens.length; j++) {
wide(childrens[j]); // 对每个子元素递归
}
return res;
}
// 非递归
function wide (node) {
var res = [];
var nodeList = []; // 存储需要被访问的节点
nodeList.push(node);
while (nodeList.length > 0) {
var currentNode = nodeList.shift(0);
res.push(currentNode);
for (var i = 0, childrens = currentNode.children; i < childrens.length; i++) {
nodeList.push(childrens[i]);
}
}
return res;
}
热心网友
时间：2022-05-14 16:03
为了方便程序验证，首先构造一个如图所示的二叉树。
源码：
/*************************** 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 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;
}
}
}
}
热心网友
时间：2022-05-14 17:21
