文档章节

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

xnhcx
 xnhcx
发布于 2015/02/08 18:14
字数 840
阅读 4650
收藏 14

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

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

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

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

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

树结构是一个名为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
数据结构之树

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

花开半夏qb
2016/11/29
0
0
二叉树知识点回忆以及整理

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

静默加载
2017/10/19
0
0

没有更多内容

加载失败,请刷新页面

加载更多

case when then

case具有两种格式。简单case函数和case搜索函数。 --简单case函数case sex when '1' then '男' when '2' then '女’ else '其他' end--case搜索函数case when sex = '1' the...

architect刘源源
17分钟前
0
0
Kubernetes探秘—kubelet的配置参数

kubelet是Kubernetes中的核心组件,需要在每一个节点安装,也是kubernetes集群启动的第一个服务。kubelet的参数存放在多个目录,修改时如果不完整就会导致各种错误,下面我们kubelet的参数存...

openthings
20分钟前
0
0
如何通过 MySQL 的二进制日志恢复数据库数据

经常有网站管理员因为各种原因和操作,导致网站数据误删,而且又没有做网站备份,结果不知所措,甚至给网站运营和盈利带来负面影响。所以本文我们将和大家一起分享学习下如何通过 MySQL 的二...

吴伟祥
29分钟前
1
0
org.apache.catalina.startup.Catalina stopServer SEVERE: Could not contact localhost:8005. Tomcat may

org.apache.catalina.startup.Catalina stopServer SEVERE: Could not contact localhost:8005. Tomcat may 2017年07月21日 14:52:10 子木HAPPY阳VIP 阅读数:14134 标签: tomcatnginx 更多......

linjin200
31分钟前
1
0
线下工坊|Blockchain Coding Day:零基础教你开发DAPP(北京)

我们的目标是通过编程学习让你更了解区块链技术。这将对区块链开发初学者一次很好的体验。这里需要强调一下,编程零基础也能学会。 我们将以小组的形式,由教练带领学员完成DAPP开发。每位学...

HiBlock
今天
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部