Home PC Games Linux Windows Database Network Programming Server Mobile  
           
  Home \ Linux \ Binary Tree Traversal     - Linux RPM default installation path (Linux)

- Ubuntu 14.04 configure JDK1.8.0_25, switchable version (Linux)

- Java implementation chain store binary tree (Programming)

- Oracle 11g creates virtual private directory RMAN-06004 ORA-00942 error handling (Database)

- Node.js developers must know four JavaScript concepts (Programming)

- IO reference Docker container (Server)

- Analysis examples: Intrusion Response Linux platform Case (Linux)

- Open MySQL slow query log (Database)

- Ubuntu 14.04 / Linux Mint 17 How to install the MintMenu 5.5.2 menu (Linux)

- SSH port forwarding application (Server)

- MySQL remote connection settings (Database)

- The source code compiler installation Nginx 1.8.0 under Ubuntu 14.10 (Server)

- Git uses a small mind (Linux)

- Linux `dirname $ 0` (Linux)

- Linux process or thread is bound to a CPU (Programming)

- To build a private Docker registry (Server)

- Hibernate4 The Hello World (basic environmental structures) (Programming)

- When the master key encounter NULL (Database)

- Lenovo Ultrabooks Ubuntu system can not open the wireless hardware switch solutions (Linux)

- CentOS 6.6 x64 Oracle Database 11gR2 RAC automated installation scripts (Database)

 
         
  Binary Tree Traversal
     
  Add Date : 2018-11-21      
         
         
         
  Sequential storage structure binary tree is to use a one-dimensional array to store the binary tree node, and the storage location node, that is, the array index to be able to reflect the logical relationships between nodes. -> Is generally used only for complete binary tree
Chain store -> binary list
Definitions: lchild | data | rchild (two pointer fields, a data field)

typedef struct Node {
     ElemType data;
     struct Node * lchild, * rchild;
} BiTnode, * BiTree;
be careful:
1) known before preorder traversal sequence and sequences can uniquely identify a binary tree
2) known preorder traversal sequence after sequence and sequences can uniquely identify a binary tree
The preamble is known and can not be determined after the order is a binary tree

Binary tree traversal: means starting from the root node, according to some order in turn have access to all the nodes in the binary tree such that each node is visited once and only be accessed once.

1, preorder traversal: root - left - right

Code:

void PreOrder (BiTree T) / * preorder: root - left - right * /
{
    if (T! = NULL)
    {
        Visit (T); / * access to the root node * /
        PreOrder (T-> lchild); / * access left child node * /
        PreOrder (T-> rchild); / * access the right child * /
    }
}

2, preorder: Left - Root - Right
Code:

void InOrder (BiTree T) / * preorder: Left - Root - Right * /
{
    if (T! = NULL)
    {
        InOrder (T-> lchild); // Left
        Visit (T); // Root
        InOrder (T-> rchild); // Right
    }
}

3, postorder: left - right - Root

Code:

void PostOrder (BiTree T) / * postorder: left - right - root * /
{
    if (T! = NULL)
    {
        PostOrder (T-> lchild); // Left
        PostOrder (T-> rchild); // Right
        Visit (T); // Root
    }
}

4, sequence traversal: starting from the root, and then click Access around the child node, and then starting from children around, turn their child nodes, access nodes until completion

Code: The program uses the idea of a queue, you can refer to the diagram to understand
(This figure shows the breadth-first traversal schematic diagram, the application layer is traversing Thought)

/ * Layer preorder idea: in order from left to right to access each node layer by layer, layer-order traversal process requires queue * /
void LevelOrder (BiTree T)
{
    BiTree p = T;

    queue < BiTree> queue; / * queue * /
    queue.push (p); / * * the root into the team /

    while (! queue.empty ()) / * queue is not empty loop * /
    {
        p = queue.front (); / * head element dequeue * /
        // Printf ( "% c", p-> data); / * p points to access node * /
        cout < < p-> data < < "";

        queue.pop (); / * exit queue * /
        if (p-> lchild! = NULL) {/ * left subtree is not empty, the left subtree into the team * /
            queue.push (p-> lchild);
        }
        if (p-> rchild! = NULL) {/ * is not empty right subtree, the right subtree into the team * /
            queue.push (p-> rchild);
        }
    }
}
     
         
         
         
  More:      
 
- Confrontation dragged Library - Web front-end encryption slow (Linux)
- The ORA-01113 error is handled with BBED without archiving (Database)
- Distributed File System using MogileFS (Linux)
- PHP parsing algorithm of the interview questions (Programming)
- Java regular expression syntax (Programming)
- MongoDB version 3.2 WiredTiger storage engine performance tests (Database)
- Shell scripts quickly deploy Tomcat project (Server)
- Use small network command to check whether PC Security (Linux)
- The most concise explanation of JavaScript closures (Programming)
- QEMU code analysis: BIOS loading process (Linux)
- Linux Basics Tutorial: Combining awk delete data before the specified date hdfs (Linux)
- Puppet 3.x installed on Debian 7 (Server)
- Linux dd command applies amplification SWAP partition (Linux)
- Common data structures and functions of Linux process scheduling (Programming)
- Linux system monitoring tool set cpu (Linux)
- ethtool command Detailed (Linux)
- Firewall types and instructions (Linux)
- Linux foreground to background process switch (Linux)
- AngularJS - Custom instructions (Programming)
- Linux vi command list (Linux)
     
           
     
  CopyRight 2002-2022 newfreesoft.com, All Rights Reserved.