experimental report
Experimental topic:
1. Establish a binary tree (enter the node value in the order of the order traversal).
2. Traverse the output binary tree in the first, middle, and rear sequences, respectively.
3. Establish a secondary linear two fork tree and establish a header to scan from the pointer.
First, demand analysis
1. Tip input information, the user enters the node value of the binary tree in the keyboard, with a space for separator, represents empty in -1 until the entire bifurcation is lost.
2. The execution command includes:
1) Establish a binary tree 2) First-order sequential traversal 3) 中 线 线 化 二 树 树 中 中 树 序
3. Test data:
Input data: 1, 2, 4, -1, -1, 5, -1, -1, 3, 6, -1, -1, 7, -1, -1
The established binary tree is:
1
2
3
4 5 6 7
Output Result: Preface: 1, 2, 4, 5, 3, 6, 7
Sentence: 4, 2, 5, 1, 6, 3, 7
Starting: 4, 5, 2, 6, 7, 3, 1
Second, summary design
The definition of the abstract data type binary tree is as follows:
ADT binarytree {
Data object D: D is a collection of data elements with the same feature.
Data relationship R: such as D = ф, then r = ф, said binarytree is an empty binary tree;
Such as D ≠ ф, r = {h}, h is the following binary relationship:
(1) There is a unique data element root called the root in D, which is unfolded under the relational H;
(2) If D- {root} ≠, there is D- {root} = {D1, DR}, and D1∩DR = ф;
(3) If D1 ≠ ф, there is a unique element X1 in D1.
1
> ∈H,
And there is D
1
On the relationship h
1
∈H; such as D
r
≠ ф, then D
r
There is a unique element X
r
,
R> ∈ h, and there is a relational HR on the DR is included in h; h = {
1>,
r
>, H
1
, H
r
}
;
(4) (D1, {H1}) is a binary tree that conforms to this definition, called the root of the right.
Basic operation P:
Initbitree (& T);
Operation result: Configuration of empty binary T.
Destroybitree (& T);
Initial conditions: the bifurcation T exists.
Operation result: Destroy the binary tree T.
CreateBithrtree (& T);
Operation Result: The first sequence is constructed in the binary tree T, LTAG and RTAG initially be set to LINK.
Preordertraverse (T);
Initial conditions: the bifurcation T exists.
Operation result: Sample recursive traversal T.
InorderTraverse (T);
Initial conditions: the bifurcation T exists.
Operation results: Single sequential recursive traversal T. PostOrDertraverse (T);
Initial conditions: the bifurcation T exists.
Operation results: The sequence is returned to traversal T.
Inorderthreading (& THRT, T);
Initial conditions: the bifurcation T exists.
Operation results: establish a header THRT and call inthreading (t); function.
INTHREADING (T);
Initial conditions: the bifurcation T exists.
Operation result: The secondary linearized binary tree T;
Inordertrasverse_thr (t);
Initial conditions: the bifurcation T exists.
Operation Result: The secondary scanned binary tree is scanned.
ADT BinaryTree
three. Specific algorithm implementation:
/ * Operation of the binary tree * /
#include
#include
/ *
// ******************************************************************************************************************************************************** ******
Typedef struct bitnode {
Int data;
BitNode * LCHILD, * RCHILD;
} BitNode, * bitree;
* /
// ******************************************************************************************************************************* ***
Typedef Enum PointerTag {link, thread};
Typedef struct bithode {
Int data;
Bithrnode * LCHILD, * RCHILD;
PointerTag LTAG, RTAG;
} Bithrnode, * bithrtree;
// ************************ Function prototype indicating ******************* ************
Void CreateBitree (Bithrtree & T);
Void PreordRraverse (Bithrtree T);
Void inorderTraverse (Bithrtree T);
Void PostRertraverse (Bithrtree T);
Void LevelopRertraverse (Bithrtree T);
Void inorderthreading (Bithrtree T, Bithrtree & thrt);
Void INTHREADING (Bithrtree P);
Void inordertrasverse_thr (Bithrtree T);
Bithrtree pre; // Make the pre-PRE to the pre-drive of the P, set to the global pointer
// ************************************************* *************
Void CreateBitree (Bithrtree & T) {// Establishing a binary tree
INT D;
Cin >> D;
IF (d == - 1) {
T = null; // Error
Return;
}
T = new bithode;
T-> DATA = D;
T-> LTAG = LINK;
T-> RTAG = LINK;
CreateBitree (T-> LCHILD);
CreateBitree (T-> rchild);
Return;
}
// **********************************************************************************
Void PreordRraverse (Bithrtree T) {// Senior sequence traversal tree
IF (t! = null) {
Cout <
Data << '';
Preordertraverse (T-> LCHILD);
Preordertraverse (T-> rchild);
}
}
Void inordertraverse (Bithrtree T) {// 中 中 二 二 二
IF (t! = null) {
Inordertraverse (T-> LCHILD);
Cout <
Data << '';
Inordertraverse (T-> rchild);
}
}
Void PostOrDraverse (Bithrtree T) {// Back sequence traversal
IF (t! = null) {
PostOrDertraverse (t-> lchild);
PostORDERTRAVERSE (T-> rchild);
Cout <
Data << '';
}
}
Void inorderthreading (Bithrtree T, Bithrtree & thrt) {// Established head node and call INTHREADING (T) function
THRT = new bithode; // Establish head node
IF (! t) return;
THRT-> LTAG = LINK;
THRT-> RTAG = Thread;
THRT-> rchild = thrt; // Right pointer back finger
If (! t) thrt-> lchild = thrt; // If the empty tree, the left pointer refers to finger
Else {
THRT-> LCHILD = T; // Left pointer points to T
Pre = thrt; // PRE can be set to global variables, always the pre-drive of the work pointer
INTHREADING (T); // 中序 线 化 Tree T
Pre-> rchild = thrt; // The right pointer of the last node points point knots
pre-> RTAG = Thread;
THRT-> rchild = pre; // head node's right pointer points to the last node
}
}
Void INTHREADING (Bithrtree P) {// 中 线 线
IF (p)
{
INTHREADING (P-> Lchild); // 中 线 线 化 子 树
IF (! p-> lchild)
{// front drive club
P-> ltag = thread;
P-> LCHILD = pre;
}
IF (! pre-> rchild)
{// follower clues
pre-> RTAG = Thread;
pre-> rchild = p;
}
pre = p; // Keep Pre point to PRE P
INTHREADING (P-> rchild); // Traine the right child
}
}
Void inordertRasverse_thr (Bithrtree T) {// 中 中 线 二 二 树
IF (! t) return;
Bithrtree P = T-> LCHILD; // P Point the left pointer to the head node, ie the root
While (p! = t) {
While (P-> LTAG == Link) // Look for the first node
P = P-> lchild;
Cout <
Data << '';
While (P-> RTAG == Thread && P-> rchild! = T)
{// follow the successful scan
P = P-> rChild;
Cout <
Data << '';
}
P = P-> rchild; // Scan the right tree
}
}
Void main () // main program, completing the call to the function
{
Bithrtree T, THRT;
CreateBitree (T);
Cout << "preface traversal:";
Preordertraverse (T);
Cout <
COUT << "中 sequence traversal:";
Inordertraverse (T); COUT <
Cout << "sequence traversal:";
PostOrDertraverse (T);
Cout <
Inorderthreading (T, THRT);
COUT << "Output Travel Tree:";
Inordertrasverse_thr (t);
Cout <
}
four. Debug analysis:
1. When the binary tree is traveled, the storage structure of the binary tree and the clue bifurcation is separated, and the data field in the binary tree cannot be transmitted into the line binary tree (two type pointers cannot be assigned each other). Two stored structures were compared, and the linear bifurches were more than two signs of LTAG, RTAG than the binary tree. So the two storage structures are combined into Bithrnode, and LTAG is placed in LTAG when establishing a binary tree. After the modification process is normal.
2. The algorithm used in this experiment report has a specific algorithm to demonstrate, and it is easy to implement, and there is no big problem in addition to the storage structure.
