苗火 Nicholas

[Data structures]Threaded binary tree

2019-8-2 萧 写技术

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

#define MAX 20

typedef struct _BiTree{
	char data;
	struct _BiTree *left;
	struct _BiTree *right;
	int lTag;
	int rTag;
}BiTree;

BiTree *pre;

int PreOrderTraverseCreate(BiTree **T)
{
	char c;
	scanf(" %c",&c); 
	printf(" %c", c);
	if(c == '$'){
		*T = NULL;
	}else{
		*T = (BiTree *)malloc(sizeof(BiTree));
		(*T)->data = c;
		(*T)->left = (*T)->right = NULL;
		(*T)->lTag = (*T)->rTag = 0;

		PreOrderTraverseCreate(&(*T)->left);
		PreOrderTraverseCreate(&(*T)->right);
	}
}

void InOrderTraverseThreaded(BiTree *T)
{
	BiTree *p = T->left;
	while(p != T){
		while(p->lTag == 0){
			p = p->left;
		}
		printf(" %c", p->data);
		while(p->rTag == 1 && p->right != T){
			p = p->right;
			printf(" %c", p->data);	
		}
		p = p->right;
	}
}

void InThreading(BiTree *p)
{
	if(p){
		InThreading(p->left);
		if(!p->left){
			p->left = pre;
			p->lTag = 1;
		}
		if(!pre->right){
			pre->right = p;
			pre->rTag = 1;
		}
		pre = p;
		printf(" %c", p->data);
		InThreading(p->right);
	}
}

void InOrderThreading(BiTree **head, BiTree *T)
{
	*head = (BiTree *)malloc(sizeof(BiTree));

	(*head)->lTag = 0;
	(*head)->rTag = 1;
	(*head)->right = *head;
	if(!T){
		(*head)->left = *head;
	}else{
		(*head)->left = T;
		pre = *head;

		InThreading(T);

		pre->right = *head;
		pre->rTag = 1;

		(*head)->right = pre;
	}

}

void main()
{
	BiTree *T;	
	BiTree *head;

	printf("log.anycle.com\n\n");
	printf("Pre order traverse create binary tree:\n");
	PreOrderTraverseCreate(&T);
	printf("\n");

	printf("In order threading:\n");
	InOrderThreading(&head, T);
	printf("\n");

	printf("In order traverse threaded binary tree:\n");
	InOrderTraverseThreaded(head);
	printf("\n");
}

标签: Data Structures data_structures