UC知道数据结构 计算结点所在层次
来源：百度知道 编辑：UC知道 时间：2024/06/07 11:03:50
已知一棵用二叉链表表示的二叉树，其根指针为root，试编写一个递归算法，以计算二叉树中指定结点*p所在层次。
二叉链表的结点（BinTreeNode）结构定义为：
typedef struct tag_node
{
int data;//数据域
struct tag_node *lchild;//左链指针，指向左子女
struct tag_node *rchild;//右链指针，指向右子女
}BinTreeNode;
外部调用方式：level(root,p);
函数的首部为：int level(BinTreeNode *t,BinTreeNode *p)
二叉链表的结点（BinTreeNode）结构定义为：
typedef struct tag_node
{
int data;//数据域
struct tag_node *lchild;//左链指针，指向左子女
struct tag_node *rchild;//右链指针，指向右子女
}BinTreeNode;
外部调用方式：level(root,p);
函数的首部为：int level(BinTreeNode *t,BinTreeNode *p)
#include <iostream.h>
#include <limits.h>
typedef struct tag_node
{
int data;//数据域
struct tag_node *lchild;//左链指针，指向左子女
struct tag_node *rchild;//右链指针，指向右子女
}BinTreeNode;
int max(int a,int b)
{
return a>b ? a : b;
}
int level(BinTreeNode * t,BinTreeNode * p)
{
if(p==t) //找到
return 0; //假如根结点的层次是0
if(t==NULL) //如果一个分支搜索到空都没有找到
return INT_MIN; //-2147483648 确保找到p的比没有找到p的要大。
return max(level(t->lchild,p),level(t->rchild,p))+1; //层数加1，递归
}
#include "iostream.h"
typedef struct LNode
{
int data;
struct LNode *LChild,*RChild;
}LNode;
void CreateTree(LNode* head) //建立自己设置结点的二叉树
{
head->LChild=NULL,head->RChild=new LNode,head->data=9;
head=head->RChild;
head->data=6,head->LChild=new LNode,head->RChild=new LNode;
head->RChild->LChild=NULL,head->RChild