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

2013-11-14

关于二叉树的一个问题有个实验作业题，本来挺简单的，但是老师说要用二叉树的数据结构，不能用数学方法来做，

关于二叉树的一个问题
有个实验作业题，本来挺简单的，但是老师说要用二叉树的数据结构，不能用数学方法来做，我就没辙了。
原题如下：
假定存在这样一颗二叉树：每个结点有两个数(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;
}

热点排行

C语言

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