【数据结构】中序线索化二叉树后实现一个迭代器来遍历二叉树

前端之家收集整理的这篇文章主要介绍了【数据结构】中序线索化二叉树后实现一个迭代器来遍历二叉树前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。

1.创建二叉树的结点

#pragma once
#include<iostream>
#include<stack>
using namespace std;
enum PointerTag
{
	THREND,LINK,};
template<class T>
struct BinaryTreeThdNode
{
	typedef BinaryTreeThdNode<T> Node;
	BinaryTreeThdNode(T data)
		:_data(data),_left(NULL),_right(NULL),_father(NULL),_leftTag(LINK),_rightTag(LINK)
	{}
	T _data;
	Node* _left;
	Node* _right;
	Node* _father;     //为后续线索化的遍历设置的父指针,此处可以忽略
	PointerTag _leftTag;
	PointerTag _rightTag;
};

2.创建二叉树

template<class T>
class BinaryTreeThd
{
public:
	typedef BinaryTreeThdNode<T> Node;
	typedef TreeIterator<T,T*,T&> Iterator;
	BinaryTreeThd()
	{}
	BinaryTreeThd(T* arr,size_t size,T invalid)   //非递归创建树

	{
		stack<Node*> s;
		size_t index = 0;
		Node* cur = NULL;
		while (index < size)
		{
			while (index < size && (arr[index] != invalid))
			{
				if (index == 0)   //根节点特殊处理
				{
					cur = new Node(arr[index++]);
					_root = cur;
				}
				else
				{
					cur->_left = new Node(arr[index++]);   //创建左结点
					Node* tmp = cur;
					cur = cur->_left;
					cur->_father = tmp;
				}
				s.push(cur);
			}
			index++;
			Node* top = s.top();
			s.pop();
			if ((index<size)&&(arr[index] != invalid))
			{
				cur = top;
				cur->_right = new Node(arr[index++]);   //创建右节点
				Node* tmp = cur;
				cur = cur->_right;
				cur->_father = tmp;
				s.push(cur);
			}
		}
	}
private:
    Node* _root;
}
/*******************中序线索化递归实现********************/
	void InorderThreading()
	{
		Node* prev = NULL;
		_InorderThreading(_root,prev);
	}
	void _InorderThreading(Node* cur,Node*& prev)
	{
		if (cur == NULL)
			return;
		_InorderThreading(cur->_left,prev);        //递归线索化左子树
		if (cur->_left == NULL)
		{
			cur->_leftTag = THREND;
			cur->_left = prev;
		}
		if (prev && (prev->_right == NULL))
		{
			prev->_rightTag = THREND;
			prev->_right = cur;
		}
		prev = cur;
		_InorderThreading(cur->_right,prev);   //递归线索化右子树

		
	}
/**************中序线索化非递归实现**********************/
void InorderThreading()
	{
		Node* cur = _root;
		Node* prev = NULL;
		stack<Node*> s;
		while (cur || !s.empty())
		{
			while (cur)
			{
				s.push(cur);
				cur = cur->_left;
			}
			Node* top = s.top();
		
			if ((top->_left == NULL))
			{
				top->_left = prev;
				top->_leftTag = THREND;
			}
			
			if (prev&&(prev->_right == NULL))
			{
				prev->_rightTag = THREND;
				prev->_right = top;
			}
			prev = top;
			if (top->_right != NULL)
				cur = top->_right;
			s.pop();
			
		}
	}
3.迭代器部分

template<class T,class Ptr,class Ref>
class TreeIterator
{
public: 
	typedef TreeIterator<T,Ptr,Ref> self;
	typedef TreeIterator<T,T&> Iterator;
	typedef BinaryTreeThdNode<T> Node;
	TreeIterator(Node* p)
		:ptr(p)
	{}
	TreeIterator()
	{}
	self& operator++()
	{
		if (ptr->_rightTag == THREND)
		{
			ptr = ptr->_right;
		}
		else if (ptr->_rightTag == LINK)
		{
			Node* tmp = ptr->_right;
			while (tmp&&tmp->_leftTag == LINK)
			{
				tmp = tmp->_left;
			}
			ptr = tmp;
		}
		return *this;
	}
	bool operator!=(Iterator it)
	{
		return !(ptr == it.ptr);
	}
	Ref operator*()
	{
		return ptr->_data;
	}
private:
	Node* ptr;
};
Iterator Begin()
	{
		Node* cur = _root;
		while (cur->_leftTag)
			cur = cur->_left;
		return Iterator(cur);
	}
	Iterator End()
	{
		Node* cur = _root;
		while (cur!=NULL)
		{
			cur = cur->_right;
		}
		return Iterator(cur);
	}
4.测试
void TestInOrderIter()
{
	int array[10] = { 1,2,3,'#',4,5,6 };
	int array1[15] = { 1,6,7,8 };
	BinaryTreeThd<int> bt(array,10,'#');
	bt.InorderThreading();
	BinaryTreeThd<int>::Iterator it;
	for (it = bt.Begin(); it != bt.End();++it)
	{
		cout << *it << " ";
	}
	cout << endl;
	BinaryTreeThd<int>bt1(array1,15,'#');
	bt1.InorderThreading();
	BinaryTreeThd<int>::Iterator it1;
	for (it1 = bt1.Begin(); it1 != bt1.End(); ++it1)
	{
		cout << *it1 << " ";
	}
	cout << endl;
}
原文链接:https://www.f2er.com/datastructure/382433.html

猜你在找的数据结构相关文章