¿Cómo escribir código para una estructura de almacenamiento secuencial de un árbol binario en una estructura de datos?

int Assign(SqBiTree T, posición e, valor TElemType)

{

// Convierte la capa y el número de secuencia de la capa en una matriz Número de serie

int i = (int)pow(2, e.level-1) e.order - 2;

if(value != Nil amp; amp; T[ (i 1)/2-1] == Nil) // hoja con valor no nulo pero dos padres son nulos

devolver 0;

else if(valor == Nil amp ;amp; (T[i*2 1] ! = Nil || T[i*2 2] ! = Nil))

// El nodo padre está vacío, pero tiene hojas (no vacías)

Devuelve 0;

T[i]=valor;

Devuelve 1;

}

/// Si e es un nodo no raíz de T, devuelve su nodo padre; de ​​lo contrario, devuelve "nulo".

"

TElemType Padre(SqBiTree T, TElemType e)

{

int i;

if(T[0]== Nil) // Árbol vacío

return Nil;

for(i =1; ilt; =MAX_TREE_SIZE-1; i )

if(T[i ]==e) // encontrado e

return T[(i 1)/2-1]

return Nil // encontrado e no

}

// Devuelve el nodo secundario izquierdo de e. Si e no tiene un nodo secundario izquierdo, devuelve "null"

TElemType LeftChild(SqBiTree T, TElemType e)

{

int i;

if(T[0]==Nil) // Árbol vacío

return Nil // Aún no; Encontrado p>

return Nil;

for(i=0;ilt;=MAX_TREE_SIZE-1;i)

if(T[i]= =e) // encontré e

return T[i*2 1];

return Nil // encontré e no

}

// Devuelve el nodo hijo derecho de e. Si e no tiene un nodo hijo derecho, devuelve Null

TElemType RightChild(SqBiTree T, TElemType e)

{

int i;

if(T[0]==Nil) // Árbol vacío<

Devuelve Nil; 0 ;ilt;=MAX_TREE_SIZE-1;i )

if(T[i]==e) // encontrar e

devolver T[i*2 2];

return Nil; // no se encontró e

}

// Devuelve el nodo secundario izquierdo de e.

Devuelve "nulo" si e es el subárbol izquierdo de T o no tiene un hermano izquierdo

TElemType LeftSibling(SqBiTree T, TElemType e)

{

int i ;

if(T[0]== Nil) // árbol vacío

return Nil

for(i=1; ilt;=MAX_TREE_SIZE - 1; i )

if(T[i] == e amp; amp; i2 == 0) // se encuentra e y su número de secuencia es par (es un hijo derecho)

Si e es hijo derecho de T o no tiene hermano derecho, devuelve Nil

TElemType RightSibling(SqBiTree T, TElemType e)

{

int i;

if(T[0]== Nil) // Árbol vacío

Devuelve Nil; =MAX_TREE_SIZE-1; i )

if(T[i]==eamp; amp; i2) // Encuentra e, y su número de secuencia es impar (es el hijo izquierdo)

Return T[ i 1];

Return Nil; // e no fue encontrado

}

// El niño a partir del nodo j de q Mueve el árbol al subárbol comenzando desde el nodo i de T

//// Se usa InsertChild()

void Move(SqBiTree q, int j, SqBiTree T, int i)

{

if(q[2*j 1] != Nil) // El subárbol izquierdo de q no está vacío

Move( q, (2*j 1), T, (2*i 1)); // Mueve el subárbol izquierdo del nodo j de q al subárbol izquierdo del nodo i de T

if(q[ 2*j 2] ! = Nil) // El subárbol derecho de q no está vacío

Move(q, (2*j 2), T, (2*i 2)); el subárbol derecho del nodo j de q al subárbol derecho del nodo i de T

T[i]=q[j] // Mueve el nodo j de q al nodo i de T

q[j]=Nil; // Deja que el nodo j de q esté vacío

}

If (q[2*j 2]! p>

}

// Inserte c como el subárbol izquierdo o derecho del nodo p en T, dependiendo de si LR es 0 o 1.

El subárbol izquierdo o derecho original de p

//El subárbol derecho se convierte en el subárbol derecho de c

int InsertChild(SqBiTree T, TElemType p, int LR, SqBiTree c)

{

int j, k, i=0;

for(j=0; jlt; (int)pow(2,BiTreeDepth(T))- 1; j ) // Encuentra el número de serie de p

if(T[j]==p) // j es el número de serie de p

break;

k= 2*j 1 LR; // k es el número de secuencia del subárbol izquierdo o derecho de p

if(T[k] != Nil) // El subárbol izquierdo original o el subárbol derecho de p no está vacío

Move(T, k, T, 2*k 2 // Mueve el subárbol comenzando desde el nodo k de T al subárbol comenzando desde el subárbol derecho de); el nodo k

Move(c, i, T, k); // Mueve el subárbol comenzando desde el nodo i de c al subárbol comenzando desde el nodo k de T

Retornar 1 ;

}

//Construir una cola vacía Q

int InitQueue(SqQueue *Q)

{

(*Q).base=(QElemType *)malloc(MAXQSIZE*sizeof( QElemType)); // Asigna espacio de longitud fija, equivalente a una matriz

if(! (*Q). base) // Error en la asignación de espacio de almacenamiento

exit(0);

(*Q).front=(*Q).rear=0 // Subíndice de inicialización

return 1;

}

//Insertar elemento e como nuevo elemento final de cola de Q

int EnQueue(SqQueue *Q, QElemType e)

{

if((*Q).reargt;=MAXQSIZE)

{ // La cola está llena, la unidad de almacenamiento se incrementa en 1

(*Q).base=(QElemType *)realloc(((*Q).*Q).base, ((*Q).rear 1)*sizeof(QElemType));

if(! (*Q).base) // No se pudo agregar la unidad

Devuelve 0;

}

*(( *Q).base (* Q).rear)=e;

(*Q).rear;

Devuelve 1;

}

// if La cola no está vacía.

Luego elimine el elemento principal de Q, devuelva su valor con e y devuelva 1; de lo contrario, devuelva 0

int DeQueue(SqQueue *Q, QElemType *e)

{

if((*Q).front==(*Q).rear) // La cola está vacía

Devuelve 0;

*e=(*Q ) .base[(*Q).front];

(*Q).front=(*Q).front 1;

Devuelve 1;

}

int DeleteChild(SqBiTree T, posición p, int LR)

{

int

int k=1; ; // La cola de banderas no está vacía

SqQueue q;

InitQueue(amp; q); Se utiliza para guardar el nodo que se va a eliminar

i=(int)pow(2, p.level-1) p.order-2 //Convierte el nivel y el número de serie del nivel en el número de serie de la matriz

if(T[i]==Nil) // El nodo está vacío

return

i=i*2; 1 LR; // Esperar El nodo raíz eliminado es el número de secuencia del nodo raíz del subárbol eliminado en la matriz

while(k)

{

if(T[2*i 1] ! =Nil) // El nodo izquierdo no está vacío

EnQueue(amp; q, 2*i 1); nodo

if(T [2*i 2]! =Nil) // El nodo derecho no está vacío

EnQueue(amp; q, 2*i 2); El número de secuencia del nodo derecho entrante

T[i]=Nil; // Eliminar este nodo

k=DeQueue(amp; q, amp; i); la cola no está vacía

}

Devuelve 1;

}

int(*VisitFunc)(TElemType);

void PreTraverse(SqBiTree T, int e)

{

// llamadas a PreOrderTraverse()

VisitFunc(T[e] ); // Primero llama a la función VisitFunc para procesar la raíz

if(T[2*e 1]!=Nil) // El subárbol izquierdo no está vacío

PreTraverse( T, 2*e 1); // Luego procesa el subárbol del lado izquierdo

if(T[2*e 2]! =Nil) // El subárbol derecho no está vacío

PreTraverse(T, 2*e 2);

}

// Recorre T en el primer orden, llamando a la función Visit solo una vez para cada nodo.

int PreOrderTraverse(SqBiTree T, int(*Visit)(TElemType))

{

VisitFunc=Visita;

if( !BiTreeEmpty(T))

PreTraverse(T, 0

printf("\n");

devuelve 1; p>}

// llamada InOrderTraverse()

void InTraverse(SqBiTree T, int e)

{

if(T[2*e 1]! =Nil) // El subárbol izquierdo no está vacío

InTraverse(T, 2*e 1);

VisitFunc(T[e]);

if(T[2*e 2]! =Nil) // El subárbol derecho no está vacío

InTraverse(T, 2*e 2);

}

// Atraviesa T en orden intermedio, llamando a la función Visita solo una vez para cada nodo.

int InOrderTraverse(SqBiTree T, int(*Visit)(TElemType))

{

VisitFunc=Visita

if( !BiTreeEmpty(T))

InTraverse(T, 0

printf("\n");

devuelve 1; p>}

// Llamada a PostOrderTraverse()

void PostTraverse(SqBiTree T, int e)

{

if(T [2*e 1]! =Nil) // El subárbol izquierdo no está vacío

PostTraverse(T, 2*e 1);

if(T[2*e 2] ]! =Nil) // El subárbol derecho no está vacío

PostTraverse(T, 2*e 2);

VisitFunc(T[e]);

}

// Realiza un recorrido posterior en T y llama a la función Visita solo una vez para cada nodo.

int PostOrderTraverse(SqBiTree T, int(*Visit)(TElemType))

{

VisitFunc = Visita

if( !BiTreeEmpty(T))

PostTraverse(T, 0

printf("\n");

Devuelve 1; p>}

// Recorrido de orden de nivel del árbol binario

void LevelOrderTraverse(SqBiTree T, int(*Visit)(TElemType))

{< / p>

int i=MAX_TREE_SIZE-1, j;

while(T[i] == Nil)

i-- // Encuentra el último no nulo Número de serie del nodo

for(j=0;jlt;=i;j) //Comience desde el nodo raíz y recorra nivel por nivel.

Nodos, recorre el árbol binario en orden jerárquico

if(T[j] != Nil)

Visit(T[j]); // Solo recorre nodos no vacíos

printf("\n");

}

/// Genera el árbol binario capa por capa según el número de capas

void Print(SqBiTree T)

{

int j, k

posición p

TElemType e

for(j= 1;jlt;=BiTreeDepth(T);j )

{

printf("Nivel d:",j);

for(k=1 ; k lt ;= pow(2,j-1);k )

{

p.level=j;

p.order=k;

e=Valor(T, p);

if (e!=Nil)

printf("d :c ",k,e);

}

printf("\n");

}

}

int visita(TElemType e)

{

printf("c ",e);

return 0;

}

int main()

{

int i, j

posición p; > TElemType e;

SqBiTree T, s;

InitBiTree(T);

CreateBiTree(T); Después de crear el árbol binario, ¿está vacío? d(1: sí 0: no) profundidad del árbol=d\n",

BiTreeEmpty(T), BiTreeDepth(T)); >

i=Root(T, amp; e);

if(i)

printf("La raíz del árbol binario es: c\n", e

else

printf("Árbol vacío, sin raíz \n");

printf("Atravesando el árbol binario en orden de niveles:\n"

LevelOrderTraverse (T, visita);

printf("Atravesando el árbol binario en orden medio:\n"); );

printf ("Atravesando el árbol binario en orden de publicación:\n");

PostOrderTraverse(T, visita);

printf("Por favor, ingrese el número de nivel del nodo que se va a modificar El número ordinal de este nivel: ");

scanf("dd*c", amp; p. nivel, amp; p.order.level, amp

; p.order);

e=Value(T, p);

printf("El valor original del nodo a modificar es c Ingrese el nuevo valor:" , e);

scanf("c*c", amp; e);

Assign(T, p, e); > printf("Árbol binario PreOrderTraverse:\n");

PreOrderTraverse(T, visita);

printf("Los dos padres del nodo c son c, y los izquierdo y los hijos derechos son ", e, Parent(T, e));

printf("c, c, los hermanos izquierdo y derecho son ", LeftChild(T, e), RightChild(T, e)) ;

printf("c, c\n", LeftSibling(T, e), RightSibling(T, e));

InitBiTree(s); p> printf("Creando árbol s con subárbol derecho vacío:\n");

CreateBiTree(s);

printf("El árbol s se inserta en el árbol T, ingrese el nodo biparental s del árbol s en el árbol T como un subárbol izquierdo(0) o derecho(1):");

scanf("cd*c",amp;e,amp;j);

InsertChild(T, e, j, s);

Print(T);

printf("Eliminando un subárbol, ingrese el número de nivel de el nodo raíz del subárbol que se va a eliminar Este número de nivel Subárbol izquierdo(0) o derecho(1):");

scanf("ddd*c",amp;p.level,amp;p .orden, & j);

DeleteChild(T, p, j

Imprimir(T);

ClearBiTree(T); >

p>

printf("Después de borrar el árbol binario, ¿está vacío el árbol? d(1: sí 0: no) La profundidad del árbol = d\n",

BiTreeEmpty(T), BiTreeDepth (T));

i=Root(T,amp;e);

if(i)

printf(" La raíz del árbol binario es: c\n", e);

else

printf("Árbol vacío, sin raíz \n");

system("pause");

return 0;

}

/*

Efecto de salida:

Ingrese el valor del nodo (en caracteres) en orden jerárquico. Los espacios representan nodos vacíos. Número de nodos ≤ 100:

Ejemplo: abcefgh

abcdefgh

Después de construir el árbol binario, ¿está vacío el árbol? (1: Sí 0: No) Profundidad del árbol = 4

La raíz del árbol binario es: a

Recorrido jerárquico del árbol binario:

a b c d e f g h

Recorrido de nivel medio de un árbol binario:

h d b e a f c g

Recorrido posterior al orden de un árbol binario:

h d e b f g c a

Ingrese el nodo a modificar. El número de capa es: 3 2

El valor original del nodo a modificar es e. Ingrese el nuevo valor: i

Primero recorra el árbol binario:

a b d h i c f g

El nodo i es el primer nodo que se modifica. p>

El nodo i tiene dos nodos principales b, dos nodos secundarios izquierdo y derecho, y dos nodos hermanos izquierdo y derecho d.

Cree un árbol s con un subárbol derecho vacío:

Ingrese el valor del nodo en orden jerárquico (en caracteres). Un espacio indica un nodo vacío. El número de nodos es ≤100:

Por ejemplo, abcefgh.

jk l

El árbol s se inserta en el árbol T. Ingrese los nodos principales de los árboles en el árbol T. s es el subárbol izquierdo (0) o derecho (1): i 0

Nivel 1: 1: a

Nivel 2: 1: b 2: c

Nivel 3: 1: d 2: i 3: f 4: g

Nivel 4: 1: h 3: j

Nivel 5: 5: k

Nivel 6: 9: l

Para eliminar un subárbol, ingrese el número de nivel del nodo raíz del subárbol que desea eliminar Número de nivel izquierdo (0) o derecho (1) Subárbol: 2 1 0

Nivel 1: 1: a

Nivel 2: 1: b 2: c

Nivel 3: 2: i 3: f 4: g< / p>

Nivel 4: 3: j

Nivel 5: 5: k

Nivel 6: 9: l

Nivel 7: 9: k

Nivel 8: 9:k

Nivel 9: 9:k

Nivel 9: 9:k

Nivel 10 Nivel : 9: k

Nivel 10: 9:k

Nivel 11: 9:l Nivel 6: 9:l

Después de borrar el árbol binario, es ¿El árbol vacío? 1(1: Sí 0: No) Profundidad del árbol = 0

El árbol está vacío y no tiene raíces

Presione cualquier tecla para continuar. .

*/.