Establishment and related operations of the binary tree
The establishment of the binary tree and its related operations are a considerable content in the data structure discipline. It is also a very wide range of classic structures. This paper has introduced to everyone through five large modules: establishing a binary tree, three-order traversal trigeshing tree, give Out of the leaf node, show the binary tree, destroy the binary tree. The whole process. I hope that everyone only has a deep understanding of this part. We designed a demo program for abstract data type binary tree in the article. The function definition of the program is such: Design to implement the basic operations such as ADT Bitree's Create, Traverse, INSERT, DELETE; Design Operational Application Interface: The data to be processed is a character pattern, typed in the process; the subroutine that needs to be created The algorithm is as follows: [1] Create a binary tree; [2] gives the junction sequence (character data) after traversing the tree; [3] gives the leaf node (character data); [4] Show two fork; [ 5] Clean up space; [6] The optional menu is given in the main program:
1.create binary tree from keyboard;
2.create binary tree from file;
3.Write Tree Data to File;
4.preorder travel;
5.inorder Travel
6.POSTORDER TRAVEL
7.SHOW Leaves
8.Display the structure of the binary tree
9. Clear Binary Tree Data
10.exit
Problem design and overall design This question is divided into five large modules: establish a binary tree, traversed the binary tree, give the leaf node, show the binary tree, destroy the binary tree. Which function module is executed by the menu. Detailed Design 1, create the second-fork tree from the keyboard to create, and enter the data, enter the data of each node by the keyboard. When entering "#", the currently operated node pointer is NULL, using the first left child The sequence function of the right subtree after the tree generates the corresponding binary tree structure according to the input data. 2. Establish a binary tree from the document 3, and the three-order traversal is used to traverse the binary tree in the order, order, and rear sequence, respectively. 4. Out of the leaves node gives the leaves node, which can be carried out in an algorithm of any traversal. If the left child and the right child of a node do not exist, then this node is the leaves node of the binary tree. 5. Displaying the binary tree program uses a spatial structure of the binary tree in a graphic mode, and uses the algorithm of the hierarchy to hierarchically access each node, and calculate the corresponding screen coordinates to display the binary tree. 6. The empty binary tree uses the back sequence to translate the emptying operation of the binary tree. The data sequence in the test data input or file is: ABC ## d ## e # f ## predecessor traversal: abcdef Sub-sequence traversal: CBDAef sequence traversal: CDBFEA Display Leaf Node: The space structure of the binary tree is shown below in CDF graphics mode.
Program brief instructions You must establish a binary tree before using a binary tree. The way to establish can be directly input. You must be read from the file, but you must first create, if you want to continue your binary tree, otherwise the program will prompt the error. The user only needs to do it according to the prompt, please refer to the test data in the input format of the data. The program source code is provided:
#include
#include
#include
#include
#include
#include
#define overflow -2
#define r 10
File * fp = null;
Char filename [20];
Int max
Int A,
INT B)
{
RETURN A> B? A: B;
}
Struct Bintreenode
{
CHAR DATA;
Bintreenode * lchild, * rchild;
INT LEFT, TOP, Right, Bottom, Ox, Oy;
}
Struct Leavesptrnode
{
Bintreenode * Leavesptr;
Leavesptrnode * Next;
}
Struct DrawingQueue
{
Leavesptrnode * phead, * ptail;
Int length;
}
Void PostOrder (bintreenode * t,
Void (* VISIT) (Bintreenode *));
Void Visit (bintreenode * t)
{
IF (t) PR
INTF ("% C", t-> data);
}
Void deleteNode (bintreenode * t)
{
IF (t) free (t);
}
Void WriteDataTOfile (Bintreenode * T)
{
IF (t)
{
PUTC (T-> DATA, FP);
WriteDataTofile (T-> LCHILD);
WriteDataTofile (T-> rchild);
}
Else
PUTC ('#', fp);
}
Char InputFromKeyboard ()
{
Return getChe ();
}
Char InputFromFile ()
{
Return Getc (FP);
}
Void createbintree (bintreenode ** t,
Char (* inoperation) ())
{
CHAR CH;
CH = inoperation ();
IF (ch == '#')
* t = null;
Else
{
* t = (bintreenode *) malloc (sizeof (bintreenode));
IF (! * t)
EXIT (OVERFLOW);
(* T) -> DATA = CH;
Createbintree (& (* T) -> LCHILD, INOPERATION
CreateBintree (& (* T) -> rchild, inoperation);
}
}
Void deleteb
Intree (Bintreenode * T)
{
PostORDER (T, DELETENODE);
}
Void Preorder (bintreenode * t,
Void (* visit) (bintreenode * t))
{
IF (t)
{
Visit (T);
Preorder (T-> Lchild, Visit);
Preorder (T-> rchild, visit);
}
}
Void inorder (bintreenode * t,
Void (* visit) (bintreenode * t))
{
IF (t)
{
Inorder (T-> LCHILD, VISIT);
Visit (T);
Inorder (t-> rchild, visit);
}
}
Void PostOrder (bintreenode * t,
Void (* visit) (bintreenode * t))
{
IF (t)
{
PostORDER (T-> LCHILD, VISIT);
PostORDER (T-> rchild, visit);
Visit (T);
}
}
Void setContent (bintreenode * t,
IOX,
IOY)
{
T-> ox = IOX;
T-> = iy;
T-> LEFT = IOX-R; T-> TOP = IOY-R;
T-> Right = IOX R;
T-> Bottom = IOY R;
}
Void Drawleaves (Bintreenode * T)
{
Circle (T-> OX, T-> OY, R);
Char s [2];
s [0] = T-> DATA;
S [1] = '/ 0';
Outtextxy (T-> OX-3, T-> OY-3, S);
}
Void Connectleaves (Bintreenode * T1, Bintreenode * T2)
{
Line (t1-> ox, t1-> bottom, t2-> ox, t2-> TOP);
}
int Getb
INTREEHEIGHT (Bintreenode * T)
{
IF (t == null)
Return 0;
Else
Return 1 Max (Getb
INTREEHEIGHT (T-> LCHILD), Getb
INTREEHEIGHT (T-> rchild);
}
Void InitQueue (DrawingQueue * qu)
{
QU-> PHEAD = qu-> ptail = null;
QU-> length = 0;
}
Void Enqueue (DrawingQueue * qu, bintreenode * t)
{
Leavesptrnode * p = null;
p = (LeavesPtrNode *) Malloc (SizeOf (LeavesPtrNode);
P-> Leavesptr = T;
P-> Next = NULL;
IF (qu-> length == 0)
{
QU-> ptail = qu-> PHEAD = P;
}
Else
{
QU-> ptail-> next = p;
QU-> ptail = qu-> ptail-> next;
}
QU-> Length ;
}
Void Dequeue (DrawingQueue * qu, bintreenode ** t)
{
Leavesptrnode * p = qu-> PHEAD;
IF (qu-> length == 0)
{
* t = null;
Return;
}
IF (qu-> length == 1)
QU-> PHEAD = qu-> ptail = null;
Else
QU-> PHEAD = qu-> PHEAD-> NEXT;
* T = P-> Leavesptr;
Free (p);
QU-> Length--;
}
Void DrawTree (bintreenode * t,
Int treewidth,
Int rootx,
Int rooty
{
INT Currentlevelleaves = 0, NextLevelleaves = 0, Distance, Currentlevel = 0;
Int nextlevelStartx, Next Delevely;
Bintreenode * Pleaves;
Drawingqueue queue;
INITQUEUE (& queue);
Enqueue (& queue, t);
SetContent (t, rootx, rooty);
Currentlevelleaves ;
Currentlevel ; // Currentlevel = 1;
While (queue.length> 0)
{
Distance = TreeWidth / Pow (2, Currentlevel-1);
Nextlevel = rooty 2 * (2 * currentlevel) * 2 * r;
While (Currentlevelleaves> 0)
{
DEQUEUE (& Queue, & pleaves);
Drawleaves (pleaves);
//Pr
INTF ("% C", plevels-> data);
IF (Pleaves-> LCHILD! = NULL)
{
SetContent (Pleaves-> Lchild, Pleaves-> OX-DISTANCE / 2, NextLELY);
Connectleaves (Pleaves, Pleaves-> Lchild);
Enqueue (& queue, pletenances-> lchild);
Nextlevelleaves ;
}
IF (Pleaves-> rchild! = null)
{
SetContent (Pleaves-> rchild, pletenances-> ox distance / 2, nextlevel);
Connectleaves (Pleaves, Pleaves-> rchild);
Enqueue (& Queue, pleveles-> rchild);
Nextlevelleaves ;
}
Currentlevelleaves -;
}
CurrentlevelleVes = nextlevelleaves;
Nextlevelleaves = 0;
Currentlevel ;
}
}
void main ()
{
Int treewidth, Treeheight, LogicalHeight, rootx, rooty, choice
INT driver = detect, mode;
Bintreenode * proot = null;
While (1)
{
Printf ("/ n1.create binary tree from keyboard / n");
Printf ("2.Create Binary Tree from File / N");
Printf ("3.Write Tree Data To File / N);
Printf ("4.preorder travel / n");
Printf ("5.inorder Travel / N");
Printf ("6.postorder travel / n");
Printf ("7.Show Leaves / N);
Printf ("8.display the
Structure of the binary tree / n ");
Printf ("9. Clear Binary Tree Data / N");
Printf ("10.exit / n");
Printf ("Please select an Opertation:");
Scanf ("% d", & choice);
Switch (choice)
{
Case 1:
IF (ProOT)
Deletebintree (ProT);
Createbintree (& ProT, InputFromKeyboard);
Printf ("CREATE TREE OK / N");
Break;
Case 2:
PRINTF ("" "");
Scanf ("% s", filename);
fp = fopen (filename, "rt"); if (! fp)
{
Printf ("can not open sudh file / n");
Break;
}
IF (ProOT)
Deletebintree (ProT);
CreateBint, InputFromFile;
Fclose (fp);
Printf ("Read File OK / N");
Break;
Case 3:
IF (! ProOT)
{
Printf ("Tree Is Not Created / N);
Break;
}
Printf ("" please input the dest file name: ");
Scanf ("% s", filename);
FP = fopen (filename, "wt");
IF (! fp)
{
Printf ("can not open sudh file / n");
Break;
}
WriteDataTofile (ProT);
Fclose (fp);
Printf ("WRITE FILE OK / N");
Break;
Case 4:
IF (! ProOT)
{
Printf ("Tree Is Not Created / N);
Break;
}
Preorder (ProT, Visit);
Break;
Case 5:
IF (! ProOT)
{
Printf ("Tree Is Not Created / N);
Break;
}
Inorder (ProT, Visit);
Break;
Case 6:
IF (! ProOT)
{
Printf ("Tree Is Not Created / N);
Break;
}
PostORDER (ProT, Visit);
Break;
Case 7:
Break;
Case 8:
IF (! ProOT)
{
Printf ("The Tree Is Not Created! / N");
Break;
}
LogicalHeight = getBintreeHeight (Proot);
TreeWidth = 2 * r * (POW (2, LogicalHeight-1) * 2-1);
Treeheight = 2 * r * (2 * logicalHeight-1);
IF (TreeWidth> 639 || TreeHeight> 479)
{
Printf ("Sorry, The Tree Is Too Big To Be Dispeyed! / N");
Break;
}
INITGRAPH (& Driver, & Mode, "..// bgi");
Rootx = (getmaxx () 1) / 2;
Rooty = (GetMaxY () 1-TreeHeight) / 2;
DrawTree (ProT, TreeWidth, Rootx, Rooty);
Getch ();
Closegraph ();
Break;
Case 9:
IF (! ProOT)
{
Printf ("Tree Is Not Created / N);
Break;
}
Deletebintree (ProT);
Proot = NULL;
Break;
Case 10:
IF (ProT! = null) deletebintree (ProT);
exit (0);
}
}
}
