Home PC Games Linux Windows Database Network Programming Server Mobile  
           
  Home \ Programming \ To convert into a binary search tree sorted doubly linked list     - Python system default encoding (Programming)

- Oracle bdump file soaring (Database)

- To install and use Docker under linux (Server)

- MySQL Online DDL tools of pt-online-schema-change (Database)

- Ten to improve the efficiency of the Linux bash tricks (Linux)

- Installation Elementary OS Freya 20 things to do (Linux)

- Linux scheduling summary (Linux)

- Common Linux System Troubleshooting (Linux)

- lolcat: an output terminal rainbow effects in the Linux command-line tool (Linux)

- ASM Management - How to Rename diskgroup (Database)

- Installation and deployment of MariaDB under CentOS (Database)

- Linux at command (Linux)

- Use Bosh deploy CloudFoundry problems encountered on OpenStack (Server)

- Compile and install Memcached can not find GCC (Programming)

- MySQL Tutorial: Using tpcc-mysql pressure measurement (Database)

- JDK installation and configuration environment variable under linuxb (Linux)

- Linux, MySQL root privilege escalation another method (Linux)

- Linux common network tools: ping host sweep (Linux)

- Python script file directory traversal examples (Programming)

- CentOS 6.5 platform offline compile and install PHP5.6.6 (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:      
 
- Linux Getting Started tutorial: Borrow Windows fonts in Ubuntu 14.10 (Linux)
- Ubuntu install video conversion tool Selene (Linux)
- Use scripts easily install the latest Linux kernel in Ubuntu (Linux)
- pureftpd basis: Install, configure, implement, anonymous logon (Linux)
- How Bluetooth turned off by default in Ubuntu 14.04 (Linux)
- Arrow keys, backspace key garbled in Python-2.7.5 Interactive Mode under CentOS 5.8 (Linux)
- Oracle database NUMBER (x, y) data types (Database)
- Shell array: Define Shell array, the array length (Programming)
- MySQL to recover the data through binlog (Database)
- Nginx configuration support f4v video format player (Server)
- Sublime Text 3 practical functions and shortcut keys used to collect (Linux)
- Simple security measures to reinforce the Linux kernel (Linux)
- MySQL 5.6.26 source install (Database)
- Installation and Configuration JDK8 In CentOS 7 (Linux)
- Python, and / or (Programming)
- Oracle 12C modify spfile path (Database)
- Tomcat installation under Linux (Server)
- Virtual Judge structures under Ubuntu 14.04 (Server)
- build Android environment on Ubuntu 12.04 (Server)
- Intruder tools Knark Analysis and Prevention Linux environment (Linux)
     
           
     
  CopyRight 2002-2022 newfreesoft.com, All Rights Reserved.