Преобразувайте листата на двоично дърво в двойно свързан списък

При дадено двоично дърво и препратка към коренния възел на дървото, трансформирайте листовите възли на дървото в двойно свързан списък в последователност по ред.

Този проблем може да бъде разделен на части — Намерете листовите възли на двоично дърво и даден набор от елементи, формирайте двойно свързан списък, като ги използвате.

Намерете листовите възли на двоично дърво -

За да обходим двоично дърво, можем да обходим дървото с помощта на алгоритми за обхождане в предварителна поръчка, по ред или след поръчка.

Обхождане на предварителна поръчка — ROOT -› НАЛЯВО -› НАДЯСНО

Обхождане по ред — НАЛЯВО -› КОРЕН -› НАДЯСНО

Traversal след поръчка — НАЛЯВО -› ДЯСНО -› КОРЕН

Решението на текущия проблем използва Inorder Traversal.

Алгоритъмът за Inorder Traversal е както следва:

1) Въведете основния възел.

2) Ако основният (текущият) възел няма ляво или дясно дете, тогава това е листов възел, в противен случай отидете на стъпка (3)

3) Ако коренният възел е NULL, тогава върнете else goto стъпка (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.