Operaciones básicas de árboles binarios de estructura de datos~~~~
Utilice el método recursivo para implementar el siguiente algoritmo:
1. Utilice una lista binaria vinculada para representar un árbol binario y construir un árbol binario;
2. Genera el resultado del recorrido del pedido previo del árbol binario;
3. Genera el resultado transversal en orden del árbol binario;
4. Genere los resultados del recorrido posterior al pedido del árbol binario;
5. Cuente el número de nodos hoja del árbol binario;
6. Cuente el número de nodos en un árbol binario;
7. Calcula la profundidad de un árbol binario.
8. Intercambie el hijo izquierdo y el hijo derecho de cada nodo en el árbol binario
#include lt; malloc.hgt
#include lt; p> #include lt;conio.hgt;
#include lt;string.hgt;
#include lt;stdlib.hgt
#define OK; 1
#define NULL 0
#define FALSE 0
typedef struct BiTNode{ //Definir estructura de árbol binario encadenado
datos de caracteres ;
estructura BiTNode *lchild, *rchild;
}BiTNode, *BiTree
BiTree T; /p>
p>
int flag=0;
int createBiTree(BiTree amp; T){
//Ingrese el valor del nodo en el binario árbol en orden (un carácter), el espacio representa un árbol vacío
ch=getchar();
if(ch==' ')T=NULL // Indica un vacío; árbol
else if (ch==10)flag=1; //Si la información del nodo se ingresa incorrectamente, se devolverá 0
else {
T=(BiTNode*)malloc(sizeof(BiTree));
if(!T)exit(1); //Salir si la asignación de espacio no es exitosa
T-gt; data=ch; //Generar nodo raíz
createBiTree(T-gt; lchild); //Generar subárbol izquierdo
createBiTree(T-gt;rchild); subárbol
}// else
return OK
}//createBiTree
int PreOrderTraverse(BiTree T){ //Recursivo algoritmo para el recorrido de pedido previo de un árbol binario
if(T){
printf("c", T-gt; data //Accede al nodo raíz
PreOrderTraverse(T-gt; lchild);
PreOrderTraverse(T-gt;rchild);
}//si
return OK
}
int InOrderTraverse(BiTree T){ //Inorder
if(T){
InOrderTraverse(T-gt) ;lc
hild);
printf("c", T-gt; data); //Accede al nodo raíz
InOrderTraverse(T-gt; rchild); p> }//si
return OK
}
int PostOrderTraverse(BiTree T){ // Postorder
if ( T){
PostOrderTraverse(T-gt;lchild);
PostOrderTraverse(T-gt;rchild);
printf("c",T - gt;data); //Accede al nodo raíz
}
return OK
}
int NodeCount(BiTree T ) { //
if(T==NULL) return 0; // Si es un árbol vacío, el número de nodos es 0
else return 1 NodeCount(T-gt ;lchild) NodeCount(T-gt;rchild);
//De lo contrario, el número de nodos es 1, el número de nodos en el subárbol izquierdo y el número de nodos en el subárbol derecho
}
int LeafNodeCount(BiTree T ){
if(!T)return 0; // Si es un árbol vacío, el número de hojas es 0; /p>
else if(LeafNodeCount(T-gt;lchild) LeafNodeCount(T-gt;rchild)==0)return 1; // Si es un nodo hoja, el número de nodos hoja es 1
else return LeafNodeCount(T-gt; lchild) LeafNodeCount(T-gt; rchild) // De lo contrario, el número de nodos hoja es el número de nodos hoja del subárbol izquierdo; y el número de hojas del subárbol derecho Número de nodos
}
int Depth(BiTree T){//Calcular la profundidad del árbol binario
int m, n;
if(T==NULL)return 0; // Si es un árbol vacío, la profundidad es 0
else {
m=Depth(T-gt;lchild);/ /Calcular la profundidad del subárbol izquierdo como m
n=Depth(T-gt; rchild); //Calcular la profundidad del derecho y el subárbol izquierdo como n
if(mgt; n) return(m 1); //La profundidad del árbol binario es el mayor entre myn más 1
else return (n 1);
}
}
intercambio vacío1(BiTree T)
{
BiTree temperatura;
if(T)
{
Intercambio1(T-gt;lchild);
Intercambio1(T-gt;rchild);
temp=T-gt;lchild;
T-gt;lchild=T-gt;rchild;
T-gt;rchild=temp;
}
}
void main(){
int no, out=1
char elegir
p>
//*********************************Interfaz principal***** ******* **********************
mientras(fuera){
sistema( "cls");
p>
printf("\nEste es el programa para el Experimento 2, siga las instrucciones:\n"); Utilice una lista binaria vinculada para representar un árbol binario y construir un árbol binario, ingrese 1");
printf("\n2. Genere el resultado transversal del pedido anticipado del árbol binario, ingrese. 2");
printf("\n3. Genera el resultado del árbol binario. Para el resultado transversal en orden, ingresa 3");
printf("\n4 Para generar el resultado del recorrido posterior al pedido del árbol binario, ingrese 4");
printf("\n5. Para contar el número de nodos en un árbol binario, ingrese 5");
printf("\n6. Para contar el número de nodos de hoja en un árbol binario, ingrese 6");
printf ("\n7. Para calcular la profundidad de un árbol binario, ingrese 7");
printf("\n8. Para intercambiar los hijos izquierdo y derecho de un árbol binario, ingrese 8");
printf( " \n9. Salir, ingrese algo más\n");
//*********************Procesar opciones de entrada*** * ********************************
elegir=getch()
switch(choose){
case '1':
system("cls");
printf("\nPor favor ingrese binario Cree un binario árbol basado en la información del nodo de la lista vinculada Un árbol vacío está representado por un espacio: \n");
if(createBiTree(T)==0||flag==1){ /. /¡Entrada de nodo incorrecta!
printf("Error de entrada, vuelva a ingresar la información del nodo!\n");
getch(); break;}
else
printf("¡Entrada completada!"); //Creado exitosamente
Lista enlazada bifurcada
getch(); break
case '2':
printf("\nEl resultado del recorrido del pedido anticipado es: ") ;
PreOrderTraverse(T);
getch();
caso '3':
printf("\nmid; -order El resultado del recorrido es: ");
InOrderTraverse(T);
getch(); break;
case '4':
printf("\nEl resultado del recorrido posterior al pedido es: ");
PostOrderTraverse(T
getch();
case '5':
no=NodeCount(T);
printf("\nEl número de puntos de resumen es: d\n", no
getch(); break;
case '6':
printf("\nEl número de nodos hoja es: d\n", LeafNodeCount(T) );
getch(); break;
case '7':
printf("\nLa profundidad del árbol binario es: d\n" , Profundidad(T) );
getch(); break;
case '8':
printf("\nEl resultado después del intercambio es: " );
p>Exchange1(T);
PostOrderTraverse(T);
getch();
printf("\nLo que ingresaste es: otro\n");
getch()
out=0; > } //finalizar cambio
}//fin de while
system("cls");
printf("\n\n\t\ ¡Bienvenido, adiós! ");
}
¡Bloqueo!