Преобразование листьев бинарного дерева в двусвязный список

Имея двоичное дерево и ссылку на корневой узел дерева, преобразуйте конечные узлы дерева в двусвязный список в неупорядоченной последовательности.

Эту задачу можно разбить на части: найти листовые узлы бинарного дерева и, учитывая набор элементов, сформировать из них двусвязный список.

Найти конечные узлы бинарного дерева —

Чтобы пройти по бинарному дереву, мы можем пройти по дереву, используя алгоритмы обхода в предварительном, неупорядоченном или постпорядковом порядке.

Обход предзаказа — ROOT -> LEFT -> RIGHT

Порядок обхода — ЛЕВЫЙ -> КОРЕНЬ -> ПРАВЫЙ

Последовательность ОБХОД — ВЛЕВО -> ВПРАВО -> КОРЕНЬ

Решение текущей проблемы использует Inorder Traversal.

Алгоритм обхода по порядку следующий:

1) Введите корневой узел.

2) Если у корневого (текущего) узла нет левого или правого дочернего элемента, то это конечный узел, в противном случае перейдите к шагу (3)

3) Если корневой узел равен NULL, вернитесь к шагу (4).

4) Прочитайте корневой узел левого поддерева и перейдите к шагу (1).

5) Распечатать значение текущего узла.

6) Прочитайте корневой узел правого поддерева и перейдите к шагу (2).

По заданному набору элементов сформируйте из них двусвязный список -

Структура данных для узла двусвязного списка:

Двусвязный список отличается от односвязного списка тем, что в двусвязном списке мы можем перемещаться в обоих направлениях, слева направо и справа налево, тогда как в односвязном списке мы можем перемещаться только в одном направлении. либо слева направо, либо справа налево.

Мы можем сформировать двусвязный список из заданных элементов, связав узлы друг с другом, итерируя до последнего узла и связывая текущий узел с последним узлом текущего связанного списка.

Приведенный ниже код написан на языке программирования C.

#include<stdio.h>
#include<stdlib.h>

struct node{
  struct node *left;
  int data;
  struct node *right;
};

struct node *head = NULL;
void leavesToDll(struct node *leaf){
  struct node *first;
  if(head == NULL){
    head = leaf;
  }
  else{
    first = head;
    while(first -> right != NULL){
      first = first -> right;
    }
    first -> right = leaf;
    leaf -> left = first;
 }
}

void inorderTraversal(struct node *root){
  if(root -> left == NULL && root -> right == NULL){
    leavesToDll(root);		
  }
  else if(root == NULL){
    return;
  }
  else{
    inorderTraversal(root -> left);
    inorderTraversal(root -> right);
  }
}

struct node *newNode(int data){
  struct node *n = (struct node *)malloc(sizeof(struct node *));
  n -> data = data;
  n -> left = NULL;
  n -> right = NULL;
  return n;
}

void main(){
  struct node *n = newNode(1);
  n -> left = newNode(2);
  n -> left -> left = newNode(4);
  n -> left -> right = newNode(5);

  n -> right = newNode(3);
  n -> right -> left = newNode(6);
  n -> right -> right = newNode(7);	
	
  inorderTraversal(n);

  while(head -> right != NULL){
    printf("%d\n", head -> data);
    head = head -> right;
  }
  printf("%d\n", head -> data);
}

Первоначально опубликовано на http://asquero.com.