| |
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);
}
}
} |
|
|
|