Home IT Linux Windows Database Network Programming Server Mobile  
  Home \ Linux \ Binary Tree Traversal     - Installing Linux and Windows 10 dual system (Linux)

- Elaborate 10-point difference between the new and malloc (Programming)

- How to deploy Icinga server (Server)

- Oracle 11G R2 DataGuard structures (Database)

- To create someone else can not afford to delete the administrator user (Linux)

- Execute command sentence can result in equipment permanently bricked in Linux laptop (Linux)

- Github Getting Started Basic Course (Linux)

- Linux / Windows setup is complete port range (Linux)

- OpenDaylight Helium version installed (Linux)

- ORA-00600 error solve one case (Database)

- Linux and SELinux Exploration Program Manager (Linux)

- innodb storage engine backup tool --Xtrabackup (Database)

- Java data structures - the single linked list LinkedList linear table (Programming)

- Do not find ifconfig eth0 and IP address under CentOS6.5 (Linux)

- How to ensure that the Internet will not be attacked (Linux)

- Oracle 12C RAC optimizer_adaptive_features cause of data into overtime (Database)

- Oracle how to maintain the consistency of read? (Database)

- Use Mop monitor stock prices at the Linux command line (Linux)

- Use mod_wsgi Django application deployment (Server)

- Zabbix Agent (Server)

  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


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

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


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);
- SecureCRT 7.0 Log Ubuntu 12.04 server via SSH service under Vmware (Server)
- Install the free open source financial software GnuCash 2.6.6 under Ubuntu (Linux)
- Without Visual Studio .NET Windows application development (Programming)
- MySQL Statistics (Database)
- ARM constant expression (Programming)
- SQLite (Database)
- The new task parallel library feature in .NET 4.6 (Programming)
- Linux kernel network subsystem analysis (Programming)
- Docker ecosystem security is gradually maturing (Server)
- Linux common commands ll namely ls -l --color = auto (Linux)
- Linux, how to filter, split, and merge pcap file (Linux)
- Linux kernel update error, update-initramfs: failed Solution (Linux)
- How to modify the SQL Server auto-increment value and the corresponding solution (Database)
- How to install Perl modules from CPAN (Linux)
- Openfire achieve load balancing cluster by Nginx (Server)
- ORA-00845: MEMORY_TARGET not supported on this system Problem (Database)
- Search Linux commands and files - which, whereis, locate, find (Linux)
- Linux Getting Started tutorial: XWindow what (Linux)
- Ubuntu How to mount iso file (Linux)
- CentOS 6.5 three ways to configure the IP address (Linux)
  CopyRight 2002-2016 newfreesoft.com, All Rights Reserved.