¡Urgente! ~Escribir un programa en lenguaje C++ para implementar operaciones en árboles binarios
Los árboles binarios utilizan listas binarias enlazadas como estructuras de almacenamiento. La programación implementa las siguientes operaciones básicas de los árboles binarios:
1. Construir un árbol binario T representado por una lista binaria enlazada. secuencia de preorden;
p>
2. Recorra este árbol binario: secuencias de preorden, en orden, post-orden y transversales jerárquicas, y genere las secuencias transversales de nodos respectivamente; /p>
3. Encuentre la profundidad/nudo del árbol binario Número de puntos/número de nodos de hoja;
4. Intercambie los subárboles izquierdo y derecho de cada nodo en el árbol binario.
Descripción de datos
//- - - - - - Representación de almacenamiento de lista enlazada binaria del árbol binario - - - - - - -
typedef struct BiTNode{
datos TElemType;
Struct BiTNode * lchild, * rchild; //Punteros secundarios izquierdo y derecho
}BiTNode, * BiTree;
Descripción del algoritmo
1. Crear un árbol binario
Estado CreateBiTree(BiTree &T)
//Ingrese el valor del nodo en el árbol binario en orden de pedido anticipado (un carácter), el carácter # representa un árbol vacío,
//Construya un árbol binario T representado por una lista binaria vinculada.
scanf(&ch);
if (ch=='#') T=NULL;
else {
if ( !(T=(BiTNode *) malloc(sizeof(BiTNode)))) exit (OVERFLOW);
T->data = ch; //Generar nodo raíz
CreateBiTree ( T->lchild); //Generar subárbol izquierdo
CreateBiTree(T->rchild); //Generar subárbol derecho
}
return OK;
}//CreateBiTree
2. Algoritmo recursivo de árbol binario transversal de pedido previo
Status PreOrderTraverse(BiTree T,Status(* Visit)(TElemType e) ){
//Utilizando una estructura de almacenamiento de lista enlazada binaria, Visit es una función de aplicación que opera en elementos de datos.
//Recorre el árbol binario T en orden y llama a la función para cada nodo. Visita una vez y sólo una vez.
//Una vez que visit() falla, la operación falla.
if (T){
if (Visita(T->datos))
if (PreOrderTraverse(T->rchild, Visita)) return OK ;
return ERROR;
}else return OK;
}// PreOrderTraverse
3. Algoritmo recursivo para recorrido en orden.
Estado InOrderTraverse(BiTree T,Status(* Visita)(TElemType e)){
if (T){
if (Visita(T->) data ))
si (InOrderTraverse(T->rchild, Visit)) devuelve OK;
devuelve ERROR;
}de lo contrario, devuelve OK;
}// InOrderTraverse
4. Algoritmo recursivo transversal posterior al pedido
Status PostOrderTraverse(BiTree T,Status(* Visit)(TElemType e)){
if (T){
if (Visita(T->datos))
if (PreOrderTraverse(T->rchild, Visita)) devuelve OK;
return ERROR;
}else return OK;
}// PreOrderTraverse
Uno de los algoritmos no recursivos para in- recorrido de orden
Estado InOrderTraverse(BiTree T, Estado (* Visita)(TElemType e)) {
InitStack(S);
Push(S,T ); //Puntero raíz Empujar en la pila
While (!StackEmpty(S)) {
While (GetTop(S,p) && p) Push(S,p- >lchild); //A la izquierda Ir al final
Pop(S,p); //El puntero nulo sale de la pila
If (!StackEmpty(S)) { //Accede al nodo, da un paso a la derecha
p>
Pop(S,p);
If (!Visit(p->data)) devolver ERROR;
Push(S,p->rchild
}//si
}//mientras
regresar; OK;
}//InOrderTraverse
6. Algoritmo no recursivo de recorrido en orden 2
Estado InOrderTraverse(BiTree T, Estado (* Visita)( TElemType e)) {
// Utilizando una estructura de almacenamiento de lista vinculada binaria, Visit es una función de aplicación que opera en elementos de datos.
//Algoritmo no recursivo para recorrer en orden el árbol binario T, llamando a la función Visit para cada elemento de datos.
InitStack(S);
p=T;
Mientras (p‖!StackEmpty(S)) {
if ( p) {Push(S,p); p=p->lchild;} //Empuja el puntero raíz en la pila y atraviesa el subárbol izquierdo
else { //Empuja el puntero raíz fuera de la pila y acceda al nodo raíz. Atraviese el subárbol derecho
Pop(S,p>if (!Visit(p->data)) return ERROR;
p=p- >rchild);
}//else
}//mientras
regresa OK;
} //InOrderTraverse
7． Algoritmo no recursivo para recorrer el nivel de un árbol binario
Status LevelOrder(BiTree T){
//Atravesar el árbol binario T jerárquicamente, Q es la cola
InitQueue(Q) ;
If (T!=NULL){//Si el árbol no está vacío
EnQueue(Q,T);//El nodo raíz es poner en la cola
While (!QueueEmpty(Q)){
DeQueue(Q,b); //El elemento principal de la cola se retira de la cola
If (b->lchild!=NULL) EnQueue(Q,b->lchild);//El subárbol izquierdo no está vacío, luego ingrese a la cola
If (b-> rchold!=Null) EnQueue(Q,b->rchild);// Si el subárbol derecho no está vacío, ingrese a la cola
}//mientras
}//si
}Orden de nivel
8． Encuentra la profundidad del árbol binario
int Depth(BiTree T){
//Si T es un árbol vacío, la profundidad es 0, de lo contrario su profundidad es igual a la izquierda o subárbol derecho Incrementar la profundidad máxima en 1
si (T==NULL) devuelve 0;
else {dep1=profundidad(T->lchild);
dep2=profundidad (T->rchild);
return dep1>dep2?dep1+1:dep2+1;
}
}
Programa fuente C
#include
#include
#define MAX 20
# define NULL 0
typedef char TElemType;
typedef int Estado;
typedef struct BiTNode{
datos TElemType ;
estructura BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
Estado CreateBiTree(BiTree *T){
char ch;
ch=getchar();
if (ch=='#') (*T)
=NULL; /* #representa un puntero nulo*/
else {
(*T)=(BiTree) malloc(sizeof(BiTNode));/*Aplicar para un nodo */
(*T)->data=ch; /*Generar nodo raíz*/
CreateBiTree(&(*T)->lchild); */
CreateBiTree(&(*T)->rchild) /*Construye el subárbol derecho*/
}
return 1;
}
anular pedido anticipado(BiTree T){
if (T) {
printf("%2c",T->data) /*Accede al nodo raíz, que se simplifica para generar el valor de datos del nodo raíz*/
PreOrder(T->lchild); /*El pedido anticipado atraviesa el subárbol izquierdo*/
PreOrder(T->rchild); /*Preorder atraviesa el subárbol derecho*/
}
}
void LevleOrder(BiTree T) {
/*Recorre el árbol binario T jerárquicamente, comenzando desde el primer nivel, cada nivel de izquierda a derecha*/
BiTree Queue[MAX],b /*Usa uno; -matriz dimensional Representa la cola, front y rear representan los punteros principal y posterior de la cola respectivamente*/
int front,rear;
front=rear=0;
if ( T) /*Si el árbol no está vacío*/
{Queue[rear++]=T /*El nodo raíz se coloca en la cola*/
while (front!=rear){ / *Cuando la cola no está vacía*/
b=Queue[front++] /*El elemento principal de la cola se retira de la cola y se accede a este nodo*/
printf("%2c", b->data);
if (b->lchild!=NULL) Queue[rear++]=b->lchild; el subárbol izquierdo no está vacío, luego ingrese la cola*/
if (b->rchild!=NULL) Queue[rear++]=b->rchild /*El subárbol derecho no está vacío, luego ingrese; la cola*/
}
}
}//LevelOrder
int profundidad(BiTree T){ /*Encontrar la profundidad del árbol binario*/
int dep1,dep2;
if (T==NULL) devuelve 0;
else {dep1=profundidad(T- >lchild);
dep2=profundidad(T->rchild);
return dep1>dep2?dep1+1:dep2+1;
}
}//profundidad
main(){
BiTree T=NULL;
printf("\nCrear una B
árbol binario\n");
CreateBiTree(&T); /*Crear un árbol binario T*/
printf("\nEl pedido anticipado es:\n");
PreOrder(T); /*Recorrido de preorden de un árbol binario*/
printf("\nEl orden de los niveles es:\n");
LevleOrder( T) ; /*Recorrido jerárquico de árboles binarios*/
printf("\nLa profundidad es:%d\n",profundidad(T));
}
Datos de prueba
1. Entrada: #↙, cree un árbol vacío,
No hay salida para el recorrido de pedido previo y el recorrido jerárquico, y la salida de profundidad de el árbol es 0;
2. Entrada: A↙
La salida del preorden y el recorrido jerárquico son ambas A;
La salida en profundidad es: 1
3. Entrada: ABC# #DE#G##F###↙,
La salida del pedido anticipado es: A B C D E G F
La salida del recorrido de nivel es: A B C D E F G<. /p>
La salida de profundidad es: 5
p>Instrucciones
1. Ingrese los valores de los nodos en el árbol binario en orden, usando '#'. para representar un árbol vacío Para cada nodo, se debe determinar el valor de sus subárboles izquierdo y derecho (para cuando está vacío, se debe usar un carácter vacío específico), por lo que al ejecutar este programa, es mejor dibujar el árbol binario que usted. desea construir en papel. Se deben determinar los subárboles izquierdo y derecho de cada nodo. Si está vacío, use una marca específica y luego ingrese la secuencia de caracteres de este árbol binario en orden;
2. Para simplificar la cantidad de escritura del programa y hacerlo más claro, el acceso al nodo se representa mediante una declaración de salida. Si tiene accesos más complejos o múltiples, puede escribir el acceso al nodo como una función. y luego llame a la función a través del puntero de función. Si está interesado, puede escribirlo usted mismo
.