Experiment four trees
First, the experimental purpose
1. Familiar with the chain storage structure of the binary tree. Master the establishment of the binary tree, the depth priority recursive traversal. Can use the traversal algorithm to implement some application II, experimental content
1. It is known that the binary tree is stored in the binary chain table, writing a algorithm to exchange all left and right subtots of the binary tree, that is, the left child of the node goes into the right child of the node, and the right tree becomes a left sub-tree. (Folder: exercise 12_14)
//
The structural type definition of the two-doxia table
.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 ()
{
CHAR 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
/ / Output according to the sequence sequence
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 << "
}
}
}
// Exchange left and right bonus. H
Void Swap (Bitree * R)
{
Bitree * p;
IF (r == null) return;
P = r-> lchild;
R-> lchild = r-> rChild;
R-> rChild = P;
SWAP (r-> lchild);
SWAP (r-> rchild);
Return;
}
/ / Exchange the main program file of the left and right bonus .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 "exchange left and right bon trees .h"
Using namespace std;
int main ()
{
Bitree * Pb;
PB = CREATTREE ();
Preorder (PB);
Cout << Endl;
SWAP (PB);
Preorder (PB);
Cout << Endl;
System ("pause");
Return 0;
}
