文档章节

深度优先遍历多叉树结构,输出叶子路径

xnhcx
 xnhcx
发布于 2015/02/08 18:14
字数 840
阅读 4447
收藏 14
点赞 0
评论 2

树结构的深度优先遍历是应用中常见的问题

在实际项目中,多叉树出现的比较普遍,常用来存储类似字典词条的路径信息。

多叉树对于在一个序列中找到前缀匹配的所有路径是可行的选择,例如找到一段文字中所有前缀匹配的词条(中国人民解放军为例,有中,中国,中国人,中国人民,中国人民解放军等匹配词条)。

构造一棵包含所有中文词条的字典树,可以通过深度优先遍历快速解析出这些前缀匹配的词条,树的每一个节点都是一个汉字,尔从根节点出发的路径是存储的中文词条。

以下的代码是一段示例,它的遍历会输出所有的叶子节点。

树结构是一个名为Tree的类型模板,其中存储了TreeData类型的有效数据,使用定义的接口可以存储路径到Tree结构中。

遍历的类型TreeTraverser,使用了一个栈来记录遍历的当前路径,其类型是自定义的TraverStack类型,表示一个节点和它未被遍历的孩子,栈中每个节点未遍历的孩子的序列实现上使用了一个vector序列容器记录,便于回溯的时候访问下一个未访问的孩子节点。

#include<iostream>
#include<stack>
#include<queue>
#include<cassert>
#include<algorithm>
using namespace std;

template<class TreeData>
struct Tree
{
	private:

		static int TreeDataCompare(Tree* op1, Tree* op2)
		{			
			return op1->GetData() - op2->GetData();
		}

	public:
		Tree(TreeData data):
			m_data(data)
		{
		}

	public:
		void AppendChild(Tree* child)
		{
			m_children.push_back(child);

			// sort children trees by treedata
			sort(m_children.begin(), m_children.end(), TreeDataCompare);
		}

		Tree* PutChildByData(TreeData data)
		{
			// data already exists
			for(int i = 0; i < m_children.size(); i++)
				if(data == m_children[i]->GetData())
					return m_children[i];

			// Append new child to children array
			Tree* newChild = new Tree(data);
			AppendChild(newChild);

			return newChild;
		}

		void PutPathByDataArray(const TreeData* szData)
		{
			if (*szData == 0)
				return;

			Tree* child = PutChildByData(*szData);

			child->PutPathByDataArray(szData+1);
		}

	private:
		TreeData m_data;
		vector<Tree*> m_children;

	public:
		int GetChildrenNum()
		{
			return m_children.size();
		}

		Tree* GetChildByIndex(int index)
		{
			return m_children[index];
		}

		TreeData GetData()
		{
			return m_data;
		}

		// Fill children to the specified queue
		virtual void FillQueueWithChildren(queue<Tree*>& queue)
		{
			for(int i = 0; i < m_children.size(); i++)
			{
				if(m_children[i])
					queue.push(m_children[i]);
			}
		}
};


template<class Tree>
class TraverseStack
{
	public:
		TraverseStack(Tree* tree):
			m_tree(tree)
		{
			m_tree->FillQueueWithChildren(m_children);
		}

		Tree* GetNextChild()
		{
			if (m_children.empty())
				return NULL;

			// pop head of the untraversed children queue
			Tree* head = m_children.front();
			m_children.pop();

			return head;
		}

		Tree* GetTree()
		{
			return m_tree;
		}

	private:
		Tree* 			m_tree;
		queue<Tree*> 	m_children;
};


template<class Tree>
class BFSTraverser
{
	public:
		BFSTraverser(Tree* root):m_root(root){}
		virtual ~BFSTraverser(){}

	public:
		typedef TraverseStack<Tree> PATHSTACKITEM;
		typedef vector<PATHSTACKITEM > PATHSTACK;

	public:
		virtual void Traverse()
		{
			m_pathStack.clear();

			// push the root stack item
			PATHSTACKITEM rItem(m_root);
			m_pathStack.push_back(rItem);
			
			while(!m_pathStack.empty())	
			{
				PATHSTACKITEM& top = m_pathStack.back();
				//cout << "Get top = " << top.GetTree()->GetData() << endl;

				Tree* nextChild = top.GetNextChild();
				if (!nextChild)
				{
					// output pathStack
					if(top.GetTree()->GetChildrenNum() == 0)
						OutputStack();

					// go back along the path to parent TraverseStack element
					m_pathStack.pop_back();
					continue;
				}

				assert(nextChild);

				// pre order output root's path
				if(nextChild == top.GetTree()->GetChildByIndex(0))	
					;//OutputStack();

				// push new TraverseStack element to path
				PATHSTACKITEM newStackItem(nextChild);

				// enlonger the current path to the untraversed child
				m_pathStack.push_back(newStackItem);
				continue;
			}
		}		
	
	private:
		void OutputStack()
		{
			for(int i = 1; i < m_pathStack.size(); i++)
			{
				if(i>0)
					;//cout << ",";

				cout << m_pathStack[i].GetTree()->GetData();
			}
			cout << endl;
		}

	private:
		Tree* m_root;
		PATHSTACK m_pathStack;

};


© 著作权归作者所有

共有 人打赏支持
xnhcx

xnhcx

粉丝 2
博文 5
码字总数 4863
作品 1
朝阳
加载中

评论(2)

xnhcx
xnhcx

引用来自“西夏一品堂”的评论

楼主能否再举一个多叉树的应用例子

目前看到的就是词典的构造和词条的查询,其他路径存储和查询遵循一样的规律,比如在搜索框里敲一个词,以它为前缀的一些词条能够查出,相当于是从以汉字为节点的多叉树中查出了查询频率较高的一些路径出来。不知你还能想到其他和前缀查找相关的应用例子否。
西夏一品堂
西夏一品堂
楼主能否再举一个多叉树的应用例子
数据结构分析之二叉树

概述 在分析树形结构之前,先看一下树形结构在整个数据结构中的位置 数据结构 当然,没有图,现在还没有足够的水平去分析图这种太复杂的数据结构,表数据结构包含线性表跟链表,也就是经常说...

wustor
2017/11/06
0
0
树/二叉树(哈夫曼树/红黑树)笔记

1.树是一种常用数据结构,它是非线性结构。 2.树中任一普通节点可以有0或者多个子节点,但只能有一个父节点。 根节点没有父节点,叶子节点没有子节点。 3.二叉树: 1)每个节点最多只能有两个...

6pker
2015/08/14
0
0
数据结构(二)——树结构模型及应用

基于树实现的数据结构,具有两个核心特征: 逻辑结构:数据元素之间具有层次关系; 数据运算:操作方法具有Log级的平均时间复杂度。 因此,树在文件系统、编译器、索引以及查找算法中有很广的...

yhthu
2017/11/11
0
0
二叉树知识点回忆以及整理

二叉树 在计算机科学中,二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”和“右子树”,左子树和右子树同时也是二叉树。二叉树的子树有左右之分,并且次序不能任意颠倒。...

静默加载
2017/10/19
0
0
数据结构之树

数据结构之树 目录: 二叉树的结构 二叉树的性质 二叉树的遍历 二叉树的特例 二叉树典型程序 树是一种编程中常常用到的一种数据结构,它的逻辑是:除了根结点之外每个结点只有一个父结点,根...

花开半夏qb
2016/11/29
0
0
数据结构与算法(3)——树(二叉、二叉搜索树)

前言:题图无关,现在开始来学习学习树相关的知识 前序文章: 数据结构与算法(1)——数组与链表(https://www.jianshu.com/p/7b93b3570875) 数据结构与算法(2)——栈和队列(https://www.ji...

我没有三颗心脏
07/11
0
0
树与二叉表达树

树基础 定义 数的定义 可以使用递归的方法定义:一棵树是一些节点的集合。一棵树由根节点和0~多个非空树(即子树)组成。这些子树中的每一颗根节点都被来自母树跟的一条有向边链接。母树的根...

月见樽
2017/12/12
0
0
回溯算法思想与八皇后问题解的个数

八皇后问题: 在88的国际象棋棋盘上,皇后是威力较大的棋子,它可以攻击到与自己同行、同列以及同一斜线上的棋子,如下图,所有橙色格子上的棋子,都可能会被皇后攻击: 而八皇后问题就是在8...

silenceyawen
03/04
24
0
二叉树-你可能需要知道这些

一直以来,我都很少使用也避免使用到树和图,总觉得它们神秘而又复杂,但是树在一些运算和查找中也不可避免的要使用到,那么今天我们就鼓起勇气来学习下树,争取在被问到和使用时不再那么怂。...

24K男
2017/10/10
0
0
100 行 C 代码终端打印树形结构

原文出处:我的上铺叫路遥 讲究套路之前,先来回答三个问题。 为什么要打印树形结构 树形结构是算法里很常见的一种数据结构,从二叉树到多叉树,还有很多变种。很多涉及到算法的工作,就需要...

我的上铺叫路遥
2017/02/08
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

实现异步有哪些方法

有哪些方法可以实现异步呢? 方式一:java 线程池 示例: @Test public final void test_ThreadPool() throws InterruptedException { ScheduledThreadPoolExecutor scheduledThre......

黄威
32分钟前
0
0
linux服务器修改mtu值优化cpu

一、jumbo frames 相关 1、什么是jumbo frames Jumbo frames 是指比标准Ethernet Frames长的frame,即比1518/1522 bit大的frames,Jumbo frame的大小是每个设备厂商规定的,不属于IEEE标准;...

六库科技
今天
0
0
牛客网刷题

1. 二维数组中的查找(难度:易) 题目描述 在一个二维数组中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入...

大不了敲一辈子代码
今天
0
0
linux系统的任务计划、服务管理

linux任务计划cron 在linux下,有时候要在我们不在的时候执行一项命令,或启动一个脚本,可以使用任务计划cron功能。 任务计划要用crontab命令完成 选项: -u 指定某个用户,不加-u表示当前用...

黄昏残影
昨天
0
0
设计模式:单例模式

单例模式的定义是确保某个类在任何情况下都只有一个实例,并且需要提供一个全局的访问点供调用者访问该实例的一种模式。 实现以上模式基于以下必须遵守的两点: 1.构造方法私有化 2.提供一个...

人觉非常君
昨天
0
0
《Linux Perf Master》Edition 0.4 发布

在线阅读:https://riboseyim.gitbook.io/perf 在线阅读:https://www.gitbook.com/book/riboseyim/linux-perf-master/details 百度网盘【pdf、mobi、ePub】:https://pan.baidu.com/s/1C20T......

RiboseYim
昨天
1
0
conda 换源

https://mirrors.tuna.tsinghua.edu.cn/help/anaconda/ conda config --add channels https://mirrors.tuna.tsinghua.edu.cn/anaconda/pkgs/free/conda config --add channels https://mir......

阿豪boy
昨天
1
0
Confluence 6 安装补丁类文件

Atlassian 支持或者 Atlassian 缺陷修复小组可能针对有一些关键问题会提供补丁来解决这些问题,但是这些问题还没有放到下一个更新版本中。这些问题将会使用 Class 类文件同时在官方 Jira bug...

honeymose
昨天
0
0
非常实用的IDEA插件之总结

1、Alibaba Java Coding Guidelines 经过247天的持续研发,阿里巴巴于10月14日在杭州云栖大会上,正式发布众所期待的《阿里巴巴Java开发规约》扫描插件!该插件由阿里巴巴P3C项目组研发。P3C...

Gibbons
昨天
1
0
Tomcat介绍,安装jdk,安装tomcat,配置Tomcat监听80端口

Tomcat介绍 Tomcat是Apache软件基金会(Apache Software Foundation)的Jakarta项目中的一个核心项目,由Apache、Sun和其他一些公司及个人共同开发而成。 java程序写的网站用tomcat+jdk来运行...

TaoXu
昨天
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部