【转】线索二叉树创建，遍历

转自： http://blog.csdn.net/cheneagle/article/details/4397750

 

     线索二叉树利用末节点的空指针将其他节点连接起来，达到整个树枝顺序和逆序都能遍历的作用。因为任何一棵n节点的二叉树，它总有n+1个空的指针。比如1个节点二叉树，那么就有2个左右孩子为空指针，同理以此类推。这样就充分利用空间而达到快速遍历的作用。详细请看源代码：

    为了以后快速查找，我还是简单说下怎么输入数据，如下图所示的数据结构：

 

像这样的数据结构我们怎么输入呢？

第一次输入ab#,然后回车。

第二次输入c##,然后回车。

第三次输入d#,然后回车。

第四次输入g##，然后回车。

不知道以后的我或者网友是否看明白呢？希望以后的我和大家领悟能力比我现在这些苍白的文字强n的XX次方！

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <iostream.h>

typedef char DataType;

typedef struct _ThreadBiTreeNode
{
	DataType data;
	int ltag, rtag;
	struct _ThreadBiTreeNode *right, *left;
}ThreadBiTreeNode, *ThreadBiTree;

/**
  *  先序方式创建线索二叉树
  *  请用以下方式输入ab#，然后回车；c##，然后回车；
  *  d#,然后回车；g##，然后回车。
  */
ThreadBiTree CreateTree( )
{
	ThreadBiTree t;
	DataType ch;
	cin >> ch;
	if( ch == '#' )
		t = NULL;
	else
	{
		t = ( ThreadBiTree )malloc( sizeof( ThreadBiTreeNode ) );
		if( t )
		{
			t->data = ch;
			t->ltag = t->rtag = 0;
			t->left = CreateTree();
			t->right = CreateTree();
		}
	}
	return t;
}

/**
  *  先序线索二叉树，将空的指针指向一个连接
  *  这里要申请一个全局变量g_pre
  *
  */
ThreadBiTree g_pre;

void PreThreadTree( ThreadBiTree t )
{
	if( t == NULL )
		return;
	
	if( t->left == NULL )
		t->ltag = 1;
	if( t->right == NULL )
		t->rtag = 1;

	if( g_pre != NULL && t->ltag == 1 )
		t->left = g_pre;
	if( g_pre != NULL && g_pre->rtag == 1  )
		g_pre->right = t;
	g_pre = t;

	if( t->ltag == 0 )
		PreThreadTree( t->left );
	if( t->rtag == 0 )
		PreThreadTree( t->right );
}

/**
  *  中序线索二叉树
  * 
  *
  */
void InThreadTree( ThreadBiTree t )
{
	if( t == NULL )
		return;

	InThreadTree( t->left );
	if( t->left == NULL )
		t->ltag = 1;
	if( t->right == NULL )
		t->rtag = 1;

	if( g_pre != NULL && t->ltag == 1 )
		t->left = g_pre;
	if( g_pre != NULL && g_pre->rtag == 1  )
		g_pre->right = t;
	g_pre = t;

	if( t->rtag == 0 )
		InThreadTree( t->right );
}

/**
  *  后序线索二叉树
  * 
  *
  */
void PostThreadTree( ThreadBiTree t )
{
	if( t == NULL )
		return;

	PostThreadTree( t->left );
	PostThreadTree( t->right );

	if( t->left == NULL )
		t->ltag = 1;
	if( t->right == NULL )
		t->rtag = 1;

	if( g_pre != NULL && t->ltag == 1 )
		t->left = g_pre;
	if( g_pre != NULL && g_pre->rtag == 1  )
		g_pre->right = t;
	g_pre = t;
}

/**
  *  寻找当前节点的后节点
  *  
  *
  */
ThreadBiTree FindNode( ThreadBiTree t )
{
	if( t->rtag == 1 )
		return t->right;
	else
	{
		t = t->right;
		while( t->ltag == 0 )
		{
			t = t->left;
		}	
		return t;
	}
}

/**
  *  中序方式遍历线索二叉树
  *  在VC6.0下测试成功
  *
  */
void InOrderThreadBiTree( ThreadBiTree t )
{
	if( t == NULL )
		return;
	printf( "%c ", t->data );
	ThreadBiTree p;
	
	//当只有一个元素时，并没有建立起线索二叉树
	if( t->ltag == 0 ) 
		p = t->left;
	else 
		p = t->right;

	while( p && ( p != t ) )
	{
		while( p->ltag == 0  )
		{	
			printf( "%c ", p->data );
			p = p->left;
		}
		printf( "%c ", p->data );
		
		while( p->rtag == 1 && p->right != t && p->right )
		{
			p = p->right;
			printf( "%c ", p->data );
		}
		p = p->right;
	}
}

/**
  *  插入右节点: 参考网上代码，有些地方需要商榷。
  * 
  *	
  */
void InsertRightNode( ThreadBiTree p, ThreadBiTree node )
{
    node->ltag = node->rtag = 1;//node->rtag=1为什么要置1，因为有node->right=p->right;这句
    node->left = p; //这可以考虑node->rtag = 0.
    node->right = p->right;//也可以让它为node->left = p->right，(^_^)是不是钻牛角尖了呢？
    p->right = p; //当然因为线索连接好了，为了不影响先前设置好的线索，故这样做，暂不考证！
    p->rtag = 0;
}

int main( void )
{
	ThreadBiTree t;
	t = CreateTree();

	PreThreadTree( t  );
	InOrderThreadBiTree( t );
	return 0;
}