The book picks up where the previous one left off, today with a hands-on approach to realizing the tree on your own.
I believe that through the previous chapters of the study, you have understood what the tree is, today we focus on binary trees, respectively, using sequential storage and chained storage to realize the tree.
01, Array Realization
We said in the previous section that if we number each node sequentially from the top of the tree from top to bottom, left to right, with the root node being 1 as the start, then there is node number i, its left child node is numbered 2i, and its right child node is numbered 2i+1. However, we know that indexing of arrays starts from 0. Therefore, if we implement the binary tree with arrays, then we can change the numbering above to starting from 0. Hence the following conclusion can be obtained:
Node number: i;
Its left child node number: 2i+1;
Its right child node number: 2i+2;
1、Initialization Init
Initialization mainly specifies the tree node capacity and creates an array of the specified capacity.
//Initialize the tree to the specified capacity
public MyselfTreeArray<T> Init(int capacity)
{
// Initialize an array of the specified length to hold the tree node elements
_array = new T[capacity]; // Return the tree.
// Return the tree.
return this.
}
2、Get the number of tree nodes Count
The number of tree nodes can be obtained directly from the internal array length.
//Number of tree nodes
public int Count
{
get
{
return _array.Length;
}
}
3, get the node index GetIndex
Getting the node index is mainly for converting the node value to an indexed value, because we are using an array implementation, and the operation of the element relies more on the index. In fact, we have other options to deal with the way to get the index, such as through the design of the element object so that it contains the index field, which is actually more convenient to operate. Below we still use the most direct access to the method as a demonstration.
//Return the index of the specified data
public int GetIndex(T data)
{
if (data == null)
{
if (data == null) { return -1; }
}
// Find the index by value
return (_array, data);
}
4. Calculate the parent node index CalcParentIndex
This method is used to implement the calculation of the parent node index by the child node index, regardless of the left child node or the right child node, using one of the following formulas will be enough, the code is as follows:
//Calculate the parent node index according to the child index
public int CalcParentIndex(int childIndex)
{
// Apply the formula to calculate the parent node index
var parentIndex = (childIndex + 1) / 2 - 1; // Check if the index is out of bounds.
// Check if the index is out of bounds
if (childIndex <= 0 || childIndex >= _array.Length
|| parentIndex < 0 || parentIndex >= _array.Length)
{
return -1; }
}
// Return the index of the parent node
return parentIndex; }
}
5. Calculate the left child node index CalcLeftChildIndex
This method is used to compute the left child node index based on the parent node index.
//Calculate the left child node index according to the parent node index
public int CalcLeftChildIndex(int parentIndex)
{
//Apply the formula to calculate the left child index
var leftChildIndex = 2 * parentIndex + 1; //Check if the index is out of bounds.
// Check if the index is out of bounds
if (leftChildIndex <= 0 || leftChildIndex >= _array.Length
|| parentIndex < 0 || parentIndex >= _array.Length)
{
return -1; }
}
// Return the left child index
return leftChildIndex;
}
6. Calculate the right child node CalcRightChildIndex
This method is used to compute the right child node index based on the parent node index.
//Calculate the right child node index according to the parent node index
public int CalcRightChildIndex(int parentIndex)
{
//Apply the formula to calculate the right child index
var rightChildIndex = 2 * parentIndex + 2; //Check if the index is out of bounds.
// Check if the index is out of bounds
if (rightChildIndex <= 0 || rightChildIndex >= _array.Length
|| parentIndex < 0 || parentIndex >= _array.Length)
{
return -1; }
}
// Return the right child index
return rightChildIndex;
}
7. Get node value Get
This method gets the node value by node index and reports an error if the index is out of bounds.
// Get the node value through the node index
public T Get(int index)
{
// Check if the index is out of bounds
if (index < 0 || index >= _array.Length)
{
throw new IndexOutOfRangeException("Invalid index");;
}
// Return the node value
return _array[index];
}
8, get the value of the left child node GetLeftChild
This method is to get its left node value by node index, first get the left child node index, then get the left child node value.
// Get the value of its left child node through the node index
public T GetLeftChild(int parentIndex)
{
//Get the left child node index
var leftChildIndex = CalcLeftChildIndex(parentIndex);
// Check if the index is out of bounds
if (leftChildIndex < 0)
{
throw new IndexOutOfRangeException("Invalid index");;
}
// Return the left child node value
return _array[leftChildIndex];
}
9, get the value of the right child node GetRightChild
This method is to get the right node value of a node by its node index, first getting the right child node index and then the right child node value.
// Get the value of its right child node through the node index
public T GetRightChild(int parentIndex)
{
//Get the right child node index
var rightChildIndex = CalcRightChildIndex(parentIndex);
// Check if the index is out of bounds
if (rightChildIndex < 0)
{
throw new IndexOutOfRangeException("Invalid index");;
}
// Return the right child node value
return _array[rightChildIndex];
}
10, add or update the node value AddOrUpdate
This method adds or updates a node value by node index, because the array is initialized with a default value, so adding or updating a node value is a direct assignment to an array element, and an error is reported if the index is out of bounds.
// Add or update the node value through the node index
public void AddOrUpdate(int index, T data)
{
// Check if the index is out of bounds
if (index < 0 || index >= _array.Length)
{
throw new IndexOutOfRangeException("Invalid index");;
}
// Update the value
_array[index] = data;
}
11, add or update the value of the left child node AddOrUpdateLeftChild
This method adds or updates the value of its left child node according to the node value, first find its index through the node value, then calculate its left child node index through its index, and directly update the value of the left child node after the index check is successful.
// Add or update the left child node value through the node value
public void AddOrUpdateLeftChild(T parent, T left)
{
//Get the node index
var parentIndex = GetIndex(parent);
// Get the left child node index
var leftChildIndex = CalcLeftChildIndex(parentIndex);
// Check if the index is out of bounds
if (leftChildIndex < 0)
{
throw new IndexOutOfRangeException("Invalid index");;
}
// Update the value
_array[leftChildIndex] = left;
}
12, add or update the value of the right child node AddOrUpdateRightChild
This method adds or updates the value of its right child node according to the node value, firstly, it finds its index through the node value, then it calculates its right child node index through its index, and after the index check is successful, it directly updates the right child node value.
// Add or update the right child node value through the node value
public void AddOrUpdateRightChild(T parent, T right)
{
//Get the node index
var parentIndex = GetIndex(parent);
// Get the left child node index
var rightChildIndex = CalcRightChildIndex(parentIndex);
// Check if the index is out of bounds
if (rightChildIndex < 0)
{
throw new IndexOutOfRangeException("invalid index");;
}
// Update the value
_array[rightChildIndex] = right;
}
13. Delete node and all its descendants Remove
This method deletes itself as well as all of its descendants by node index, and deleting a descendant node requires that the left and right child nodes recursively call the method itself, respectively.
//Delete the node and all its descendants through the node index
public void Remove(int index)
{
//Illegal indexes are skipped directly
if (index < 0 || index >= _array.Length)
{
return;
}
//clear node values
_array[index] = default;
// Get the left child node index
var leftChildIndex = CalcLeftChildIndex(index);
// Recursively remove the left child node and all its descendants
Remove(leftChildIndex); //remove the left child node and all its descendants.
//Get the right child index
var rightChildIndex = CalcRightChildIndex(index);
//Recursively remove the right child node and all its descendants
Remove(rightChildIndex); //Delete the right child node and all its descendants recursively.
}
14. Remove the left node and all its descendants RemoveLeftChild
This method deletes its left node and all descendant nodes of its left node by node value. First, it obtains the node index by node value, then calculates the left child node index, and finally completes the deletion by calling the Remove node Remove method.
//Delete its left node and all its descendants by node value
public void RemoveLeftChild(T parent)
{
//Get the node index
var parentIndex = GetIndex(parent);
// Get the left child node index
var leftChildIndex = CalcLeftChildIndex(parentIndex);
// Check if the index is out of bounds
if (leftChildIndex < 0)
{
throw new IndexOutOfRangeException("Invalid index");;
}
// Remove the left child node and all its descendants
Remove(leftChildIndex);
}
15. Remove the right node and all its descendants RemoveRightChild
This method deletes its right node and all the descendant nodes of its right node by the node value. First, it gets the node index by the node value, then calculates the right child node index, and finally completes the deletion by calling the Remove node Remove method.
//Delete the right node and all its descendants by node value
public void RemoveRightChild(T parent)
{
//Get the node index
var parentIndex = GetIndex(parent);
//Get the right child node index
var rightChildIndex = CalcRightChildIndex(parentIndex);
// Check if the index is out of bounds
if (rightChildIndex < 0)
{
throw new IndexOutOfRangeException("Invalid index");;
}
// Remove the right child node and all its descendants
Remove(rightChildIndex);
}
16、Pre-order traversal PreOrderTraversal
The core idea of a preorder traversal is to print the root node of the tree first, then the left subtree of the tree, and finally the right subtree of the tree.
//Pre-Order Traversal
public void PreOrderTraversal(int index = 0)
{
//Illegal index directly skip
if (index < 0 || index >= _array.Length)
{
return;
}
//print
(_array[index]).
// Get the left child index
var leftChildIndex = CalcLeftChildIndex(index);
// Print the left child tree
PreOrderTraversal(leftChildIndex);
//Get the right child index
var rightChildIndex = CalcRightChildIndex(index);
//print the right child tree
PreOrderTraversal(rightChildIndex);; //Print the right child tree.
}
17、Middle order traversal InOrderTraversal
The core idea of a mid-order traversal is to print the left subtree of the tree first, then the root node of the tree, and finally the right subtree of the tree.
//Middle order traversal
public void InOrderTraversal(int index = 0)
{
//Illegal index directly skip
if (index < 0 || index >= _array.Length)
{
return;
}
// Get the left child index
var leftChildIndex = CalcLeftChildIndex(index);
// Print the left child tree
InOrderTraversal(leftChildIndex);
//print
(_array[index]).
// Get the right child index
var rightChildIndex = CalcRightChildIndex(index);
//print the right child tree
InOrderTraversal(rightChildIndex);
}
18、Post-order traversal PostOrderTraversal
The core idea of a backward traversal is to print the left subtree of the tree first, then the right subtree of the tree, and finally the root node of the tree.
//post-order traversal
public void PostOrderTraversal(int index = 0)
{
//Illegal index directly skip
if (index < 0 || index >= _array.Length)
{
return;
}
// Get the left child index
var leftChildIndex = CalcLeftChildIndex(index);
// Print the left child tree
PostOrderTraversal(leftChildIndex);
//Get the index of the right child node
var rightChildIndex = CalcRightChildIndex(index);
//print the right child tree
PostOrderTraversal(rightChildIndex); //print the right child tree.
//print
(_array[index]);
}
19, level traversal LevelOrderTraversal
The core idea of hierarchical traversal is that with the help of a queue, starting from the root node, from top to bottom, from left to right, first into the queue and wait for the subsequent printing, and then out of the queue immediately after the printing, and at the same time the left and right child nodes of this node are added to the queue in order, and the cycle repeats itself until the completion of the printing of all the elements.
//level traversal
public void LevelOrderTraversal()
{
//create a queue for hierarchical traversal
var queue = new Queue<int>();
// First put the root node index 0 into the queue
(0);
// Keep processing as long as there are values in the queue
while ( > 0)
{
// out of the queue, take out the first node index
var currentIndex = ();
//print the first node value
(_array[currentIndex]); //Print the first node value.
// Get the left child node index
int leftChildIndex = CalcLeftChildIndex(currentIndex);
// If the left child node exists, add its index to the queue
if (leftChildIndex >= 0)
{
(leftChildIndex);
}
// Get the right child node index
int rightChildIndex = CalcRightChildIndex(currentIndex);
// If the right child node exists, add its index to the queue
if (rightChildIndex >= 0)
{
(rightChildIndex);
}
}
}
02Chained Table Implementation
Chained table implementation of the generality will be stronger, basically can realize all the tree structure, while the operation is also more convenient, the following we are still binary tree implementation as an example of the demonstration.
1、Initialize tree root node InitRoot
Before initializing the root node of the tree, you need to define the nodes of the chain table, which contains the data field and the left and right child nodes, as well as maintaining the root node and the number of nodes as two private fields in the tree species.
public class MyselfTreeNode<T>
{
//data domain
public T Data { get; set; }
////left child node (math.)
public MyselfTreeNode<T> Left { get; set; }
//right child node (math.)
public MyselfTreeNode<T> Right { get; set; }
public MyselfTreeNode(T data)
{
Data = data;
Left = null;
Right = null;
}
}
public class MyselfTreeLinkedList<T>
{
//root node
private MyselfTreeNode<T> _root;
//Number of tree nodes
private int _count;
//初始化树root node
public MyselfTreeLinkedList<T> InitRoot(T root)
{
_root = new MyselfTreeNode<T>(root);
//Number of tree nodes加1
_count++;
//Return to the tree
return this;
}
}
2、Get the number of tree nodes Count
The number of tree nodes can be returned directly via the private field _count.
//Get the number of tree nodes
public int Count
{
get
{
return _count; }
}
}
3、Get the root node Root
The root node can be returned directly via the private field _root.
//Get the root node
public MyselfTreeNode<T> Root
{
get
{
return _root;
}
}
4. Add or update the value of the left child node AddOrUpdateLeftChild
This method is used by the node to add or update its left child value.
// Add or update the left child node value by specifying the node
public void AddOrUpdateLeftChild(MyselfTreeNode<T> parent, T left)
{
if ( ! = null)
{
// change the node value
= left; return; // change the node value.
return.
}
// Add node
= new MyselfTreeNode<T>(left);
// Add 1 to the number of nodes
_count++;
}
5. Add or update the value of the right child node AddOrUpdateRightChild
This method is used by the node to add or update its right child value.
// Add or update the right child element by specifying the node
public void AddOrUpdateRightChild(MyselfTreeNode<T> parent, T right)
{
if ( ! = null)
{
// change the node value
= right; return; //More node values.
return.
}
// Add the node
= new MyselfTreeNode<T>(right);
// Add 1 to the number of nodes
_count++;
}
6. Delete nodes and their descendants Remove
This method deletes itself and all its descendants through the node, which requires recursive deletion of the left and right child nodes and all their descendants.
// Delete the node and its descendants by specifying the node
public void Remove(MyselfTreeNode<T> node)
{
if ( ! = null)
{
// Recursively remove all descendants of the left child node
Remove();
}
if ( ! = null)
{
// Recursively remove all descendants of the right child node
Remove();
}
// Remove the node
= default;
//Number of nodes minus 1
_count--;
}
7、Pre-order traversal PreOrderTraversal
The core idea is the same as the array implementation.
//Pre-Order Traversal
public void PreOrderTraversal(MyselfTreeNode<T> node)
{
//print
();
if ( ! = null)
{
//print the left subtree
PreOrderTraversal();
}
if ( ! = null)
{
// Print the right subtree
PreOrderTraversal();
}
}
8, in order traversal InOrderTraversal
The core idea is the same as the array implementation.
//Middle order traversal
public void InOrderTraversal(MyselfTreeNode<T> node)
{
if ( ! = null)
{
// Print the left subtree
InOrderTraversal();
}
//print
();
if ( ! = null)
{
//print the right subtree
InOrderTraversal();
}
}
9、Post-order traversal PostOrderTraversal
The core idea is the same as the array implementation.
// Post-order traversal
public void PostOrderTraversal(MyselfTreeNode<T> node)
{
if ( ! = null)
{
// Print the left subtree
PostOrderTraversal();
}
if ( ! = null)
{
// Print the right subtree
PostOrderTraversal();
}
//print
();
}
10, level traversal LevelOrderTraversal
The core idea is the same as the array implementation.
//level traversal
public void LevelOrderTraversal()
{
//create a queue for hierarchical traversal
Queue<MyselfTreeNode<T>> queue = new Queue<MyselfTreeNode<T>>();
// Queue the root node first
(_root);
// Keep processing as long as there are values in the queue
while ( > 0)
{
// out of the queue, take out the first node
var node = ();
//print the first node value
(); // Print the first node value.
// If the left child node exists add it to the queue
if ( ! = null)
{
();
}
// Add the right child to the queue if it exists
if ( ! = null)
{
();
}
}
}
classifier for sums of money: The test method code as well as the sample source code have been uploaded to the code repository for those who are interested./hugogoos/Planner