Experiment name (tree)

1, Experiment purpose and requirements Be familiar with various representation methods and traversal methods of trees, master the implementation of relevant algorithms, and understand the application of trees in computer science and other engineering technologies.

2, Experimental content and principle Choose the first question and the second question (the first question and the second question are written in a program:) Input: (in the first line, a binary tree is traversed in sequence, and null is # replaced by null. In the second line, the sequence number of the search node is entered) ABD##EH###CF#I##G## 3 Output: (first output three traversal output results, then output the number of leaf nodes, and finally output the search location node) Preorder traversal result: ABDEHCFIG Middle order traversal result: DBHEAFICG Post order traversal result: DHEBIFGCA Number of leaf nodes: 4 The node of the third position is: D Storage structure: Binary linked list storage Algorithm idea: Through the recursive idea, if there are no left and right children, it is a recursive exit, that is, a leaf node The node is stored in the a [] array through pre order traversal, and the node at the K position is the value of a[k]

3, Main instruments and equipment HP notebook and win10 environment are all running in cpp file. Please also open it in CPP form

4, Operation methods and experimental steps

Questions 1 and 2:

#include<stdio.h>
#include<windows.h>
#define N 1000
char a[N];
int i=1,k;

typedef struct node{
	char data;
	struct node * lchild;
	struct node * rchild; 
}BiTree;

BiTree * CreatTree();
int Count(BiTree * );//Leaf node 
void Preorder(BiTree * );//Preorder traversal  
void Middleorder(BiTree * );//Medium order traversal 
void Postorder(BiTree * );//Postorder traversal 
void getNode(BiTree * );//Recursive algorithm, find the node at the K position in the preorder sequence in the binary tree

int main(){
	printf("Please enter a binary tree in the order of precedence, and leave blank#Replace \ n ""); 
	BiTree * top = NULL;
	top = CreatTree();
	
	printf("Preorder traversal result: ");
	Preorder(top);
	printf("\n");
	
	printf("Middle order traversal result: ");
	Middleorder(top);
	printf("\n");
	
	printf("Postorder traversal result: ");
	Postorder(top);
	printf("\n");
	
	putchar('\n');
	printf("The number of leaf nodes is: %d\n",Count(top));
	printf("Please enter the node location to find: ");
	scanf("%d",&k);
	printf("The first%d Nodes at locations are: ",k);
	getNode(top);
	printf("%c\n",a[k]);
	system("pause"); 
	return 0;
	
}

BiTree * CreatTree(){
	BiTree *t;
	char ch;
	ch = getchar();
	if(ch != '#'){
		t=(BiTree *)malloc(sizeof(BiTree));
		t->data=ch;//First, traverse the left and right of the root, and empty is # replaced 
		t->lchild=CreatTree();
		t->rchild=CreatTree();
	}
	else{
		t=NULL;
	}
	return t;
}
int Count(BiTree * top){
	if(top==NULL){
		return 0;
	}
	else if((top->lchild==NULL)&&(top->rchild==NULL)){//Recursive exit. If the left and right children are empty, it is a leaf node 
		return 1;
	}
	else {
		return Count(top->lchild)+Count(top->rchild);
	}
}

void Preorder(BiTree *top){
	if(top!=NULL){//If it is not empty, it is traversed first 
		printf("%c",top->data);
		Preorder(top->lchild);
		Preorder(top->rchild);
	}
}

void Middleorder(BiTree *top){
	if(top!=NULL){//If it is not empty, the middle order traversal 
		Middleorder(top->lchild);
		printf("%c",top->data);
		Middleorder(top->rchild);
	}
}

void Postorder(BiTree *top){
	if(top!=NULL){//If it is not empty, it will be traversed in sequence 
		Postorder(top->lchild);
		Postorder(top->rchild);
		printf("%c",top->data);
	}
}

void getNode(BiTree *t){
	if(t){//If it is not empty, traverse around the root 
		a[i]=t->data;
		i++;
		getNode(t->lchild);
		getNode(t->rchild);
	}
}

5, Experimental data recording and processing

Question 1, question 2:

6, Experimental results and analysis

The program uses recursion to establish a binary tree, recursively output a binary tree, leaf node, that is, find the location node. The recursive algorithm is relatively simple to write, easy to understand and clear at a glance, but the efficiency is not as good as the non recursive algorithm

Three non recursive traversal algorithms can be realized with the help of stack. In addition, the hierarchical traversal algorithm of binary tree can be given, which can be realized with the help of queue.

I give a non recursive algorithm for preorder traversal:

//Idea: put t on the stack and traverse the left subtree; After traversing the left subtree, when returning, the top element of the stack should be t. after leaving the stack, first traverse the right subtree of T.

void PreOrder(BiTree T){  

 stack<BiTree> stack;  

    //p is the traversal pointer

    BiTree p = T;  

    //Loop when p is not empty or stack is not empty

    while (p || !stack.empty())  

{  

       if (p != NULL)  

                {  

            //Store in stack

           stack.push(p);  

         //Operate on the nodes in the tree

         operation1(p->data);  

          //Traverse left subtree

           p = p->lchild;  

        }  

        else  

          {  

                 //Back stack

            p = stack.top();  

            stack.pop();  

            //Access right subtree

            p = p->rchild;  

        }  

    }   

}  

7, Discussion and experience

The third topic is non recursive rewriting program. I tried to rewrite it with the tutorial. I found it more complex, but non recursive rewriting

The above procedures will improve the efficiency. I will study this method in my spare time after the test