以二叉链表为存储结构。分别写出在二叉树中查找值为X的结点及求X所在的结点在树中层数的算法

Question

如题所述

Answer 1

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#define NUM_NODE 12

typedef struct BiTree{
int data;
BiTree *lchild;
BiTree *rchild;
}BiTree;

BiTree* CreateTree(int n)
{
BiTree *t;
if (n <= 0 || n> NUM_NODE) return NULL;
if (!(t = (BiTree*)malloc(sizeof(BiTree))))
return NULL;
t->data = n;
printf("%d ", t->data);
t->lchild = CreateTree(2*n);
t->rchild = CreateTree(2*n+1);
return t;
}

void FreeTree(BiTree *t)
{
if (t)
{
if (t->lchild)
FreeTree(t->lchild);
if (t->rchild)
FreeTree(t->rchild);
printf("%d ", t->data);
free(t);
}
}

typedef struct NodePos{
BiTree *pos;
int Depth;
} NodePos;

//前序查找,如果返回0，说明树中没有这个数 depth参数为 根结点的层数，由用户定
int PreSeek(BiTree *T, int data, int depth, NodePos *p)
{
int ret=0;

if (T->data == data)
{
p->Depth = depth;
p->pos = T;
ret = 1;
}
else
{
if (T->lchild)
ret += PreSeek(T->lchild, data,depth+1, p);
if (T->rchild)
ret += PreSeek(T->rchild, data,depth+1, p);
}
return ret;
}

int main()
{
BiTree *root;

printf("Create Tree\n");
root = CreateTree(1);
printf("Input what you looking for: ");
int a;
NodePos pos;
scanf("%d", &a);
if (PreSeek(root, a, 1, &pos))
printf("结点地址为：%8X, 深度： %d\n", pos.pos, pos.Depth);
else
printf("Node not found\n");

printf("\nFree Tree\n");
FreeTree(root);
return 0;
}本回答被提问者采纳