Home IT Linux Windows Database Network Programming Server Mobile  
           
  Home \ Programming \ Binary tree traversal recursive and non-recursive (cyclic) traversal achieve     - Linux start the process (Linux)

- How to contribute code on GitHub uploads (Linux)

- MySQL stored procedures execute dynamic sql statement (Database)

- LAMP environment to build Apache, MySQL, PHP under Ubuntu (Server)

- 22 Port weak passwords and SSH connection program of the Linux server (Linux)

- Linux --- process tracking (Linux)

- Vim custom color (Linux)

- MySQL 5.6 master-slave replication configuration (Database)

- Using Oracle for Oracle GoldenGate to achieve a one-way data synchronization (Database)

- Nginx start, stop, smooth start, smooth upgrade (Server)

- Advanced network security tips Linux backdoor Technology and Practice (Linux)

- Practical top command (Linux)

- Close Pycharm spell check (Programming)

- Ubuntu 32 compile Android 4.0.4 Problems (Linux)

- Https (SSL / TLS) Detailed principles (Server)

- Let's Encrypt with semiautomatic into Nginx configuration https (Server)

- Oracle to start to solve the error ORA-27102 (Database)

- How to use Evernote in the Linux command line (Linux)

- HAproxy let IP recording back-end RS (Server)

- Android Activity launchMode (Programming)

 
         
  Binary tree traversal recursive and non-recursive (cyclic) traversal achieve
     
  Add Date : 2016-12-18      
         
       
         
  Binary tree traversal recursive and non-recursive (cyclic) traversal achieve

struct BinTree
{
    int data;
    BinTree * left;
    BinTree * right;
};
Recursive version

void PreOrder (BinTree * root)
{
    if (root! = nullptr)
    {
        cout < < root-> data;
        PreOrder (root-> left);
        PreOrder (root-> right);
    }
}
Loop version

Access node p and node p stack
P node to determine whether the child is left empty, if not empty, then the output of the left child, and P point to the new left child until the child is left empty
If the child is left empty, this time left the child's parent node have been output is completed, then the parent node in the stack, it will point to the right child p stack node, traverse the right branch
Until the pointer is NULL and the stack is empty, traversal ends
Preorder only need to adjust the output statement
void PreOrder (BinTree * root)
{
    stack < BinTree *> s;
    BinTree * p = root;
    while (p! = nullptr ||! s.empty ())
    {
        while (p! = nullptr)
        {
            cout < < p-> data < < "";
            s.push (p);
            p = p-> left;
        }
        if (! s.empty ())
        {
            p = s.top ();
            s.pop ();
            p = p-> right;
        }
    }
}
After traversing cycle harder to achieve

To ensure access to the root after the kids left and right child access, so for any node P, the first of its stack. P If there is no left child and right child, you can access it directly; or in the presence of P left child or right child, but the child left and right children have been visited, you can also directly access the node. If not the above two cases, then P's right child and left child turn the stack, thus ensuring each taking the top element when the child was left in front of the access right child, left child and right child at the root knot access point is in front

void postOrder (BinTree * root) // preorder after non-recursive
{
    stack < BinTree *> s;
    // Current node; BinTree * cur
    BinTree * pre = NULL; // first visit to the former node
    s.push (root);
    while (! s.empty ())
    {
        cur = s.top ();
        if ((cur-> lchild == NULL && cur-> rchild == NULL) ||
           (Pre! = NULL && (pre == cur-> lchild || pre == cur-> rchild)))
        {
            cout < < cur-> data < < ""; // if the current node is no child node or child nodes have been visited
              s.pop ();
            pre = cur;
        }
        else
        {
            if (cur-> rchild! = NULL)
                s.push (cur-> rchild);
            if (cur-> lchild! = NULL)
                s.push (cur-> lchild);
        }
    }
}
     
         
       
         
  More:      
 
- Lsblk command lists using Linux block device information (Linux)
- Customize own small private Linux system (Linux)
- Linux operating system Start Tutorial: Xmanager Remote Access Linux graphical interface (Linux)
- C # C ++ Java interface type conversion (Programming)
- Add a custom encryption algorithm in OpenSSL (Linux)
- [Android] Eclipse does not update the Android SDK Manager solution [using GoAgent] (Programming)
- Oracle SQL statement to retrieve data paging table (Database)
- Object Oriented Programming Java reflection (Programming)
- Firewall types and instructions (Linux)
- Using VMware vSphere Client Linux virtual machine installation CentOS6.4 system (Linux)
- Ubuntu 14.04 LTS compiler installation R Source Code (Linux)
- Tmux Getting Start (Linux)
- Teach you to diagnose problems with strace (Linux)
- CentOS 6.5 installation using a data recovery software extundelete (Linux)
- Ubuntu file security removal tool (Linux)
- Linux kernel socket protocol stack routing lookup cache mechanism (Linux)
- LVM management reduces swap partition space to the root partition (Linux)
- MySQL uses mysqld_multi to deploy stand-alone multi-instance detail procedures (Database)
- Ubuntu install Wireshark (Linux)
- Java memory mechanism Description (Programming)
     
           
     
  CopyRight 2002-2016 newfreesoft.com, All Rights Reserved.