日期：2017-7-8
思路：二叉树中序遍历
*/
#include <iostream> #include <string> #include <vector> #include <stack> using namespace std; template <typename T> class tnode { public: T nodeValue; tnode<T> *left, *right; tnode(){ } tnode(const T& item, tnode<T> *lptr = NULL, tnode<T> *rptr = NULL) { nodeValue = item; left = lptr; right = rptr; } }; //中序遍历（递归） template <typename T> void inorderOutput(tnode<T> *t, const string& separator = " ") { if (t != NULL) { inorderOutput<T>(t->left, separator); cout << t->nodeValue << separator; inorderOutput<T>(t->right, separator); } } //中序遍历（非递归） template <typename T> tnode<T>* inorderOut(tnode<T>* root) { //if (root == NULL) // return ; tnode<T>* p = root; tnode<T>* max = root; stack<tnode<T>*> stack; while (p != NULL || !stack.empty()) { while (p != NULL) { stack.push(p); p = p->left; } if (!stack.empty()) { p = stack.top(); stack.pop(); if (p->nodeValue > max->nodeValue) max = p; p = p->right; } } return max; }