二叉树线索化

落日映苍穹つ 2022-07-21 00:16 139阅读 0赞

#pragma once
    
    enum PointerTag { THREAD, LINK };
    
    template <class T>
    struct BinaryTreeNodeThd
    {
    	T _data;                         // 数据
    	BinaryTreeNodeThd<T >* _left;	  // 左孩子
    	BinaryTreeNodeThd<T >* _right;	  // 右孩子
    	PointerTag   _leftTag;            // 左孩子线索标志
    	PointerTag   _rightTag;           // 右孩子线索标志
    
    	BinaryTreeNodeThd(const T& x)
    		:_data(x)
    		, _left(NULL)
    		, _right(NULL)
    		, _leftTag(LINK)
    		, _rightTag(LINK)
    	{}
    };
    
    template<class T>
    class BinaryTreeThd
    {
    	typedef BinaryTreeNodeThd<T> Node;
    public:
    	BinaryTreeThd(const T* a, size_t size, const T& invalid)
    	{
    		size_t index = 0;
    		_root = _CreateTree(a, size, index, invalid);
    	}
    
    	void InOrderThreading()
    	{
    		Node* prev = NULL;
    		_InOrderThreading(_root, prev);
    	}
    
    	void PrevOrderThreading()
    	{
    		Node* prev = NULL;
    		_PrevOrderThreading(_root, prev);
    	}
    
    	void PostOrderThreading();
    
    	void InOrderThd()//中序线索化打印
    	{
    		Node* cur = _root;
    		while (cur)
    		{//1.找最左节点
    			while (cur->_leftTag == LINK)//Link-连接类型
    			{
    				cur = cur->_left;
    			}
    			cout << cur->_data << " ";
    			// 访问连续的后继
    			while (cur->_rightTag == THREAD)
    			{
    				cur = cur->_right;
    				cout << cur->_data << " ";
    			}
    
    			// 访问右子树
    			cur = cur->_right;
    		}
    
    		cout << endl;
    	}
    
    	//void PrevOrderThd()
    	//{
    	//	Node* cur = _root;
    	//	while(cur)
    	//	{
    	//		while (cur->_leftTag == LINK)
    	//		{
    	//			cout<<cur->_data<<" ";
    	//			cur = cur->_left;
    	//		}
    
    	//		cout<<cur->_data<<" ";
    
    	//		/*while(cur->_rightTag == THREAD)
    	//		{
    	//			cur = cur->_right;
    	//			cout<<cur->_data<<" ";
    	//		}
    	//		cur = cur->_right;*/
    	//		cur = cur->_right;
    	//	}
    	//	cout<<endl;
    	//}
    
    	void PrevOrderThd()
    	{
    		Node* cur = _root;
    		while (cur)
    		{
    			cout << cur->_data << " ";
    			if (cur->_leftTag == LINK)
    			{
    				cur = cur->_left;
    			}
    			else
    			{
    				cur = cur->_right;
    			}
    		}
    
    		cout << endl;
    	}
    
    protected:
    	//中序线索化
    	void _InOrderThreading(Node* cur, Node*& prev)
    	{
    		if (cur == NULL)
    			return;
    		
    		_InOrderThreading(cur->_left, prev);//先递归到最左
    		if (cur->_left == NULL)//如果左为空，则将cur的左的标志改变
    		{
    			cur->_leftTag = THREAD;//
    			cur->_left = prev;//左边变为prev，因为是中序遍历，左根右
    		}
    		//第一次线索化prev不存在为空，不进入
    		if (prev && prev->_right == NULL)
    		{
    			prev->_rightTag = THREAD;//第一次为prev为3
    			prev->_right = cur;//3的右指向2
    		}
    		prev = cur;//将cur变为prev，所以变成每次递归后前一个的数据变为prev
    		//左边线索化完后，递归线索化右
    		_InOrderThreading(cur->_right, prev);
    	}
    
    	void _PrevOrderThreading(Node* cur, Node*& prev)
    	{
    		if (cur == NULL)
    			return;
    
    		if (cur->_left == NULL)
    		{
    			cur->_leftTag = THREAD;
    			cur->_left = prev;
    		}
    
    		if (prev && prev->_right == NULL)
    		{
    			prev->_rightTag = THREAD;
    			prev->_right = cur;
    		}
    
    		prev = cur;
    
    		if (cur->_leftTag == LINK)
    		{
    			_PrevOrderThreading(cur->_left, prev);
    		}
    
    		if (cur->_rightTag == LINK)
    		{
    			_PrevOrderThreading(cur->_right, prev);
    		}
    	}
    
    	Node* _CreateTree(const T* a, size_t size,
    		size_t& index, const T& invalid)
    	{
    		Node* root = NULL;
    		if (index < size && a[index] != invalid)
    		{
    			root = new Node(a[index]);
    			root->_left = _CreateTree(a, size, ++index, invalid);
    			root->_right = _CreateTree(a, size, ++index, invalid);
    		}
    		return root;
    	}
    
    protected:
    	Node* _root;
    };
    
    void TestThd()
    {
    	int a1[10] = { 1, 2, 3, '#', '#', 4, '#', '#', 5, 6 };
    	int a2[15] = { 1, 2, '#', 3, '#', '#', 4, 5, '#', 6, '#', 7, '#', '#', 8 };
    	BinaryTreeThd<int> t1(a1, 10, '#');
    
    	t1.InOrderThreading();
    	t1.InOrderThd();
    
    	/*t1.PrevOrderThreading();
    	t1.PrevOrderThd();*/
    
    	BinaryTreeThd<int> t2(a2, 15, '#');
    
    	//t2.InOrderThreading();
    	//t2.InOrderThd();
    
    	t2.PrevOrderThreading();
    	t2.PrevOrderThd();
    }