【二叉树线索化】(索引加速 | 标记附加域 | 三叉链表）

目录

介绍

节点定义

预定义辅助函数

中序线索化

先序线索化

后序线索化

中序遍历

先序遍历

后序遍历

---

介绍

线索二叉树：二叉树悬挂节点空指针域指向特定遍历序列的对应前驱和后继

这种处理方法可以加速查找前驱后继的速度

并且非递归遍历不依赖栈的引入，从而非迭代实现

节点定义

#include <cstdio>
#include <cstddef>
#include <cstdlib>
#include <cstdbool>
typedef struct TBTNode{
		struct TBTNode *childs[2];
		mutable int          data;
		int 		  counter {0};
		int 		     size {0};
		_Bool  		tags[2] {0,0};
		
		TBTNode(const struct TBTNode *lchlid = nullptr,
				const struct TBTNode *rchild = nullptr,
				const int givenData)
				:data(givenData){
					childs[0] = lchild;
					childs[1] = rchild;
				}
				
		explicit TBTNode(const TBTNode& other)
			:data(other.data)
			,tags[0](other.tags[0])
			,tags[1](other.tags[1])
		{
			register int i;
			for(i = 0;i < 2;++i)
				childs[i] = other.childs[i] ? new TBTNode( *(other.childs[i]) ) : nullptr;
		}
		explicit TBTNode(TBTNode&& other) noexcept
			:data(other.data)
			,tags[0](other.tags[0])
			,tags[1](other.tags[1])
			,childs[0](other.childs[0])
			,childs[1](other.childs[1])
		{
			other.childs[1] = other.childs[0] = nullptr;
		}
		
		inline leftThreadArgAssign(const struct TBTNode *ptr,const int ltag) noexcept{
			childs[0] = ptr;
			tags[0] = ltag;
		}
		
		inline rightThreadArgAssign(const struct TBTNode *ptr,const int ltag) noexcept{
			childs[1] = ptr;
			tags[1] = ltag;
		}
		
	};

预定义辅助函数

void threaded(TBTNode *cur,TBTNode *pre){
	if( cur->childs[0] ) cur->leftThreadArgAssign( pre,1 );
	if( pre && !pre->childs[1] ) pre->rightThreadArgAssign( cur,1 );
}

inline TBTNode::leftThreadArgAssign(const struct TBTNode *ptr,const int ltag) noexcept{
			childs[0] = ptr;
			tags[0] = ltag;
		}
		
inline TBTNode::rightThreadArgAssign(const struct TBTNode *ptr,const int ltag) noexcept{
			childs[1] = ptr;
			tags[1] = ltag;
		}

中序线索化

void _infixThreaded(TBTNode *cur,TBTNode **pre){
	if( !cur ) return;
	_infixThreaded( cur->childs[0],pre );
	threaded(cur, (*pre) );
	( *pre ) = cur;
	_infixThreaded( cur->childs[1],pre );
}
void infixThreaded(TBTNode *root){
	if( !root ) return;
	TBTNode *pre = nullptr;
	_infixThreaded( root,&pre );
	pre->rightThreadArgAssign( NULL,1 );
}

先序线索化

void _prefixThreaded(TBTNode *cur,TBTNode **pre){
	if( !cur ) return;
	threaded(cur, (*pre) );
	( *pre ) = cur;
	register int i;
	for(i = 0;i < 2;++i)if(cur->tags[i])
		_prefixThreaded( cur->childs[i],pre );
}	
void prefixThreaded(TBTNode *root){
	if( !root ) return;
	TBTNode *pre = nullptr;
	_prefixThreaded( root,&pre );
	pre->rightThreadArgAssign( NULL,1 );
}

后序线索化

void _postThreaded(TBTNode *cur,TBTNode **pre){
	if( !cur ) return;
	_postThreaded( cur->childs[0],pre );
	_postThreaded( cur->childs[1],pre );
	threaded(cur, (*pre) );
	( *pre ) = cur;
}
void postThreaded(TBTNode *root){
	if( !root ) return;
	TBTNode *pre = nullptr;
	_postThreaded( root,&pre );
	pre->rightThreadArgAssign( NULL,1 );
}

中序遍历

inline TBTNode *_first(TBTNode *o){
	while( !o->tags[0] ) o = o->childs[0];
	return p; 
}
inline TBTNode *_next(TBTNode *o){
	return !o->tags[1] ? _first(o->childs[1]) : o->childs[1];
}

void infixOrder( TBTNode *root,void (*visit)(int) ){
	if( !root ) return;
	register TBTNode *p = nullptr;
	for(p = _first(root);p;p = _next(p))visit(p->data);
}

先序遍历

void prefixOrder( TBTNode *root,void (*visit)(int) ){
	if( !root ) return;
	TBTNode *p = nullptr;
	for(p = root; p ;visit( p ),p = p->childs[1])
		do visit( p );while( !p->tags[0] && ( p = p->childs[0] ) );
}

后序遍历

void postOrder( TBTNode *root,void (*visit)(int) ){
	if( !root ) return;
	/* 代码太长  不写了 就正常递归实现就行*/
	
}