Java realizes the establishment of binary tree calculation height and recursive output operation example
- 2021-07-06 11:00:10
- OfStack
In this paper, an example of Java is given to realize the establishment of 2-tree, the calculation of height and the recursive output operation. Share it for your reference, as follows:
1. Establish recursive output to calculate three non-recursive outputs before, during and after height
public class Tree_Link {
private int save = 0;
private int now = 0;
Scanner sc = new Scanner(System.in);
/*
* Constructor
*/
Tree_Link(){
}
/*
* Establishment of linked list
*/
public Tree Link_Build(Tree head){
// Tree head = new Tree();// Head node
System.out.println(" Continue code : 1");
int flag = sc.nextInt();
if(flag != 1){
return head;
}else{
System.out.println("\n\n\n Input Node information: ");
head.SetCode(sc.nextInt());
System.out.println("\n Establish Left Subtree code : 1 Otherwise: 0");
flag = sc.nextInt();
if(flag == 1){
now++;
Tree LTree = new Tree();
head.SetLtree(LTree);
LTree.SetFronttree(head);// Set Parent Node
Link_Build( head.GetLtree() );
}
System.out.println("\n Current location: " + head.GetCode());
System.out.println("\n Establish Right Subtree code : 1 Otherwise: 0");
flag = sc.nextInt();
if(flag == 1){
now++;
Tree Rtree = new Tree();
head.SetRtree(Rtree);
Rtree.SetFronttree(head);// Set Parent Node
Link_Build( head.GetRtree() );
}
if( now > save ){
save = now;
}
now--;
}
return head;
}
/*
* Output tree
*/
public Tree output(Tree head){
int flag;
if(head.GetCode() == -1){
return head;
}else{
System.out.println("\n Current location: " + head.GetCode());
System.out.println(head.GetLtree() != null);
if(head.GetLtree() != null){
System.out.println("\n Visit Left subtree :");
output( head.GetLtree() );
}
if(head.GetRtree() != null){
System.out.println("\n Visit Right subtree :");
output( head.GetRtree() );
}
}
return head;
}
/*
* Obtain height
*/
public int GetSave(){
return this.save;
}
/*
* Non-recursive Preorder traversal
*/
public void Front_Traverse(Tree head){
Tree star = head;// Exit mark
int choose = 1; // Left
int flag = 1; // Right
System.out.println( "<--- Preorder traversal --->" + head.GetCode() );// Access the root first
while(true){
if( head.GetLtree() != null && choose != 0 ){
head = head.GetLtree();
System.out.println( "<--- Preorder traversal --->" + head.GetCode() );// Access to information
flag = 1;
}else if( head.GetRtree() != null && flag != 0 ){
head = head.GetRtree();
System.out.println( "<--- Preorder traversal --->" + head.GetCode() );
choose = 1;
}else if( flag == 0 && choose == 0 && head == star){
break;
}else{
if(head == head.GetFronttree().GetRtree()){
flag = 0;
choose = 0;
}
if(head == head.GetFronttree().GetLtree()){
choose = 0;
flag = 1;
}
head = head.GetFronttree();
System.out.println(" Obtain Parents " + head.GetCode());
System.out.println( "\n\n\n" );
}
}
}
/*
* Non-recursive Middle order traversal
*/
public void Center_Traverse(Tree head){
Tree star = head;// Exit mark
int choose = 1; // Left
int flag = 1; // Right
while(true){
if( head.GetLtree() != null && choose != 0 ){
head = head.GetLtree();
flag = 1;
}else if( head.GetRtree() != null && flag != 0 ){
if(head.GetLtree() == null){// Return because the left side is empty
System.out.println( "<-1-- Middle order traversal --->" + head.GetCode());
}
head = head.GetRtree();
choose = 1;
}else if( flag == 0 && choose == 0 && head == star){
break;
}else{
int area = 0;// Judge which side will come back
flag = 1;
choose = 1;
if(head == head.GetFronttree().GetRtree()){
area = 1;// Come back on the right
flag = 0;
choose = 0;
}
if(head == head.GetFronttree().GetLtree()){
area = 2;// Come back on the left
choose = 0;
flag = 1;
}
if( head.GetLtree() == null && head.GetRtree() == null ){// Return because the left side is empty
System.out.println( "<-2-- Middle order traversal --->" + head.GetCode());
}
head = head.GetFronttree();
if( area == 2){// Because the left side returns after accessing
System.out.println( "<-3-- Middle order traversal --->" + head.GetCode());
}
System.out.println(" Obtain Parents " + head.GetCode());
System.out.println( "\n\n\n" );
}
}
}
/*
* Non-recursive Subsequent traversal
*/
public void Bottom_Traverse(Tree head){
Tree star = head;// Exit mark
int choose = 1; // Left
int flag = 1; // Right
while(true){
if( head.GetLtree() != null && choose != 0 ){
head = head.GetLtree();
flag = 1;
}else if( head.GetRtree() != null && flag != 0 ){
head = head.GetRtree();
choose = 1;
}else if( flag == 0 && choose == 0 && head == star){
break;
}else{
int area = 0;// Judge which side will come back
flag = 1;
choose = 1;
if(head == head.GetFronttree().GetRtree()){
area = 1;// Come back on the right
flag = 0;
choose = 0;
}
if(head == head.GetFronttree().GetLtree()){
choose = 0;
flag = 1;
}
if(head.GetRtree() == null){// Returns because the right side is empty
System.out.println( "<-1-- Post-order traversal --->" + head.GetCode());
}
head = head.GetFronttree();
if( area == 1){
System.out.println( "<-2-- Post-order traversal --->" + head.GetCode());
}
System.out.println(" Obtain Parents " + head.GetCode());
System.out.println( "\n\n\n" );
}
}
}
}
2. Tree class implementation:
public class Tree {
private int code = -1;
private Tree Fonttree;
private Tree Ltree;
private Tree Rtree;
Tree(){
this.code = -1;
this.Ltree = null;
this.Rtree = null;
}
/*
* Tree content viewing method:
*/
public void SetCode(int code){// Set number
this.code = code;
}
public int GetCode(){ // Acquisition number
return this.code;
}
/*
* Set the parent pointer:
*/
public void SetFronttree(Tree Front){
this.Fonttree = Front;
}
public Tree GetFronttree(){
System.out.println(" Obtain Parents ");
return this.Fonttree;
}
/*
* Set the left child:
*/
public void SetLtree(Tree Ltree){
this.Ltree = Ltree;
}
public Tree GetLtree(){
System.out.println(" Get the left subtree ");
return this.Ltree;
}
/*
* Set the right child:
*/
public void SetRtree(Tree Rtree){
this.Rtree = Rtree;
}
public Tree GetRtree(){
System.out.println(" Get the right subtree ");
return this.Rtree;
}
}
3. Main function testing:
public class MainActivity {
Scanner sc = new Scanner(System.in);
public static void main(String[] args) {
Tree head = new Tree();
Tree_Link link_1st = new Tree_Link();
head = link_1st.Link_Build(head);
System.out.println("Build succeed !");
System.out.println("\n2 Tree height -->" + link_1st.GetSave());
link_1st.output(head);
System.out.println("Output Over !");
System.out.println("\n\n<---------------- Front ------------------>\n Preamble access root: ");
link_1st.Front_Traverse(head);
System.out.println("\n\n<---------------- Medium ------------------>\n Middle order access root: ");
link_1st.Center_Traverse(head);
System.out.println("\n\n<---------------- Posterior ------------------>\n Post-order access root: ");
link_1st.Bottom_Traverse(head);
System.out.println("\n\n\n\nText over !\n\n\n");
}
}
More readers interested in java algorithm can check the topics of this site: "Java Data Structure and Algorithm Tutorial", "Java Operation DOM Node Skills Summary", "Java File and Directory Operation Skills Summary" and "Java Cache Operation Skills Summary"
I hope this article is helpful to everyone's java programming.