bintree.h

二叉树的非递归遍历算法 可以直接上交

#ifndef BinTree_H
#define BinTree_H

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

// 二叉树结点的结构定义
template <class T>
struct BinTreeNode  
{ T data;
  BinTreeNode<T> *lchild, *rchild;
};
  
enum TravFlag{START,LEFT,RIGHT};

template <class T>
class Status        // 遍历状态类
{ 
public:
  BinTreeNode<T> *p; // 遍历中的位置
  TravFlag flag;     // 遍历中的方向
  void NextFlag()
  { if(flag==START) { flag=LEFT;  return; }
    if(flag==LEFT ) { flag=RIGHT; return; }
  }
};

// 二叉树类定义
template <class T>
class BinTree  
{
  BinTreeNode<T>* m_Root; 
public:    
  BinTree();
  ~BinTree();
  BinTree(vector<T> &pre); // 根据pre创建二叉树
  void Free();  // 释放整个树的空间
  void TraverseDFS(int kind); // 深度遍历二叉树
private:
  // 仅与CreateByPre函数相关的私有成员
  vector<T> m_pre; int m_prei;
  BinTreeNode<T> *DoCreateByPre();
  // 仅与Free函数相关的私有成员
  void DoFree(BinTreeNode<T> *p);
};

#endif