Home PC Games Linux Windows Database Network Programming Server Mobile  
           
  Home \ Programming \ To convert into a binary search tree sorted doubly linked list     - Ubuntu Tutorial - Manually install Oracle Java JDK 8 (Linux)

- Ubuntu Linux Change the PATH (Linux)

- Oracle () trunc function usage (Database)

- Docker knowledge base (Server)

- Vim useful plugin: EasyGrep (Linux)

- Under CentOS Linux automatic backup MySQL database daily (Database)

- Oracle data row split multiple lines (Database)

- Setting up Linux machine through a proxy firewall (Linux)

- How to install the client sqlplus under linux (Database)

- To install Samba server on CentOS 6.6 (Server)

- Linux character device - user mode and kernel mode data transfer data (Linux)

- LVM Disk Manager Application (Linux)

- Linux settings Java_home (Linux)

- Java MD5 encryption implementation (Programming)

- Hibernate Search and Lucene quick introduction (Linux)

- GitLab Installation Guide -Ubuntu 14.04 LTS (Server)

- Redis performance test (Database)

- How to remove the files inside the privacy of data on Linux (Linux)

- To install the mail client terminal Evolution 3.13.2 under Ubuntu 14.04 (Linux)

- C ++ Supplements - locates the new expression (Programming)

 
         
  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:      
 
- Hadoop 0.23 compile common errors (Server)
- Java multi-threaded shared communications variables (Programming)
- Ubuntu install code editor Sublime Text 3 (Linux)
- C ++ Object Model Comments (Programming)
- VMware virtual machine can not start VMnet0 no Internet access and other issues (Linux)
- Installation on Ubuntu class Winamp audio player Qmmp 0.9.0 (Linux)
- Ubuntu 14.04 compile and install Apache (Server)
- Android Dynamic efficiency articles: a brilliant Loading Analysis and Implementation (Programming)
- Linux system performance and usage activity monitoring tools -Sysstat (Linux)
- State and Linux nf_conntrack TCP disconnect time (Programming)
- Wine 1.7 is installed on a system based on RedHat or Debian (Linux)
- Linux system security settings after installation (Linux)
- Configuring Proxy on a Unix terminal, accelerate Android Studio Construction (Linux)
- Java Foundation - Getting Start (Programming)
- Linux user opens a number of adjustment processes (Linux)
- MySQL5.7 implement virtual column expression index (Database)
- Getting Started with Linux system to learn: how to install the Shrew Soft IPsec VPN on Linux (Linux)
- Help you enhance Python programming languages 27 (Programming)
- CentOS 6.5 start ActiveMQ being given to solve (Server)
- Android Fragment everything you need to know (Programming)
     
           
     
  CopyRight 2002-2020 newfreesoft.com, All Rights Reserved.