设计一个算法，求出指定结点在给定二叉排序树中的层次。(假设二叉排

Question

设计一个算法，求出指定结点在给定二叉排序树中的层次。(假设二叉排序树采用二叉存储结构，要求采用二叉排序树非递归查找算法实现)

大神求解

Answer 1

测试结果:

创建二叉排序树,请输入结点的总数量: 7
请连续输入7个结点的数据: 2 4 1 3 7 9 5
先序遍历序列: 2 1 4 3 7 5 9
中序遍历序列: 1 2 3 4 5 7 9
后序遍历序列: 1 3 5 9 7 4 2
输入要查找的结点的数值(0退出): 9
该结点的层次是 4
输入要查找的结点的数值(0退出): 7
该结点的层次是 3

二叉树示意图:

    2 
   / \
  1   4
     / \
    3   7
       / \
      5   9


#include "stdio.h"
#include "stdlib.h"
struct Tree
{
    int data;
    struct Tree *left;
    struct Tree *right;
};
typedef struct Tree TreeNode;
typedef TreeNode *Bitree;
//插入结点
Bitree insertNode(Bitree root,int data)
{
    Bitree newnode;
    Bitree current;
    Bitree back;
    newnode=(Bitree)malloc(sizeof(TreeNode));
    if(newnode==NULL)
    {
        printf("\n动态分配内存出错.\n");
        exit(1);
    }
    newnode->data=data;
    newnode->left=NULL;
    newnode->right=NULL;
    if(root==NULL)
    {
        return newnode;
    }
    else
    {
        current=root;
        while(current!=NULL)
        {
            back=current;
            if(current->data > data)
            {
                current=current->left;
            }
            else
            {
                current=current->right;
            }
        }
        if(back->data > data)
        {
            back->left=newnode;
        }
        else
        {
            back->right=newnode;
        }
    }
    return root;
}
//创建二叉排序树(非递归)
Bitree createTree()
{
    Bitree root=NULL;
    int len;
    int data;
    int i;
    printf("创建二叉排序树,请输入结点的总数量: ");
    scanf("%d",&len);
    printf("请连续输入%d个结点的数据: ",len);
    for(i=0;i<len;i++)
    {
        scanf("%d",&data);
        root=insertNode(root,data);
    }
    return root;
}
//先序遍历(递归法)
void preOrder(Bitree ptr)
{
    if(ptr!=NULL)
    {
        printf("%d ",ptr->data);
        preOrder(ptr->left);
        preOrder(ptr->right);
    }
}
//中序遍历(递归法)
void inOrder(Bitree ptr)
{
    if(ptr!=NULL)
    {
        inOrder(ptr->left);
        printf("%d ",ptr->data);
        inOrder(ptr->right);
    }
}
//后序遍历(递归法)
void postOrder(Bitree ptr)
{
    if(ptr!=NULL)
    {
        postOrder(ptr->left);
        postOrder(ptr->right);
        printf("%d ",ptr->data);
    }
}
//计算结点的层次(非递归)
int findLevel(Bitree root,int data)
{
    Bitree current;
    int nLevel;
    if(root==NULL)
    {
        return -1;
    }
    else
    {
        current=root;
        nLevel=0;
        while(current!=NULL)
        {
            nLevel++;
            if(current->data > data)
            {
                current=current->left;
            }
            else if(current->data < data)
            {
                current=current->right;
            }
            else
            {
                return nLevel;
            }
        }
    }
    return 0;
}

int main()
{
    Bitree root=NULL;
    int data;
    int nLevel;

    root=createTree(); //创建二叉排序树

    printf("先序遍历序列: ");
    preOrder(root);
    printf("\n");

    printf("中序遍历序列: ");
    inOrder(root);
    printf("\n");

    printf("后序遍历序列: ");
    postOrder(root);
    printf("\n");

    while(1)
    {
        printf("输入要查找的结点的数值(0退出): ");
        scanf("%d",&data);
        if(data==0)
        {
            break;
        }
        //计算结点的层次(非递归)
        nLevel=findLevel(root,data);
        if(nLevel == -1)
        {
            printf("二叉树没有数据.\n");
        }
        else if(nLevel == 0)
        {
            printf("二叉树没有该数据.\n");
        }
        else
        {
            printf("该结点的层次是 %d\n",nLevel);
        }
    }

    printf("\n");
    return 0;
}