Home IT Linux Windows Database Network Programming Server Mobile  
           
  Home \ Programming \ Binary tree traversal recursive and non-recursive (cyclic) traversal achieve     - Repair fatal error in Linux: lame / lame.h: No such file or dir Error (Linux)

- Build ftp server under CentOS 6.5 (Server)

- Oracle lag () and lpad () function (Database)

- Android 5.1 OTA package compilation error (Programming)

- Linux - EXT2 file system is described in detail (Linux)

- Linux System Getting Started Tutorial: how to find information on Linux-embedded module (Linux)

- Some MySQL interview questions (Database)

- Debian 8 (amd64) installation deployment Memcached management tools MemAdmin (Server)

- Linux stand-alone OGG synchronous Oracle 11g DB test (Database)

- Linux Apache server configure to protect system security (Linux)

- Linux shell scripts bubble sort (Programming)

- Alien Magic: RPM and DEB Mutual Convert (Linux)

- Java enum use (Programming)

- Linux SSH remote connection service slow Solutions (Linux)

- mysqldump MySQL command-line tool (Database)

- To install and configure the Jetty server and JDK under Ubuntu 14.04.2 (Server)

- Linux dd command applies amplification SWAP partition (Linux)

- Docker + OpenvSwitch build experimental environment VxLAN (Server)

- Terminal fun: 6 interesting Linux command-line tools (Linux)

- Linux System Getting Started Tutorial: How to automatically set the JAVA_HOME environment variable on Linux (Linux)

 
         
  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:      
 
- Linux system monitoring, top command of the diagnostic tool Detailed (Linux)
- Hadoop virtualization performance comparison and tuning experience (Server)
- Linux system security infrastructure Highlights (Linux)
- Linux asynchronous read documents by AIO (Programming)
- Linux filtration empty file command summary (Linux)
- 5 interesting Linux command line tips (Linux)
- Sort sql MySQL 5.6 upgrade slow Cause Analysis (Database)
- Gitolite how to import other Git repositories (Server)
- S5PV210 development board for embedded development environment to build under Ubuntu (Linux)
- CentOS7 Kubernetes used on container management (Server)
- HAProxy performance under high concurrency (Server)
- Some Linux networking tools you might not know (Linux)
- Hadoop 2.2.0 installation development environment (standalone pseudo-distributed mode) (Server)
- MySQL group_con cat_max_Len (Database)
- Oracle through the alarm log view and inspect the main library, physical and snapshot standby database (Database)
- Oracle Database asynchronous IO cause slow query response (Database)
- Linux Network Programming - libnet Guide (Programming)
- Linux server dual-card dual-IP and single-card dual-IP configuration method (ReHat / CentOS) (Server)
- Formatted output printf command (Programming)
- Use Bash script write CVS version control (Server)
     
           
     
  CopyRight 2002-2016 newfreesoft.com, All Rights Reserved.