首页 / 操作系统 / Linux / 编程算法 - 中序遍历 递归/迭代 代码（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本文永久更新链接地址：http://www.linuxidc.com/Linux/2014-10/107627.htm