二叉树的遍历
广度优先遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| template <class T>
void BinaryTree<T>::levelOrder(BinaryTreeNode<T> *root)
{
using std::queue;
queue<BinaryTreeNode<T> *> nodeQueue;
BinaryTreeNode<T> *pointer = root;
if (pointer)
nodeQueue.push(pointer);
while (!nodeQueue.empty())
{
pointer = nodeQueue.front();
visit(pointer);
nodeQueue.pop();
if (pointer->leftChild)
nodeQueue.push(pointer->leftChild);
if (pointer->rightChild)
nodeQueue.push(pointer->rightChild);
}
}
|
深度优先遍历
递归算法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
|
template <class T>
void BinaryTree<T>::preOrder(BinaryTreeNode<T> *root)
{
if (root != nullptr)
{
visit(root);
preOrder(root->leftChild);
preOrder(root->rightChild);
}
}
template <class T>
void BinaryTree<T>::inOrder(BinaryTreeNode<T> *root)
{
if (root != nullptr)
{
inOrder(root->leftChild);
visit(root);
inOrder(root->rightChild);
}
}
template <class T>
void BinaryTree<T>::postOrder(BinaryTreeNode<T> *root)
{
if (root != nullptr)
{
postOrder(root->leftChild);
postOrder(root->rightChild);
visit(root);
}
}
|
非递归算法
前序遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| template <class T>
void BinaryTree<T>::PreOrderWithoutRecusion(BinaryTreeNode<T> *root)
{
using std::stack;
stack<BinaryTreeNode<T> *> nodeStack;
BinaryTreeNode<T> *pointer = root;
while (!nodeStack.empty() || pointer)
{
if (pointer)
{
visit(pointer);
if (pointer->rightChild)
nodeStack.push(pointer->rightChild);
pointer = pointer->leftChild;
}
else
{
pointer = nodeStack.top();
nodeStack.pop();
}
}
}
|
中序遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| template <class T
void BinaryTree<T>::InOrderWithoutRecursion(BinaryTreeNode<T> *root)
{
using std::stack;
stack<BinaryTreeNode<T> *> nodeStack;
BinaryTreeNode<T> *pointer = root;
while (!nodeStack.empty() || pointer)
{
if (pointer)
{
nodeStack.posh(pointer);
pointer = pointer->leftChild;
}
else
{
pointer = nodeStack.top();
visit(pointer);
pointer = pointer->rightChild;
nodeStack.pop();
}
}
}
|
后续遍历
template
void BinaryTree::PostOrderWithoutRecursion(BinaryTreeNode *root)
{
using std::stack;
stack<BinaryTreeNode *> nodeStack;
BinaryTreeNode *pointer = root;
BinaryTreeNode *pre = root;
while (pointer)
{
while (pointer->leftChild)
{
nodeStack.push(pointer);
pointer = pointer->leftChild;
}
while (pointer && (pointer->rightChild) || pointer->rightChild == pre)
{
visit(pointer);
pre = pointer;
if (nodeStack.empty())
return;
pointer = nodeStack.top();
nodeStack.pop();
}
nodeStack.push(pointer);
pointer = pointer->rightChild;
}
}