Home PC Games Linux Windows Database Network Programming Server Mobile  
           
  Home \ Programming \ To convert into a binary search tree sorted doubly linked list     - Ubuntu 12.04 installation DHCP Server (Server)

- Ubuntu 14.04 to install file editor KKEdit 0.1.5 version (Linux)

- CentOS replaces update source and Linux kernel compilation summary (Linux)

- Installation Yarock 1.1.4 Music Player in Ubuntu (Linux)

- Java Concurrency -volatile keywords (Programming)

- How to Upgrade Ubuntu GNOME 14.10 to GNOME 3.16 Desktop (Linux)

- Apache Spark1.1.0 deployment and development environment to build (Server)

- Mongo-connector integrated MongoD to achieve incremental Solr index (Server)

- The formatted Linux hard drive and mount (Linux)

- Timing task Crontab under Linux system (Linux)

- MySQL 5.6 use GTIDs build the master database (Database)

- Linux gprof oprofiling and performance testing tools (Linux)

- Analysis: Little Notebook facing a major security threat secure online (Linux)

- Git Rebase Tutorial: Using Git Rebase turn back the clock (Linux)

- Talk about Java EE Learning (Programming)

- RedHat / CentOS ext4 partition can not be formatted large supplementary ext4 formatting (Linux)

- How to configure a development environment elegant Lua (Linux)

- Delay for the specified IP port analog network to send and receive packets on Linux (Linux)

- Django how to generate content in non-HTML formats (Programming)

- The security configuration of Linux (Linux)

 
         
  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:      
 
- Oracle 11g RAC manually playing GI PSU patch (11.2.0.4.8) (Database)
- Generic mechanism C11 standard (Programming)
- Change CentOS 7 NIC name eno16777736 to eth0 (Linux)
- How to use the character in C ++ without pressing the Enter key to enter the Show (Programming)
- OGG-03510 Problem (Database)
- C # function (Programming)
- MongoDB common optimization settings in Linux (Database)
- Linux System Getting Started Tutorial: How to update outdated version of Ubuntu (Linux)
- High-performance JavaScript loaded and executed (Programming)
- Graphical development environment to build Android under Ubuntu 11.04 (Linux)
- Linux platform to prevent hackers to share practical skills (Linux)
- Iptables Instructions (Linux)
- Linux and Unix systems really do network more secure (Linux)
- Timeout control related to Python threads and a simple application (Programming)
- Nginx concerning the location and rewrite applications proxy_pass (Server)
- CentOS / RHEL 6 was repeated prohibited under the SNMP connection log (Server)
- Effective Java - lazy initialization (Programming)
- ADSL router to defend their own network security methods (Linux)
- Install minimize RHEL / CentOS 7 some things need to do (Linux)
- Linux virtual machine how to access the Internet in a virtual machine when using NAT mode (Linux)
     
           
     
  CopyRight 2002-2022 newfreesoft.com, All Rights Reserved.