从零开始学数据结构系列之第三章《先序线索二叉树查找及总代码》

文章目录

• 查找下一个节点
• 总代码
• 往期回顾

查找下一个节点

​   我们为啥没有像中序二叉树一样有第一个节点，因为我们一开始最大就是我们的根节点，所以无需遍历去寻找我们的第一个节点，我们的T就是我们的第一个节点

​ 我们回过来看中序线索二叉树的节点应该是怎么写的

/* 按线索来查找 */
TreeNode* getNext(TreeNode* node) 
{
	if (node -> rtag == 1)
        return node -> rchild;
    else
        return getFirst(node -> rchild);
}

​   我们想一下，这一个能不能直接搬过来用，很显然，不行，由于我们直接没有getFirst这一个函数了，那我们简单的修改一下

TreeNode* getNext(TreeNode* node) 
{
	if (node -> rtag == 1)
        return node -> rchild;
    else
        return node ->lchild;
}

​ 简单的推导一下，我们第一个传进来的参数是A，之后返回的参数是B，之后是D，后面是E, 之后是C

这样子好像没错，但是我们再将条件变化一下

  我们前三个节点是正常进行遍历，但是当遍历到D节点的时候，我们执行的的代码是return node ->lchild;,那D的前驱是B，那这样子的话我们遍历的顺序又不对了，那应该怎么进行修改呢

…
…
…
…
…
…
…

这里直接公布答案

TreeNode* getNext(TreeNode* node) 
{
	if (node -> rtag == 1 || node -> ltag == 1)
        return node -> rchild;
    else 
		return node -> lchild;
}

那我们这样子的话，就可以解决这个小问题了

其他部分和中序遍历差不多的，我们只用注意一下以上两个小问题就行了

总代码

/*可以输入
ABD##E##CF##G##
来进行验证
*/

#include <stdio.h>
#include <stdlib.h>
#define size 20

typedef struct TreeNode 
{
	char data;
	struct TreeNode *lchild;
	struct TreeNode *rchild;
	int ltag;
	int rtag;

}TreeNode;


void createTree(TreeNode** T,char* temp,int* index)
{
	char ch;
	
	ch = temp[*index];
	(*index)++;

	if( ch == '#') *T = NULL;
	else
	{
		 *T =(TreeNode*)malloc(sizeof(TreeNode));
		 (*T)->data = ch;
		 (*T)->ltag = 0;
		 (*T)->rtag = 0;
		createTree(&(*T)->lchild,temp,index);
		createTree(&(*T)->rchild,temp,index);		
	}
}

void inThreadTree(TreeNode* T, TreeNode** pre) 
{
	if(T)
	{		
		if(T->lchild == NULL)
		{
			T->ltag = 1;
			T->lchild = *pre;
		}
		if(*pre != NULL && (*pre)->rchild == NULL)
		{
			(*pre)->rtag = 1;
			(*pre)->rchild = T;
		}
		*pre = T;

		if(T->ltag == 0)
			inThreadTree(T->lchild,pre);
        inThreadTree(T -> rchild, pre);
	}
}


TreeNode* getNext(TreeNode* node) 
{
	if (node -> rtag == 1 || node -> ltag == 1)
        return node -> rchild;
    else 
		return node -> lchild;
}


int main(int argc, char* argv[]) 
{
	TreeNode *T;
	TreeNode* pre = NULL;
	int i=0;
	char *temp=NULL;
	TreeNode* node = NULL;
	temp=(char*)malloc(sizeof(char) * (size+1));
	gets(temp);
	createTree(&T,temp,&i);
	inThreadTree(T, &pre);
    pre -> rtag = 1;
    pre -> rchild = NULL;
	node = T;
	for (; node != NULL; node = getNext(node)) 
	{
        printf("%c ", node -> data);
    }
    printf("\n");

    return 0;
}

往期回顾

1.【第一章】《线性表与顺序表》
2.【第一章】《单链表》
3.【第一章】《单链表的介绍》
4.【第一章】《单链表的基本操作》
5.【第一章】《单链表循环》
6.【第一章】《双链表》
7.【第一章】《双链表循环》
8.【第二章】《栈》
9.【第二章】《队》
10.【第二章】《字符串暴力匹配》
11.【第二章】《字符串kmp匹配》
12.【第三章】《树的基础概念》
13.【第三章】《二叉树的存储结构》
14.【第三章】《二叉树链式结构及实现1》
15.【第三章】《二叉树链式结构及实现2》
16.【第三章】《二叉树链式结构及实现3》
17.【第三章】《二叉树链式结构及实现4》
18.【第三章】《二叉树链式结构及实现5》
19.【第三章】《中序线索二叉树理论部分》
20.【第三章】《中序线索二叉树代码初始化及创树》
21.【第三章】《中序线索二叉树线索化及总代码》
22【第三章】《先序线索二叉树理论及线索化》