編程算法 - 中序遍歷 遞歸/迭代 代碼(C)

中序遍歷 遞歸/迭代 代碼(C)

中序遍歷(InOrder)作為二叉搜索樹的排序方式, 有著重要的作用.

遞歸和迭代的方法都需要掌握, 迭代主要使用了棧(stack)進行輸入輸出.

代碼:

/*
* main.cpp
*
* Created on: 2014.9.18
* Author: Spike
*/

/*eclipse cdt, gcc 4.8.1*/

#include <iostream>
#include <list>
#include <queue>
#include <stack>
#include <string.h>
#include <stdlib.h>
#include <stdio.h>

using namespace std;

struct BinaryTreeNode {
BinaryTreeNode(int _value) {
value = _value;
left = NULL;
right = NULL;
}

int value;
BinaryTreeNode* left;
BinaryTreeNode* right;
};

void printTree (BinaryTreeNode* tree)
{
BinaryTreeNode* node = tree;
std::queue<BinaryTreeNode*> temp1;
std::queue<BinaryTreeNode*> temp2;

temp1.push(node);

while (!temp1.empty())
{
node = temp1.front();
if (node->left != NULL) {
temp2.push(node->left);
}

if (node->right != NULL) {
temp2.push(node->right);
}

temp1.pop();

std::cout << node->value << " ";

if (temp1.empty())
{
std::cout << std::endl;
temp1 = temp2;
std::queue<BinaryTreeNode*> empty;
std::swap(temp2, empty);
}
}
}

BinaryTreeNode* buildTree (void)
{
BinaryTreeNode* root = new BinaryTreeNode(1);
BinaryTreeNode* node2 = new BinaryTreeNode(2);
BinaryTreeNode* node3 = new BinaryTreeNode(3);
BinaryTreeNode* node4 = new BinaryTreeNode(4);
BinaryTreeNode* node5 = new BinaryTreeNode(5);
BinaryTreeNode* node6 = new BinaryTreeNode(6);
BinaryTreeNode* node7 = new BinaryTreeNode(7);
BinaryTreeNode* node8 = new BinaryTreeNode(8);
BinaryTreeNode* node9 = new BinaryTreeNode(9);
BinaryTreeNode* node10 = new BinaryTreeNode(10);

root->left = node2;
root->right = node3;

node2->left = node4;
node2->right = node5;

node4->left = node6;
node4->right = node7;

node5->left = node8;
node5->right = node9;

node9->left = node10;

return root;
}

void InOrder(BinaryTreeNode *root)
{
if(root == NULL)
return;

stack<BinaryTreeNode*> s;
s.push(root);
BinaryTreeNode* node = root->left;

while (node != NULL || !s.empty())
{
while (node != NULL)
{
s.push(node);
node = node->left;
}
node = s.top();
s.pop();

printf("%d ", node->value);
node = node->right;
}
}

void InOrderR(BinaryTreeNode* root) {
if (root == NULL) return;
InOrder(root->left);
printf("%d ", root->value);
InOrder(root->right);
}

int main (void)
{
BinaryTreeNode* root = buildTree();
printTree(root);
InOrder(root);
cout << endl;
InOrderR(root);
cout << endl;
return 0;
}

輸出:

1
2 3
4 5
6 7 8 9
10
6 4 7 2 8 5 10 9 1 3
6 4 7 2 8 5 10 9 1 3