The tree of the data structure of the postgraduate entrance examination (6.10) -- the value of the k-th node in the output sequence of the exercise (C representation)

subject

Suppose that the binary tree is stored in a binary linked list storage structure, and a program is written to output the value of the k-th node in the sequence of traversal, assuming that K is not greater than the total node tree (the type of node data field is char type).

analysis

Using the first order traversal, we use a variable to calculate whether the current node is the first node of the whole first order traversal sequence, and then compare it with k to see whether it is equal, and then output the value of the corresponding node.

code

Core code:

/* Output the value of the k-th node in the preorder traversal */
/* E.g.: ABC, De, F, GH### */ 
int n=0;// Define the global variable n, and set the initial node count value to 0
void trave(BTNode *p,int k) {
	if(p!=NULL) {
		n++;// Count when you first arrive at a node, indicating that this is the nth node
		if(k==n) { // When arriving at a node for the first time, judge whether it is the k-th node in the sequence of precedence
			printf("%c",p->data);// If yes, output the value of the node
			return;// And do not continue to traverse. Use return to return directly
		}
		trave(p->lchild,k);
		trave(p->rchild,k);
	}
}

Full code:

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

/* Number structure type definition*/
typedef struct BTNode {
	char data;// Here, the default node data field is char type
	struct BTNode *lchild;// Left child pointer field
	struct BTNode *rchild;// Right child pointer field
} BTNode,*BiTree;

/* Create a binary tree based on input */
/* E.g.: ABC, De, F, GH### */
void CreatBiNode(BTNode **Node) { //Note the parameters passed here (double pointer)
	char data;
	scanf("%c", &data);

	*Node = (BiTree)malloc(sizeof(BTNode));
	if (data == '#') {
		*Node = NULL;
	} else if ((data != '#') && (*Node)) {
		(*Node)->data = data;
		(*Node)->lchild = NULL;
		(*Node)->rchild = NULL;
		CreatBiNode(&(*Node)->lchild);
		CreatBiNode(&(*Node)->rchild);
	}
}

/* Output the value of the k-th node in the preorder traversal */
/* E.g.: ABC, De, F, GH### */ 
int n=0;// Define the global variable n, and set the initial node count value to 0
void trave(BTNode *p,int k) {
	if(p!=NULL) {
		n++;// Count when you first arrive at a node, indicating that this is the nth node
		if(k==n) { // When arriving at a node for the first time, judge whether it is the k-th node in the sequence of precedence
			printf("%c",p->data);// If yes, output the value of the node
			return;// And do not continue to traverse. Use return to return directly
		}
		trave(p->lchild,k);
		trave(p->rchild,k);
	}
}


int main() {
	printf("First order input binary tree(For null node'#'for): ");
	BiTree T=NULL;
	CreatBiNode(&T);// Create a binary tree

	/* Output the value of the k-th node in the preorder traversal sequence */ 
	trave(T,4);

	return 0;
}

Operation result:

Search the value code of the k-th node in the middle order traversal sequence:

int n=0;
void trave(BTNode *p,int k){
	if(p!=NULL){
		trave(p->lchild,k);
		n++;
		if(k==n){
			printf("%c",p->data);
			return;
		}
		trave(p->rchild,k);
	}
}

To find the value code of the k-th node in the subsequent traversal sequence:

int n=0;
void trave(BTNode *p,int k){
	if(p!=NULL){
		trave(p->lchild,k);
		trave(p->rchild,k);
		n++;
		if(k==n){
			printf("%c",p->data);
			return;
		}
	}
}

 

Posted on Thu, 04 Jun 2020 10:03:59 -0700 by Plug-in