关于二叉树的一个有关问题

关于二叉树的一个问题
有个实验作业题，本来挺简单的，但是老师说要用二叉树的数据结构，不能用数学方法来做，我就没辙了。
原题如下：
假定存在这样一颗二叉树：每个结点有两个数(a,b)，结点的左儿子为(a+b,b)，右儿子为(a,a+b)，根为（1,1）。现在给出某结点的两个数，问从根到这个结点要几次向左，几次向右（必须使用二叉树的数据结构解决，不能用数学方法）。
解决方案要求：
输入参数：结点中的两个数
输出参数：左右走向次数
参考样例：
Example ：
Input ：42 1
Output ：41 0

Test Data ：
Input ：3 4
17 73
Output ：2 1
4 6

我说下我的看法哦，这个题目的话，我想要找到指定的结点的话，至少要用二叉树的遍历吧。然后加个计数的变量。但是我想归想，写不出来。各位大神帮帮忙，看看吧。最好有代码参考下。谢谢，感激不尽。

数据结构

------解决方案--------------------

引用:

Quote: 引用:

你可以自己在纸上试着建一颗这样的数(根节点为1,1)，
建几层之后你会发现其实是有规律的，并不一定是要遍历按整棵树，
而且比如你输入41,1这数据，整棵树中有好些41,1的节点的
你可以试着写写

其实我想问的是，那个所谓的数学方法到底指的是什么？

应该是类似树的生长公式吧
然后用公式就可以求出输入的节点的位置
------解决方案--------------------
参考一下：

#include <stdio.h>

#include <stdlib.h>

#include <memory.h>

#include <string.h>



typedef struct binary_tree bitree_t;

typedef char btelem_t;

typedef void (*visitor_t)(bitree_t *);


struct binary_tree {

	bitree_t* l;

	bitree_t* r;

	btelem_t  e;

};



#define NIL_ELEM(e) ((e) == ' ')



// create binary with in-order way.

void create_bitree(bitree_t** root, const btelem_t** elems, int* elemnum)

{

	if (*elemnum == 0) return; // no more elements


	if (NIL_ELEM(**elems)) {

		*root = NULL;

		(*elems)++; (*elemnum)--;

	} else {

		// m-node

		*root = (bitree_t*)malloc(sizeof(bitree_t));

		(*root)->e = *(*elems)++; (*elemnum)--;

		// (l, r)-nodes

		create_bitree(&((*root)->l), elems, elemnum); // l-tree

		create_bitree(&((*root)->r), elems, elemnum); // r-tree

	}

}


void preorder(bitree_t* root, visitor_t visitor)

{

	if (root == NULL) {

		//if (visitor) visitor(root);

		return;

	}


	if (visitor) visitor(root);

	preorder(root->l, visitor);

	preorder(root->r, visitor);

}


void inorder(bitree_t* root, visitor_t visitor)

{

	if (root == NULL) return;


	inorder(root->l, visitor);

	if (visitor) visitor(root);

	inorder(root->r, visitor);

}


void postorder(bitree_t* root, visitor_t visitor)

{

	if (root == NULL) return;


	postorder(root->l, visitor);

	postorder(root->r, visitor);

	if (visitor) visitor(root);

}




void print_node(bitree_t *node)

{

	if (node == NULL) return;


	putchar(node->e);


	//putchar(node ? node->e : ' ');

}




int main(void)

{

	bitree_t *root = NULL;

	btelem_t *elems = "ABD   CE  F  ";

	size_t elemnum = strlen(elems);

	visitor_t visitor = print_node;


	create_bitree(&root, &elems, &elemnum);


	printf("pre-order: ");

	preorder(root, visitor);

	putchar('\n');


	printf("in-order: ");

	inorder(root, visitor);

	putchar('\n');


	printf("post-order: ");

	postorder(root, visitor);

	putchar('\n');


	getch();

	return 0;

}

关于二叉树的一个有关问题

相关推荐