深度优先遍历多叉树结构,输出叶子路径
博客专区 > xnhcx 的博客 > 博客详情
深度优先遍历多叉树结构,输出叶子路径
xnhcx 发表于3年前
深度优先遍历多叉树结构,输出叶子路径
  • 发表于 3年前
  • 阅读 4229
  • 收藏 14
  • 点赞 0
  • 评论 2

【腾讯云】新注册用户域名抢购1元起>>>   

摘要: 树结构的深度优先遍历是应用中常见的问题 在实际项目中,多叉树出现的比较普遍,常用来存储类似字典词条的路径信息。 多叉树对于在一个序列中找到前缀匹配的所有路径是可行的选择,例如找到一段文字中所有前缀匹配的词条(中国人民解放军为例,有中,中国,中国人,中国人民,中国人民解放军等匹配词条)。

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

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

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

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

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

树结构是一个名为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
粉丝 2
博文 5
码字总数 4863
作品 1
评论 (2)
西夏一品堂
楼主能否再举一个多叉树的应用例子
xnhcx

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

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

目前看到的就是词典的构造和词条的查询,其他路径存储和查询遵循一样的规律,比如在搜索框里敲一个词,以它为前缀的一些词条能够查出,相当于是从以汉字为节点的多叉树中查出了查询频率较高的一些路径出来。不知你还能想到其他和前缀查找相关的应用例子否。
×
xnhcx
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: