The establishment and traversal of binary tree in data structure experiment

Time Limit: 1000 ms Memory Limit: 65536 KiB

Submit Statistic

Problem Description

It is known that a sequence of characters, such as ABC, De, G, F,, (where comma represents empty node), is input in a sequence of precedence. Please build a binary tree and traverse it in the middle and back order. Finally, find out the number of leaf nodes and the depth of the binary tree.

 

Input

Enter a string less than 50 characters long.

Output

There are four lines of output:
The first line outputs the middle order traversal sequence;
The second line outputs the sequential traversal sequence;
The third line outputs the number of leaf nodes;
The fourth line outputs the depth of the binary tree.

Sample Input

abc,,de,g,,f,,,

Sample Output

cbegdfa
cgefdba
3
5

 

 

The new point of this problem lies in the judgment of depth Baidu)

First, the depth of the left subtree of the binary tree is traversed, and then the depth of the right subtree of the binary tree is traversed. Finally, judge the depth of the left and right subtrees. If the left subtree is deeper than the right subtree, return the left subtree depth + 1, otherwise return the right subtree depth + 1.

/* Initial condition: the existence of binary tree t. Operation result: returns the depth of T */
int BiTreeDepth(BiTree T)
{
 int i,j;
    if(!T)
  return 0;
 if(T->lchild)
  i=BiTreeDepth(T->lchild); // Left subtree depth
 else
  i=0;
 if(T->rchild)
  j=BiTreeDepth(T->rchild);  // Right subtree depth
 else
  j=0;
 return i>j?i+1:j+1;
}

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct TreeNode *BinTree;
typedef  char ElementType;
typedef BinTree Position;
struct TreeNode
{
    ElementType Data;
    BinTree Left;
    BinTree Right;
} ;
char st[55];
int cnt;
struct TreeNode *creat()
{
    struct TreeNode *root;
    if(st[++cnt] == ',')
    {
        root = NULL;
    }
    else
    {
        root = (struct TreeNode *)malloc(sizeof(struct TreeNode));
        root->Data = st[cnt];
        root->Left = creat();
        root->Right = creat();
    }
    return root;
};
void zhongxu(struct TreeNode *root)
{
    if(root)
    {
        zhongxu(root->Left);
        printf("%c",root->Data);
        zhongxu(root->Right);
    }
}
void houxu(struct TreeNode *root)
{
    if(root)
    {
        houxu(root->Left);
       houxu(root->Right);
        printf("%c",root->Data);
    }
}
int leave(struct TreeNode *root)
{
    if(root == NULL)
        return 0;
    if(root->Left == NULL&& root->Right == NULL)
        return 1;
    else return leave(root->Left) + leave(root -> Right);
}
int depth(struct TreeNode *root) //Judgment of depth
{
    int i,j;
    if(!root)return 0;
    if(root->Left) i= depth(root->Left);
    else i = 0;
    if(root->Right)j = depth(root->Right);
    else j = 0;
    return i>j?i + 1:j+1;
}
int main()
{
    while(~scanf("%s",st))
    {
        cnt = -1;
        struct TreeNode *root;
        root = creat();
        zhongxu(root);
        printf("\n");
        houxu(root);
        printf("\n");
        printf("%d\n",leave(root));
        printf("%d\n",depth(root));
    }
   return 0;
}