Experiment four trees
First, the experimental purpose
1. Familiar with the chain storage structure of the binary tree
2. Master the establishment of the binary tree, depth priority recursive traversal, etc.
3. Can use the traversal algorithm to implement some applications
Second, the experiment content
2. A binary tree is stored in a binary table structure to prepare an algorithm to delete the node of the data value of the binary tree and its subtree, and output the deleted subtree. (Folder: exercise 12_15)
// The structural type of the binary table is defined .h
Const int maxSize = 1024;
Typedef char dattype;
Typedef struct node
{
DataType Data;
Struct Node * LCHILD, * RCHILD;
} bitree;
// bifurcation of binary tree. H
Bitree * creatree ()
{
DataType ch;
Bitree * q [MaxSize];
Int Front, REAR;
Bitree * root, * s;
Root = NULL;
Front = 1; REAR = 0;
While (ch = getchar ())! = '#')
{
s = NULL;
IF (ch! = '@')
{
s = new bitree;
S-> DATA = CH;
S-> LCHILD = NULL;
S-> rChild = null;
}
REAR ;
Q [REAR] = S;
IF (REAR == 1) root = s;
Else
{
IF (S && Q [Front])
IF (Rear% 2 == 0) q [Front] -> LCHILD = S;
Else Q [Front] -> rChild = S;
IF (Rear% 2 == 1) Front ;
}
}
Return root;
}
// binary tree output .h
#include
#include
#include
Using std :: cout;
Void Preorder (Bitree * P)
{
IF (p! = null)
{
Cout << p-> data;
IF (p-> lchild! = null || P-> rchild! = null)
{
Cout << "(";
Preorder (P-> LCHILD);
IF (p-> rchild! = null) cout << ";
Preorder (P-> rchild);
Cout << "
}
}
}
/ / Remove the main program file of the binary nodes .cpp
#include
#include
#include
#include "The structural type of the two-forked list is defined .h"
#include "the establishment of the binary tree. H"
#include "Output of the binary tree. H"
#include "Delete Node and Sub Tree .h"
Using std :: cin;
Using std :: cout;
Using std :: end1;
int main ()
{
Bitree * root;
DataType X;
Cout << "Please enter the node of the binary tree. According to the sequence sequence input, enter" @ "indicate the node is empty, enter" # "End Enter:" << Endl; root = Creattree ();
Preorder (root);
Cout << Endl;
Cout << "Please enter the sub-tree node that you want to delete:" << Endl;
CIN >> X;
Root = delsubtree (root, x);
Cout << "The binary tree after deleting the subtree is:" << Endl;
Preorder (root);
Cout << Endl;
System ("pause");
Return 0;
}
/ / Delete the node and the subtree .h
#include
#include
#include
Void Destroy (Bitree * R);
Bitree * Delsubtree (Bitree * root, DataType X)
{
IF (root! = null)
{
Root-> lchild = delsubtree (root-> lchild, x);
Root-> rchild = delsubtree (root-> rchild, x);
IF (root-> data == x)
{
DESTROY (root);
Return NULL;
}
Else
{
Return root;
}
}
Else
{
Return root;
}
}
Void Destroy (Bitree * R)
{
IF (r! = null)
{
DESTROY (R-> LCHILD);
DESTROY (r-> rchild);
Delete R;
}
}
