Clue binary tree

Clue binary tree

This paper refers to the data structure of Dahua

principle

For a binary list with n nodes, each node has a pointer field pointing to the left and right children, so there are 2n pointer fields in total. The binary tree with n nodes has a total of n-1 branches, that is, there are 2n-(n-1)=n+1 empty finger needle fields. These empty finger needle fields do not store anything and waste memory resources in vain.

When we do traversal, such as middle order traversal, we can know who is the precursor and successor of any node; But in the binary linked list, we can only know the address of each node pointing to its left and right child nodes, but we don't know the predecessor and successor of a node.

In order to make full use of these empty addresses, they can be used to store the addresses of the predecessor and successor nodes pointing to the node in a certain traversal order. We call this kind of pointer pointing to the precursor and successor as clue, the binary linked list with clue is called clue linked list, and the corresponding binary tree is called clue binary tree.


We can change the rchild in all empty finger needle fields to point to its successor nodes, and the lchild in all empty finger needle fields to point to the precursor of the current node. In this way, it becomes a two-way linked list, which is convenient for us to insert, delete and find a node. The process of traversing a binary tree in some order to turn it into a clue binary tree is called cueing.

structure

In order to distinguish whether the lchild of a node points to the left child or the precursor; Whether rchild points to the right child or the successor, we add two boolean variable flag fields ltag and rtag in each node, which occupy less memory space than pointer variables such as lchild and rchild.

  • When ltag is 0, it points to the left child of the node, and when ltag is 1, it points to the precursor of the node;
  • When rtag is 0, it points to the right child of the node, and when rtag is 1, it points to the successor node;
/* Definition of binary clue storage structure of binary tree */
typedef enum	{Link, Thread} PointerTag;	//Link == 0 refers to the left and right children, Thread == 1 refers to the predecessor and successor
/* Binary clue storage node structure */
typedef struct BithrNode{
	TElemType data;		//Node data
	struct BiThrNode *lchild, *rchild;	//Left and right child pointers
	PointerTag LTag;
	PointerTag RTag;	//Left and right signs
}biThrNode, *BiThrTree;

Cueing

The essence of cueing is to change the null pointer in the binary list to the clue pointing to the precursor or successor. Because the precursor and subsequent information can only be obtained when traversing the binary tree, the process of cueing is the process of modifying the null pointer in the process of traversal

Recursive function code of middle order traversal cueing:

BiThrTree pre;	//Global variable, always pointing to the node just visited
/* Middle order traversal for middle order cueing */
void InThreading(BiThrTree p){
	if(p){
		InThreading(p->lchild);	 //Recursive left subtree cueing
		if(!p->lchild){			//No left child	
			p->LTag = Thread;	//Precursor clue
			p->lchild = pre;	//The left child's pointer points to the front drive
		}
		if(!pre->rchild){		//The precursor has no right child
			pre->RTag = Thread;	//Subsequent clues
			pre->rchild = p;	//The right child pointer of the predecessor points to the successor (current node p)
		}
		pre = p;	//Keep pre pointing to the precursor of p
		InThreading(p->rchild);		//Recursive right subtree cueing
	}
}

With a clue binary tree, we traverse it, which is equivalent to operating a two-way linked list structure.

Like the two-way linked list structure, add a head node on the binary clue linked list, as shown in figure 6-10-6, and make the pointer of its lchild field point to the root node of the binary tree, and the pointer of its rchild field point to the last node accessed during the middle order traversal. On the contrary, in the first node of the middle order sequence of the binary tree, the lchild field pointer and the rchild field pointer of the last node point to the head node. The advantage of this definition is that we can traverse from the first node to the next node, or from the last node to the precursor.

/* T Point to the head node, the left chain lchild of the head node points to the root node, and the right key rchild of the head node points to the last node of the middle order traversal. Binary tree T represented by middle order traversal binary clue linked list */
Status InOrderTraverse(BiThrTree T){
	BiThrTree p;
	p = T->lchild;	//p points to the root node
	while(p != T){	//At the end of empty tree or traversal, p == T
		while(p->LTag == Link)	//When LTag == 0, cycle to the first node of the middle sequence
			p = p->lchild;
		printf("%c",p->data);	//Display node data, which can be changed to other node operations
		while(p->RTag == Thread && p->rchild != T){
			p = p->rchild;
			printf("%c", p->data);
		}
		p = p->rchild;		//p goes to the root of its right sub tree
	}
	return OK;
}

This code is equivalent to scanning a linked list, so the time complexity is O(n);
Because it makes full use of the space of the empty finger needle domain (which is equivalent to saving space), it also ensures that one traversal at the time of creation can benefit from the information of the predecessor and successor for life (which means saving time). Therefore, in practical problems, if the binary tree needs to be traversed frequently or the precursor and successor in some traversal sequence are needed when looking up nodes, the storage structure of clue binary list is a very good choice.

Examples

Input sequence (pre sequence input): 1, 2, 46553565535, 56553565535, 3, 66553565535, 76553565535

#include <stdio.h>
#include <stdlib.h>
typedef int TElemType;
typedef enum{
	Link, Thread
}PointerTag;

struct BithrNode{
	TElemType data;	//Data domain 
	BithrNode *lchild, *rchild;	//Left and right children 
	PointerTag LTag;	//sign 
	PointerTag RTag;
};

BithrNode* pre;	//Point to the previous access node to get the precursor 

/* Middle order cueing is actually the process of changing null pointers to precursors and successors */
void InThreading(BithrNode* b){
	if(b != NULL){
		//Medium order traversal, so recursively access the leaf node first 
		InThreading(b->lchild);
		if(b->lchild == NULL){	//No left child 
			b->LTag = Thread;	//Clue point 
			b->lchild = pre;	//The left child points to the front 
		}
		if(pre->rchild == NULL){	//If the previous node has no right child, then the current node is the successor of the previous node 
			pre->RTag = Thread;	//Clue point
			pre->rchild = b;	//The successor of the pre node is the current node 
		}
		pre = b;	//Point to the previous visited node 
		InThreading(b->rchild);	//Cued right subtree
	}
}

/* Initialize binary tree */
BithrNode* InitBithree(){
	int input;
	printf("Please enter a value, 65535 indicates NULL: \n");
	scanf("%d", &input);
	if(input != 65535){
		//New node
		BithrNode* newNode = (BithrNode*)malloc(sizeof(BithrNode));
		newNode->data = input;
		newNode->LTag = newNode->RTag = Link;
		newNode->lchild = InitBithree();
		newNode->rchild = InitBithree();
		return newNode;
	}
	return NULL;
}

/* Middle order traversal clue binary tree */
void InOrderTraverse(BithrNode* b){
	
	BithrNode* p = b;
	while(p){
		//Start traversing from the first node of the middle order traversal 
		while(p->LTag == Link){
			p = p->lchild;
		} 
		printf("%d ", p->data);
		while(p->RTag == Thread){	//Subsequent flag effective
			p = p->rchild;	//The current node points to the successor node
			printf("%d ",p->data); 
		}
		//Find the leftmost node under the right subtree and cycle through it
		p = p->rchild;
	}
}

int main(){
	
	BithrNode* root = InitBithree();	//Initialize the binary tree to get the root node
	pre = root;	//Point to root node
	InThreading(root);
	InOrderTraverse(root);
	return 0;
} 

Example results

Tags: C data structure Binary tree

Posted by Satria Ox41464b on Sun, 08 May 2022 08:35:18 +0300