아르보레 비나리아
struct arvbin {
int info;
struct arvbin *esq, *dir;
};
typedef struct arvbin TAB;
크리안도 데 움 노
TAB *TAB_cria(int info, TAB *esq, TAB *dir) {
TAB *no = (TAB *) malloc(sizeof(TAB));
no->info = info;
no->esq = esq;
no->dir = dir;
return no;
}
Copiando 우마 아르보레
TAB *copia(TAB *a) {
if(!a)
return NULL;
return TAB_cria(a->info, copia(a->esq), copia(a->dir));
}
// identico
TAB *copia(TAB *a) {
if(!a)
return NULL;
// aloca uma nova arvore
TAB *novo = (TAB *) malloc(sizeof(TAB));
// copia a informação
novo->info = a->info;
// copia as subarvores
novo->esq = copia(a->esq);
novo->dir = copia(a->dir);
return novo;
}
에스펠한도 우마 아르보레
TAB *espelho(TAB *a) {
if(!a)
return NULL;
return TAB_cria(a->info, espelho(a->dir), espelho(a->esq));
}
Encontrando menor/maior elemento de uma árvore
TAB *maior(TAB *a) {
if(!a)
return a;
TAB *result = a;
// maior elem da sub-arv da esquerda
TAB *e = maior(a->esq);
// maior elem da sub-arv da direita
TAB *d = maior(a->dir);
// comparar o elemento da raiz com os maiores das sub-arvores
if(e && e->info > result->info)
result = e;
if(d && d->info > result->info)
result = d;
return result;
}
Comparando duas árvores
int igual(TAB *a, TAB *b) {
// duas arvores vazias
if(!a && !b)
return 1;
// uma das arvores vazia, a outra nao
if(!a || !b)
return 0;
// se as raizes forem iguais, as sub arvores tambem preciam ser iguas
if(a->info == b->info)
return igual(a->esq, b->esq) && igual(a->dir, b->dir);
return 0;
}
Retirando os nos pares de uma árvore
TAB *retira_pares(TAB *a){
if(!a)
return NULL;
// retiro os pares das minhas duas sub-arvores
a->esq = retira_pares(a->esq);
a->dir = retira_pares(a->dir);
// se a raiz for par...
if(a->info % 2 == 0) {
// se for uma folha
if(!a->esq && !a->dir) {
free(a);
return NULL;
}
// trocar a raiz com um elem de uma sub-arvore
// como ja foram tirado os pares das sub-arvores, garanto que esse elemento nao vai ser par
TAB *aux = a->esq;
if(!aux)
aux = a->dir;
// trocando
int tmp = aux->info;
aux->info = a->info;
a->info = tmp;
// depois da troca, tentar retirar de novo
a = retira_pares(a);
}
return a;
}
Contando os nos
int nn(TAB *a) {
if(!a)
return 0;
return 1 + nn(a->esq) + nn(a->dir);
}
Contando os nos internos
int ni(TAB *a) {
if(!a)
return 0;
// se o no for folha
if(!a->esq && !a->dir)
return 0;
// a raiz + os nos internos das sub-arvores
return 1 + ni(a->esq) + ni(a->dir);
콘탄도 오스 노스 폴하스
int ni(TAB *a) {
if(!a)
return 0;
// se o no for folha
if(!a->esq && !a->dir)
return 1;
// os nos folhas das sub-arvores
return nf(a->esq) + nf(a->dir);
Transformando em um vetor
int *ab2vet(TAB *a) {
if(!a)
return NULL;
int n = nn(a);
int *v = (int *) malloc(sizoef(int) * n);
tovet(a, v);
return v;
}
void tovet(TAB *a, int *vet) {
if(!a)
return;
int pos = nn(a->esq);
v[pos] = a->info;
tovet(a->esq, v);
tovet(a->dir, v + pos + 1);
}
Transformando em uma Lista Simplismente Encadeada
TLSE *ab2lse(TAB *a) {
if(!a)
return NULL;
return tolse(a, NULL);
}
TLSE *tolse(TAB *a, TLSE *l) {
if(!a)
return l;
l = tolse(a->esq);
l = TLSE_insere(l, a->info);
l = tolse(a->dir);
return l;
}
Transformando em uma Árvore Binária de Busca
TABB *ab2abb(TAB *a) {
if(!a)
return NULL;
int *v = ab2vet(a);
// alguma funcao qualquer para ordenar v
sort(v);
return vet2abb(v, nn(a));
}
TABB *vet2abb(int *v, int n) {
if(n == 0)
return NULL;
return TAB_cria(v[n/2], vet2abb(v, n/2), vet2abb(v + n/2 + 1, n - n/2 - 1));
}
Reference
이 문제에 관하여(아르보레 비나리아), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://dev.to/sulyak/arvore-binaria-1hok텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)