Home PC Games Linux Windows Database Network Programming Server Mobile  
           
  Home \ Programming \ To convert into a binary search tree sorted doubly linked list     - The correct way to open Xcode - Debugging (Programming)

- Linux Study of --CentOS create local yum repository (Linux)

- Spring + Log4j + ActiveMQ remote logging - Analysis of combat (Server)

- Infinispan 8 new Redis cache storage implementation (Linux)

- OS X CAOpenGLLayer how to enable OpenGL 3.2 core profile (Programming)

- How to build Memcached Docker container (Server)

- Java Set and List in the relationship and difference (Programming)

- Zabbix configuration external network mail alarm (Server)

- mysql_config_editor encryption and decryption of the new features of MySQL realization (Database)

- Connect to the Oracle Database Help class (Database)

- How Glances monitoring system on Ubuntu (Linux)

- To install the latest version of the EPEL on CentOS 5.x or 6.x (Linux)

- Linux common network tools: hping Advanced Host Scan (Linux)

- Installation of network monitoring ntopng under CentOS 6.4 (Linux)

- The method of Linux into the rescue mode (Linux)

- Hazelcast integration with MongoDB (Database)

- How to use SVN to manage our source code (Server)

- MySQL bulk insert data script (Database)

- Android Get App version number and version name (Programming)

- DRBD daily management (Server)

 
         
  To convert into a binary search tree sorted doubly linked list
     
  Add Date : 2018-11-21      
         
         
         
  Title: Enter a search tree two yuan, two yuan to find the tree into a sort of two-way linked list. Requirements can not create any new node, adjust the pointers point only.
For example, dibasic search tree
10
/ \
614
/ \ / \
481216
Converted into a doubly linked list

4 = 6 = 8 = 10 = 12 = 14 = 16.

Ideas: a lot of problems for the tree, you can use the recursive method to deal with. This question is no exception. Our most basic way of considering this topic.

The right to a binary programming doubly linked list, the final is an ordered sequence, that is, after the results of traversal, then when we use the traversal traverse binary tree traversal to a node, the node is a preamble pointer to the current node, then left pointer points to the preamble of the current node node, then the node so that the preamble refers to the current node.

BinTree * head = NULL;
void helper (BinTree * root, BinTree * & pre)
{
 if (root == NULL && root == NULL)
  return;
  
 helper (root-> left, pre);
 if (head == NULL)
  head = root;
 if (pre == NULL)
  pre = root;
 else
 {
  root-> left = pre;
  pre-> right = root;
  pre = root;
 }
 // Cout < < root-> value < < "" < < endl;
 helper (root-> right, pre);
}
BinTree * SearchTreeConverstToList (BinTree * root)
{
 BinTree * pre = NULL;
 helper (root, pre);
 return head;
}

Thought two: If the current node, we put the right sub-tree into a doubly linked list, and then left sub-tree into a doubly linked list, when we marked the conversion of the head node and tail node of the list, so we only need to the current node and tail left subtree is connected to the head and right subtree is connected to.

void helper_second (BinTree * root, BinTree * & head, BinTree * & tail)
{
 if (root == NULL || (root-> left == NULL && root-> right == NULL))
 {
  head = root;
  tail = root;
  return;
 }
 BinTree * left_head = NULL;
 BinTree * left_tail = NULL;
 BinTree * right_head = NULL;
 BinTree * right_tail = NULL;
 
 helper_second (root-> left, left_head, left_tail);
 helper_second (root-> right, right_head, right_tail);

 if (left_head == NULL)
  head = root;
 else
 {
  head = left_head;
  left_tail-> right = root;
  root-> right = left_tail;
 }
 if (right_head == NULL)
  tail = root;
 else
 {
  tail = right_tail;
  root-> right = right_head;
  right_head-> left = root;
 }
}

BinTree * ConverstToList (BinTree * root)
{
 BinTree * head = NULL;
 BinTree * tail = NULL;
 helper_second (root, head, tail);
 return head;
}
     
         
         
         
  More:      
 
- ORA-01000 Solution (Database)
- Difference Redhat5 and 6 YUM source configuration (Linux)
- Thinking in Java study notes - initialization and cleanup (Programming)
- Linux FTP setting file description (Server)
- Android development, may cause a memory leak problem (Programming)
- Linux basic articles of the boot process (Linux)
- MySQL Data Types (Database)
- DDOS Attacks and Prevention (Linux)
- Management and application Oracle external table (Database)
- MongoDB study notes - polymerization (Database)
- Linux commands to access the cheat sheet (Linux)
- Linux use additional rights (Linux)
- MySQL + Corosync + Pacemaker + DRBD build highly available MySQL (Server)
- Oracle 12c of the auto-increment Identity Columns (Database)
- Eclipse remove all comments and code spaces (Linux)
- cat command uses the Linux redirection merge files (Linux)
- Installation Mesos + Marathon + Zookeeper under CentOS 7 (Server)
- The callback function used in C ++ (Programming)
- Java object serialization (Programming)
- shell script: MySQL startup script simple (Database)
     
           
     
  CopyRight 2002-2022 newfreesoft.com, All Rights Reserved.