[basic operation summary of binary tree 1]

//Binary tree linked list storage
#include<iostream>
#include<queue>
#include<algorithm>
const int N=1e5+10;
using namespace std;
struct BiNode{
	char data;
	BiNode *lchild,*rchild;
};
class BiTree{
	private:
		BiNode* root;
	public:
		BiTree(){root=create(root);}
		~BiTree(){release(root);}
		BiNode* getRoot(){return root;}
		BiNode* create(BiNode *bt);
		void preOrder(BiNode* bt);
		void inOrder(BiNode* bt);
		void postOrder(BiNode* bt);
		void levelOrder(BiNode* bt);
		void release(BiNode* bt);
		int getDepth(BiNode* bt);
		int getNum(BiNode* bt);
		int getArray(BiNode* bt,char *array,int i); 
		
}; 
BiNode* BiTree::create(BiNode *bt){
	char ch;
	cin>>ch;
	if(ch=='#') bt=NULL; 
	else{
		bt=new BiNode;
		bt->data=ch;
		bt->lchild=create(bt->lchild);
		bt->rchild=create(bt->rchild);
	}
	return bt;
}

void BiTree::preOrder(BiNode* bt){
	if(bt==NULL) return;
	else{
		cout<<bt->data<<" ";
		preOrder(bt->lchild);
		preOrder(bt->rchild);
	}
	return;
}

void BiTree::inOrder(BiNode* bt){
	if(bt==NULL) return;
	else{
		inOrder(bt->lchild);
		cout<<bt->data<<" ";
		inOrder(bt->rchild);
	}
	return;
	
}

void BiTree::postOrder(BiNode* bt){
	if(bt==NULL) return;
	else{
		postOrder(bt->lchild);
		postOrder(bt->rchild);
		cout<<bt->data<<" "; 
	}
	return;
}

void BiTree::levelOrder(BiNode* bt){
	if(bt==NULL) return;
	queue<BiNode*> Q;
	Q.push(bt);
	BiNode* p;
	while(!Q.empty()){
		p=Q.front();
		Q.pop();
		cout<<p->data<<" ";
		if(p->lchild!=NULL) Q.push(p->lchild);
		if(p->rchild!=NULL) Q.push(p->rchild);
	}
	return;
}
//Post order traversal delete node 
void BiTree::release(BiNode* bt){
	BiNode* p=bt;
	if(p->lchild==NULL&&p->rchild==NULL){
		cout<<"delete "<<p->data<<endl;
		delete p;
	}
	else{
		if(p->lchild!=NULL) release(bt->lchild);
		if(p->rchild!=NULL) release(bt->rchild);
		cout<<"delete "<<p->data<<endl;
		delete p;
	}
	return;
}

int BiTree::getDepth(BiNode* bt){
//	if(bt->lchild==NULL&&bt->rchild==NULL) return 1;
//	else{
//		int left=0,right=0;
//		if(bt->lchild!=NULL) left=getDepth(bt->lchild);
//		if(bt->rchild!=NULL) right=getDepth(bt->rchild);
//		return max(left,right)+1;
//	}
	if(bt==NULL) return 0;
	int left=getDepth(bt->lchild);
	int right=getDepth(bt->rchild);
	return max(left,right)+1;
} 

int BiTree::getNum(BiNode* bt){
	if(bt==NULL) return 0;
	int left=getNum(bt->lchild);
	int right=getNum(bt->rchild);
	return left+right+1;
}
int BiTree::getArray(BiNode* bt,char *array,int i){
	BiNode* p=bt;
	if(p==NULL) return i/2;
	array[i]=p->data;
	int left=getArray(p->lchild,array,i*2);
	int right=getArray(p->rchild,array,i*2+1);
	return max(left,right);
}


int main(){
	BiTree BT;
	BiNode* r=BT.getRoot();
	cout<<"Preorder traversal"<<endl;
	BT.preOrder(r);
	cout<<endl;
	cout<<"Middle order traversal"<<endl;
	BT.inOrder(r);
	cout<<endl;
	cout<<"Postorder traversal"<<endl;
	BT.postOrder(r);
	cout<<endl;
	cout<<"level traversal "<<endl;
	BT.levelOrder(r);
	cout<<endl; 
	cout<<"depth:"<<endl;
	cout<<BT.getDepth(r)<<endl;
	cout<<"Number of nodes:"<<endl;
	cout<<BT.getNum(r)<<endl;
	cout<<"Into a one-dimensional array"<<endl;
	char array[N];
	int len=BT.getArray(r,array,1);
	for(int i=1;i<=len;i++){
		if(array[i]=='\0') cout<<'^';
		else cout<<array[i];
	} 
	cout<<"Start deconstruction!"<<endl;
	
	return 0;
	
} 

Take the binary tree as an example to try the effect

The printing effect is as follows:

Let's take out each function list and talk about it briefly

Constructor

BiTree(){root=create(root);}

BiNode* create(BiNode *bt);

Here, call create in the constructor, because you need to call the function recursively and new a space. Remember that root=create(root)

It's easy for me to make mistakes

Pre -, middle -, and post order traversal

Take preOrder(BiNode* bt) as an example

Traversal is also written recursively. There's nothing to say.

level traversal

levelOrder(BiNode* bt)

Sequence traversal uses a container, the queue in STL.

Explain the functions used:

 

Because pop() has a return value when you write your own code to implement the queue. It can only be accessed through front(). A bug was d found when writing

The idea here is to join the root node into the team and check whether it has left and right subtrees every time it leaves the team. If yes, join the queue (using the queue first in first out feature)

Destructor

~BiNode(release(root));

release(BiNode* bt)

Here we need to reclaim the new space step by step. As we all know, binary trees visit and ask child nodes through the root node. If you delete the root node, there will be no way to reclaim the left and right subtrees, so we use the method of sequential access to delete

If it is already a leaf node (without left and right subtrees), it can be de directly

If it is a branch node, you need to de the left and right subtrees first, and then de yourself.

Find depth

getDepth(BiNode* bt);

Depth, as we all know, is the maximum depth of a binary tree. Then, let's first find the depth on the left and the depth on the right, take the largest, add 1 of our own layer, and return. Then call recursively.

Knot count

getNum(BiNode* bt);

The number and depth of knots are similar.

Let's replace "first find the depth on the left and the depth on the right, take the largest, and then add the 1 of our own layer" with "find the number on the left and the number on the right, add it, and then add our own 1". We can call recursively.

Convert to one-dimensional array

getArray(BiNode* bt,char *array,int i);

This is similar to the previous sequence, but there is one more step to store the traversal results (and according to the nature of binary tree).

nature:

One point coordinate is i (subscript starts from 1)

Then the left subtree (root node of) = = i*2

Right subtree (root node of) = = i*2+1

The strategy is to store only data with actual values

When traversing the array, if there is no data, we will manually print '^'

I wrote about the problems encountered after:

I don't know how large the array is -- -- > Strategy: open 1e5+10 when it is large

How to judge the ending -------- -- > good question, take a closer look at the following code

if(p==NULL) return i/2;


max(left,right);

One is the backtracking after accessing the leaf node

A number gets the maximum subscript of the array

over!

Tags: C++ data structure

Posted by nano on Sun, 01 May 2022 19:07:09 +0300