編程算法 - 中序遍歷 遞歸/迭代 代碼(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