Data Structure - Binary Tree

1. Sequential storage

The root node bit order is 0. The remaining nodes, assuming the bit order is i, if the left child exists, the left child is 2i+1.

If the right child exists, the right child is 2i+2. Its parent nodes are all (i-1)/2.

If the node does not exist, it can be marked with a number.

The disadvantage is that it is easy to waste space, and it is generally used for complete binary tree, or binary tree storage close to complete binary tree.

2. Chain storage structure

There are two types of linked list nodes in chain storage, one is a binary linked list node, and the other is a three-forked linked list node.

A binary linked list node only stores pointers to the left and right children and the data of the node.

The three-forked list node adds a pointer to the parent node.

These two nodes can of course also be used for sequential storage.

Just talk about the binary linked list:

1. Depth-first traversal

(1) Preorder traversal (DLR is data, left, right)

It can be seen that when the node is not empty, first traverse the node, then traverse the left node, then traverse the right node, and finally end.

Otherwise return until all nodes are traversed.

(2) In-order traversal (LDR)

It can be seen that when the node is not empty, first traverse the left node of the node, then traverse the node, then traverse the right node of the node, and finally end.

Otherwise return until all nodes are traversed.

(3) Post-order traversal (LRD)

It can be seen that when the node is not empty, first traverse the left node of the node, then traverse the right node of the node, then traverse the node, and finally end.

Otherwise return until all nodes are traversed.

In terms of memory, it is the traversal order of the node, which is the order traversal. And follow the traversal of the left node before the right node.

2. Breadth-first traversal

Level order traversal:

        

That is, first from top to bottom, from left to right, as shown in the figure, the numbers are traversed in order.

#pragma once
#include<stack>
#include<queue>
#include<iostream>
template<class T>
class binary_tree
{
public:
	struct node
	{
		T data;
		node* left;
		node* right;
		node() = default;
		node(const T& d, node* const l = nullptr, node* const r = nullptr)
		{
			data = d; left = l; right = r;
		}
	};
	node* root;
	binary_tree():root(nullptr){}
	~binary_tree() { p_clear(root); }
	unsigned size() { return p_size(root); }
	unsigned height() { return p_height(root); }
	unsigned leaf_num() { return p_leaf_num(root); }
	void preorder0() { p_preorder0(root); }
	void preorder1() { p_preorder1(root); }
	void inorder0() { p_inorder0(root); }
	void inorder1() { p_inorder1(root); }
	void postorder0() { p_postorder0(root); }
	void postorder1() { p_postorder1(root); }
	void levelorder() { p_levelorder(root); }
private:
	//A p in front of the name means private
	unsigned p_size(node* root);//Find the number of nodes
	void p_clear(node* root);//delete all nodes
	unsigned p_height(node* root);//Find the height of the binary tree
	unsigned p_leaf_num(node* root);//Find the number of nodes in a binary tree
	//1 for recursive mode, 0 for non-recursive mode
	void p_preorder0(node* root);//preorder traversal
	void p_preorder1(node* root);
	void p_inorder0(node* root);//Inorder traversal
	void p_inorder1(node* root);
	void p_postorder0(node* root);
	void p_postorder1(node* root);//post-order traversal
	void p_levelorder(node* root);
};
template<class T>
unsigned binary_tree<T>::p_size(node* root)
{
	//If the current node is empty, return 0
	if (!root)
		return 0;
	//If it is not empty, the number of nodes is equal to 1 (representing the current node) + the number of left subtree nodes + the number of right subtree nodes
	return 1 + p_size(root->left) + p_size(root->right);
}
template<class T>
void binary_tree<T>::p_clear(node* root)
{
	if (!root)//Return if node is empty
		return;
	else
	{
		node* p = root;
		p_clear(p->left);//delete left subtree
		p_clear(p->right);//delete right subtree
		delete p;//delete current node
	}
}
template<class T>
unsigned binary_tree<T>::p_height(node* root)
{
	if (!root)
		return 0;
	unsigned left_height = p_height(root->left);//left subtree length
	unsigned right_height = p_height(root->right);//right subtree length
	return 1 + (left_height >= right_height ? left_height : right_height);
}
template<class T>
unsigned binary_tree<T>::p_leaf_num(node* root)
{
	//If it is a leaf node, return 1
	if (!root->left&&!root->right)
		return 1;
	//If not, return the left subtree leaf node + the right subtree leaf node
	return p_leaf_num(root->left) + p_leaf_num(root->right);
}
template<class T>
void binary_tree<T>::p_preorder0(node* root)
{
	if (!root)
		return;
	//No recursion, using stack structure
	std::stack<node*> obj;
	/*two methods
	* Node* p=root;
	* while(!obj.empty()||p)
	* {
	*	if(p)//Existence means to traverse the current node first, push the current to the stack, leave it to visit the right node later, and then traverse the left node
	*	{
	*		std::cout<<p->data<<" ";
	*		obj.push(p);
	*		p=p->left;
	*	}
	*	else//The left node accesses to the head, accesses the right node of the previous node,
	*	{
	*		p=obj.top();
	*		obj.pop();
	*		p=p->right;
	*	}
	* }
	*/
	//optimize it
	obj.push(root);
	while (!obj.empty())
	{
		auto p = obj.top();
		obj.pop();
		std::cout << p->data << " ";
		//Press the right node first, then the left node, to ensure that the left node of the node is accessed next time
		if(p->left)
			obj.push(p->right);
		if(p->right)
			obj.push(p->left);
	}
	return;
}
template<class T>
void binary_tree<T>::p_preorder1(node* root)
{
	if (!root)
		return;
	std::cout << root->data << " ";
	p_preorder1(root->left);//visit left node
	p_preorder1(root->right);//visit right node
}
template<class T>
void binary_tree<T>::p_inorder0(node* root)
{
	if (!root)
		return;
	std::stack<node*> obj;
	auto p = root;
	while (!obj.empty() || p)
	{
		if (p)//Push the node onto the stack for later traversal
		{
			obj.push(p);
			p = p->left;
		}
		else
		{
			p = obj.top();
			obj.pop();
			std::cout << p->data << " ";
			p = p->right;
		}
	}
}
template<class T>
void binary_tree<T>::p_inorder1(node* root)
{
	if (root->left)//have left child
		p_inorder1(root->left);
	std::cout << root->data << " ";
	if (root->right)
		p_inorder1(root->right);
}
template<class T>
void binary_tree<T>::p_postorder0(node* root)
{
	enum child_type{Left,Right};
	struct elem
	{
		node* pointer;
		child_type flag;
	};
	std::stack<elem> obj;
	auto p = root;
	elem q;
	while (!obj.empty() || p)
	{
		if (p)
		{
			q.pointer = p;
			q.flag = Left;
			obj.push(q);
			p = p->left;
		}
		else
		{
			q = obj.top();
			obj.pop();
			p = q.pointer;
			if (q.flag==Left)//Returning from left with right child
			{
				q.flag = Right;
				obj.push(q);
				p = p->right;
			}
			else
			{
				std::cout << p->data << " ";
				p = nullptr;
			}
		}
	}
}
template<class T>
void binary_tree<T>::p_postorder1(node* root)
{
	if (root->left)
		p_postorder1(root->left);
	if (root->right)
		p_postorder1(root->right);
	std::cout << root->data << " ";
}
template<class T>
void binary_tree<T>::p_levelorder(node* root)
{
	std::queue<node*> obj;
	obj.push(root);
	while (!obj.empty())
	{
		int sum = obj.size();
		while (sum--)
		{
			auto p = obj.front();
			obj.pop();
			std::cout << p->data << " ";
			if (p->left)
				obj.push(p->left);
			if (p->right)
				obj.push(p->right);
		}
	}
}

Tags: Algorithm data structure

Posted by tha_mink on Tue, 03 May 2022 20:11:07 +0300