C++ binary tree structure establishment and basic operations
- 2020-04-02 01:52:44
- OfStack
To prepare data
Define the variables and data needed for binary tree structure operations.
#define MAXLEN 20 //The maximum length
typedef char DATA; //Define the element type
struct CBTType //Define a binary tree node type
{
DATA data; //Element data
CBTType * left; //Pointer to the left subtree node
CBTType * right; //Pointer to the right subtree node
};
Defines the type DATA of the binary tree structure DATA element and the DATA structure CBTType of the binary tree structure. The node's specific DATA is stored in a sister DATA, while the pointer left is used to refer to the left subtree node, and the pointer right is used to point to the right subtree node
Initialize the binary tree
Initializes the binary tree and sets a node as the root of the binary tree.
CBTType * InitTree()
{
CBTType * node;
if(node = new CBTType) //Application memory
{
cout<<" Please enter a root node data first: "<<endl;
cin>>node->data;
node->left=NULL;
node->right=NULL;
if(node!=NULL) //If the binary tree node is not null
{
return node;
} else
{
return NULL;
}
}
return NULL;
}
First apply for a node, and then the user input the data of the root node, and the left subtree and the right subtree pointer set null, can complete the binomial tree initialization work.
To find the node
To find a node is to walk through each node in the binary tree, compare the data one by one, and return the pointer to the node where the data is located when the target data is found.
CBTType *TreeFindNode(CBTType *treeNode,DATA data)
{
CBTType *ptr;
if(treeNode==NULL)
{
return NULL;
}else
{
if(treeNode->data==data)
{
return treeNode;
}
else //Look up the left and right subtrees respectively; & have spent & have spent
{
if(ptr=TreeFindNode(treeNode->left,data)) //Left subtree recursive lookup
{
return ptr;
}
else if(ptr=TreeFindNode(treeNode->right,data)) //Right subtree recursive lookup
{
return ptr;
}
else
{
return NULL;
}
}
}
}
The input parameter treeNode is the root node of the binary tree to be searched, and the input parameter data is the node data to be searched. In the program, first determine whether the root node is null, and then determine whether it is root node according to the data, and then search to the left and right subtrees respectively, using recursive method to find, find the node, then return the corresponding pointer node; If all are not found, NULL is returned.
Add a node
Adding nodes is to add node data in the binary tree. When adding nodes, in addition to input node data, it is also necessary to specify the parent node, and the node added as a left or right subtree. Then set the node to the left or right subtree of its parent.
void AddTreeNode(CBTType *treeNode)
{
CBTType *pnode,*parent;
DATA data;
char menusel;
if(pnode=new CBTType) //Allocate memory
{
cout<<" Input binary tree node data: "<<endl;
cin>>pnode->data;
pnode->left=NULL; //Set the left subtree to be empty
pnode->right=NULL; //Set the left subtree to be empty
cout<<" Enter the parent data for the node "<<endl;
cin>>data;
parent=TreeFindNode(treeNode,data);//Find the parent node and get the node pointer
if(!parent)
{
cout<<" The parent was not found "<<endl;
delete pnode;
return ;
}
cout<<"1. Add the node to the left subtree; 2. Add the node to the right subtree. Please enter the corresponding number for the operation. "<<endl;
do
{
cin>>menusel;
if(menusel=='1'||menusel=='2')
{
switch(menusel)
{
case '1': //Add node to left subtree
if(parent->left) //The left subtree is not empty
{
cout<<" The left subtree is not empty "<<endl;
}
else
{
parent->left=pnode;
cout<<" Data added successfully! "<<endl;
}
break;
case '2': //Add node to right subtree
if(parent->right) //The right subtree is not empty
{
cout<<" The right subtree is not empty "<<endl;
}
else
{
parent->right=pnode;
cout<<" Data added successfully! "<<endl;
}
break;
default:
cout<<" Child node selection error!"<<endl;
break;
}
}
}while(menusel!='1'&&menusel!='2');
}
}
The input parameter treeNode is the root node of the binary tree. The program first request memory, and then by the user input binary tree node data, and set the left and right subtree as empty. Then specify its parent and set it to the left or right subtree.
Calculate the depth of the binary tree
To calculate the depth of binary tree is to calculate the maximum number of layers of nodes in the binary tree.
int TreeDepth(CBTType *treeNode)
{
int depleft,depright;
if(treeNode==NULL)
{
return 0; //When the node is empty, the depth is 0
}
else
{
depleft=TreeDepth(treeNode->left); //Left subtree depth (recursive call)
depright=TreeDepth(treeNode->right); //Right subtree depth (recursive call)
if(depleft)
{
return ++depleft;
}
else
{
return ++depright;
}
}
}
The input parameter treeNode is the root node of the binary tree to be calculated. First, the root node is judged to be empty, and then the left subtree depth and the right subtree depth are calculated respectively according to the recursive call, so as to complete the calculation of the entire binary tree depth.
Display node data
void ShowNodeData(CBTType *treeNode)
{
cout<<treeNode->data<<"t"; //Output node data directly
}
The input parameter is a pointer to the node to be displayed.
Empty the binary tree
To empty a binary tree is to turn the binary tree into an empty tree, which also needs to be implemented using a recursive algorithm.
void ClearTree(CBTType *treeNode)
{
if(treeNode) //Determines that the current tree is not empty
{
ClearTree(treeNode->left); //Empty the left subtree
ClearTree(treeNode->right); //Empty the right subtree
delete treeNode; //Release the memory occupied by the current node
}
}
The input parameter treeNode is the root node of the binary tree to be emptied. In the program, the left subtree, right subtree and root node are emptied recursively, and the memory space occupied by the node is freed to complete the emptying operation.
Traversing the binary tree
Traversing the binary tree is to find all nodes in the binary tree one by one. Here, in order to visually display the search results, the corresponding nodes will be output in the order of finding.
Iterating by level
Layer traversal is the most intuitive algorithm. Namely: first output the first layer is the root node, and then output the number of left and right children of the first node, that is, the second layer...... In this way, the loop processing, can be traversed layer by layer, layer by layer in order to output nodes from the top to the bottom, from left to right.
void LevelTree(CBTType *treeNode)
{
CBTType *p;
CBTType *q[MAXLEN]; //Define a queue
int head=0,tail=0;
if(treeNode) //If the header pointer is not null
{
tail=(tail+1)%MAXLEN; //Calculate the tail number of the circular queue
q[tail]=treeNode; //Binary root pointer into the queue
while(head!=tail)
{
head=(head+1)%MAXLEN; //Calculates the queue leader number of the circular queue
p=q[head]; //Gets the header element
ShowNodeData(p); //Outputs the header element
if(p->left!=NULL) //If there is a left subtree
{
tail=(tail+1)%MAXLEN; //Calculate the tail number of the queue
q[tail]=p->left; //Left sub tree joined the team
}
if(p->right!=NULL) //If there is a right subtree
{
tail=(tail+1)%MAXLEN; //Calculate the tail number of the queue
q[tail]=p->right; //Join the right subtree
}
}
}
}
The input parameter treeNode is the root node of the binary tree that needs to be traversed. In the whole process of processing, the program starts from the root node and gradually enters the nodes of each layer into the loop queue, and each loop outputs the data of the node at the head of the queue, and then enqueues its left and right subtrees. This cycle continues until all the data in the queue is output.
Order traversal first
An order-traversal algorithm is to access the root node, then the left subtree, and then the right subtree. The program can recursively traverse the left and right subtrees.
void DLRTree(CBTType *treeNode)
{
if(treeNode)
{
ShowNodeData(treeNode); //Display node content
DLRTree(treeNode->left); //Displays the contents of the left subtree
DLRTree(treeNode->right); //Displays the right subtree content
}
}
Middle order traversal algorithm
An order-traversal algorithm is to access the left subtree, then the root node, and then the right subtree. The program can recursively traverse the left and right subtrees.
void LDRTree(CBTType *treeNode)
{
if(treeNode)
{
LDRTree(treeNode->left); //Displays the contents of the left subtree & cake; & have spent & have spent
ShowNodeData(treeNode); //Display node content
DLRTree(treeNode->right); //Displays the right subtree content & cake; & have spent & have spent
}
}
Sequential traversal algorithm
An order-traversal algorithm is to access the left subtree, then the right subtree, and then the root node. The program can recursively traverse the left and right subtrees.
void LRDTree(CBTType *treeNode)
{
if(treeNode)
{
LRDTree(treeNode->left); //Displays the contents of the left subtree & cake;
DLRTree(treeNode->right); //Displays the right subtree content & cake; & have spent & have spent
ShowNodeData(treeNode); //Display node content
}
}
Complete code sample operation:
Add a header file to the file, then include all the above functions, and then write a main function:
#include<iostream>
using namespace std;
#define MAXLEN 20 //The maximum length
typedef char DATA; //Define the element type
struct CBTType / Define a binary tree node type
{
DATA data; //Element data
CBTType * left; //Pointer to the left subtree node
CBTType * right; //Pointer to the right subtree node
};
CBTType * InitTree()
{
CBTType * node;
if(node = new CBTType) //Application memory
{
cout<<" Please enter a root node data first: "<<endl;
cin>>node->data;
node->left=NULL;
node->right=NULL;
if(node!=NULL) //If the binary tree node is not null
{
return node;
} else
{
return NULL;
}
}
return NULL;
}
CBTType *TreeFindNode(CBTType *treeNode,DATA data)
{
CBTType *ptr;
if(treeNode==NULL)
{
return NULL;
}else
{
if(treeNode->data==data)
{
return treeNode;
}
else //Look up the left and right subtrees respectively; & have spent & have spent
{
if(ptr=TreeFindNode(treeNode->left,data)) //Left subtree recursive lookup
{
return ptr;
}
else if(ptr=TreeFindNode(treeNode->right,data)) //Right subtree recursive lookup
{
return ptr;
}
else
{
return NULL;
}
}
}
}
void AddTreeNode(CBTType *treeNode)
{
CBTType *pnode,*parent;
DATA data;
char menusel;
if(pnode=new CBTType) //Allocate memory
{
cout<<" Input binary tree node data: "<<endl;
cin>>pnode->data;
pnode->left=NULL; //Set the left subtree to be empty
pnode->right=NULL; //Set the left subtree to be empty
cout<<" Enter the parent data for the node "<<endl;
cin>>data;
parent=TreeFindNode(treeNode,data); //Find the parent node and get the node pointer
if(!parent)
{
cout<<" The parent was not found "<<endl;
delete pnode;
return ;
}
cout<<"1. Add the node to the left subtree; 2. Add the node to the right subtree. Please enter the corresponding number for the operation. "<<endl;
do
{
cin>>menusel;
if(menusel=='1'||menusel=='2')
{
switch(menusel)
{
case '1': //Add node to left subtree
if(parent->left) //The left subtree is not empty
{
cout<<" The left subtree is not empty "<<endl;
}
else
{
parent->left=pnode;
cout<<" Data added successfully! "<<endl;
}
break;
case '2': //Add node to right subtree
if(parent->right) //The right subtree is not empty
{
cout<<" The right subtree is not empty "<<endl;
}
else
{
parent->right=pnode;
cout<<" Data added successfully! "<<endl;
}
break;
default:
cout<<" Child node selection error!"<<endl;
break;
}
}
}while(menusel!='1'&&menusel!='2');
}
}
int TreeDepth(CBTType *treeNode)
{
int depleft,depright;
if(treeNode==NULL)
{
return 0; //When the node is empty, the depth is 0
}
else
{
depleft=TreeDepth(treeNode->left); //Left subtree depth (recursive call)
depright=TreeDepth(treeNode->right); //Right subtree depth (recursive call)
if(depleft)
{
return ++depleft;
}
else
{
return ++depright;
}
}
}
void ShowNodeData(CBTType *treeNode)
{
cout<<treeNode->data<<"t"; //Output node data directly
}
void ClearTree(CBTType *treeNode)
{
if(treeNode) //Determines that the current tree is not empty
{
ClearTree(treeNode->left); //Empty the left subtree
ClearTree(treeNode->right); //Empty the right subtree
delete treeNode; //Release the memory occupied by the current node
}
}
void LevelTree(CBTType *treeNode)
{
CBTType *p;
CBTType *q[MAXLEN]; //Define a queue
int head=0,tail=0;
if(treeNode) //If the header pointer is not null
{
tail=(tail+1)%MAXLEN; //Calculate the tail number of the circular queue
q[tail]=treeNode; //Binary root pointer into the queue
while(head!=tail)
{
head=(head+1)%MAXLEN; //Calculates the queue leader number of the circular queue
p=q[head]; //Gets the header element
ShowNodeData(p); //Outputs the header element
if(p->left!=NULL) //If there is a left subtree
{
tail=(tail+1)%MAXLEN; //Calculate the tail number of the queue
q[tail]=p->left; //Left sub tree joined the team
}
if(p->right!=NULL) //If there is a right subtree
{
tail=(tail+1)%MAXLEN; //Calculate the tail number of the queue
q[tail]=p->right; //Join the right subtree
}
}
}
}
void DLRTree(CBTType *treeNode)
{
if(treeNode)
{
ShowNodeData(treeNode); //Display node content
DLRTree(treeNode->left); //Displays the contents of the left subtree
DLRTree(treeNode->right); //Displays the right subtree content
}
}
void LDRTree(CBTType *treeNode)
{
if(treeNode)
{
LDRTree(treeNode->left); //Displays the contents of the left subtree
ShowNodeData(treeNode); //Display node content
DLRTree(treeNode->right); //Displays the right subtree content
}
}
void LRDTree(CBTType *treeNode)
{
if(treeNode)
{
LRDTree(treeNode->left); //Displays the contents of the left subtree
DLRTree(treeNode->right); //Displays the right subtree content
ShowNodeData(treeNode); //Display node content
}
}
int main()
{
CBTType *root=NULL; //Root is a pointer to a binary root node
char menusel;
//Set the root
root=InitTree();
//Add a node
do
{
cout<<" Please select the menu to add binary tree node: "<<endl;
cout<<"0. exit ;1. Add the nodes of the binary tree. "<<endl;
cin>>menusel;
switch(menusel)
{
case '1':
AddTreeNode(root);
break;
case '0':
break;
default:
cout<<"Add a nodeerror"<<endl;
break;
}
}while(menusel!='0');
//Output tree depth
cout<<"depth:"<<TreeDepth(root)<<endl;
//Output node content
do
{
cout<<" Please select the menu to traverse the binary tree and type 0 Means exit: "<<endl;
cout<<"1. According to the layer traversal "<<endl;
cout<<"2. The first sequence traversal DLR"<<endl;
cout<<"3. In the sequence traversal LDR"<<endl;
cout<<"4. After the sequence traversal LRD"<<endl;
cin>>menusel;
switch(menusel)
{
case '0':break;
case '1':
cout<<" Results of traversal by layer: "<<endl;
LevelTree(root);
cout<<endl;
break;
case '2':
cout<<" Results of first order traversal: "<<endl;
DLRTree(root);
cout<<endl;
break;
case '3':
cout<<" Results of middle order traversal: "<<endl;
LDRTree(root);
cout<<endl;
break;
case '4':
cout<<" Results of post-order traversal: "<<endl;
LRDTree(root);
cout<<endl;
break;
default:
cout<<" Traversal mode error! "<<endl;
break;
}
}while(menusel!='0');
//Empty binary tree & cake;
ClearTree(root);
return 0;
}
The corresponding tree structure is shown in the following figure:
< img Alt = "" border = 0 SRC =" / / files.jb51.net/file_images/article/201310/20131005124135953.png ">
Program operation interface:
< img Alt = "" border = 0 SRC =" / / files.jb51.net/file_images/article/201310/20131004213026531.png ">
< img Alt = "" border = 0 SRC =" / / files.jb51.net/file_images/article/201310/20131004213040265.png ">