博客

描述

已知一棵二叉树用邻接表结构存储，中序查找二叉树中值为x的结点，并指出是第几个结点。例：如图二叉树的数据文件的数据格式如下:

enter image description here


格式

输入格式


第一行n为二叉树的结点个树，n≤100；第二行x表示要查找的结点的值；以下第一列数据是各结点的值，第二列数据是左儿子结点编号，第三列数据是右儿子结点编号。


输出格式


一个数即查找的结点编号。


样例

输入样例

7

15

5 2 3

12 4 5

10 0 0

29 0 0

15 6 7

8 0 0

23 0 0

输出样例

4

限制

时间限制: 1000 ms

内存限制: 65536 KB

#include<bits/stdc++.h>
using namespace std;

struct node{
	int data;
	int lchild;
	int rchild;
	int parent;
}bt[1000];

int n,key,tag,cnt;

void dfs(node index){
	if(index.data==0) return;
	dfs(bt[index.lchild]);
	if(tag==1) return;
	cnt++;
	if(index.data==key){
		tag=1;
		cout<<cnt;
		return;
	}
	dfs(bt[index.rchild]);
	if(tag==1) return;
}

int main(){
	cin>>n>>key;
	for(int i=1;i<=n;i++){
		int data,left,right;
		cin>>data>>left>>right;
		bt[i].data=data;
		bt[i].lchild=left,bt[left].parent=i;
		bt[i].rchild=right,bt[right].parent=i;
	}
	dfs(bt[1]);
	return 0;
}