二叉树

#include <iostream> #include <cassert> #include <queue> #include <stack> using namespace std; template <class T> struct TreeNode { TreeNode(const T& value = T()) :_value(value) ,_lchild(0) ,_rchild(0) {} T _value;//节点的值 TreeNode<T>* _lchild;//左孩子 TreeNode<T>* _rchild;//右孩子 }; template <class T> class BinaryTree { public: typedef TreeNode<T> Node; BinaryTree()//无参构造函数 :_root(NULL) {} BinaryTree(const T* a,size_t size,const T& invalid)//构造函数 { assert(a); size_t index = 0; _root = CreatTree(a,size,invalid,index); } BinaryTree(const BinaryTree<T>& b)//拷贝构造 { _root = Copy(b._root); } //现代写法的赋值运算符重载1 BinaryTree& operator=(const BinaryTree<T>& b) { if (this != &b) { Node* tmp = Copy(b._root); Destroy(_root) ; _root = tmp; //swap(_root,tmp); } return *this; } 现代写法的赋值运算符重载2 //BinaryTree& operator=(BinaryTree<T> b) //{ // swap(b._root,_root); // return *this; //} ~BinaryTree()//析构 { if (NULL != _root) { Destroy(_root); _root = NULL; } } protected: //按照先序遍历递归建树 Node* CreatTree(const T* a,size_t size,const T& invalid,size_t& index)//注意index的传值方式 { assert(a); Node* root = NULL; if (a[index] != invalid && index < size)//按先序遍历建树 { root = new Node(a[index]); root->_lchild = CreatTree(a,size,invalid,++index); root->_rchild = CreatTree(a,size,invalid,++index); } return root; } //拷贝对象 Node* Copy(Node* root) { Node* tmp = NULL; if(root) { tmp = new Node(root->_value); tmp->_lchild = Copy(root->_lchild); tmp->_rchild = Copy(root->_rchild); } return tmp; } //释放空间 void Destroy(Node*& root) { if(root)//用后序遍历方式释放空间 { Destroy(root->_rchild); Destroy(root->_lchild); delete root; root = NULL; } } private: Node* _root;//根节点 }; 2、遍历二叉树 二叉树的遍历方式一共分为四种：先序遍历、中序遍历、后序遍历和层序遍历，而前三种遍历又分为递归遍历和非递归遍历，层序遍历则是借助队列先进先出的特性来辅助完成。 【递归遍历二叉树】 void preorder(Node* root)//先序遍历打印树的各个节点   {  if (root) { cout<<root->_value<<" "; //访问当前节点的值   preorder(root->_lchild); //递归遍历左子树  preorder(root->_rchild); //递归遍历右子树   } }   void inorder(Node* root)//中序遍历打印树的各个节点  { if (root) { preorder(root->_lchild); //递归遍历左子树 cout<<root->_value<<" "; //访问当前节点的值 preorder(root->_rchild); //递归遍历右子树  } } void postorder(Node* root)//后序遍历打印树的各个节点   { if (root) { preorder(root->_lchild); //递归遍历左子树  preorder(root->_rchild); //递归遍历右子树   cout<<root->_value<<" "; //访问当前节点的值  } } void levelorder(Node* root)//层序遍历打印树的各个节点  { queue<Node*> q; if (root)   {   q.push(root);//将根节点插进队列 } while(!q.empty()) { Node* front = q.front(); q.pop(); cout<<front->_value<<" "; if (front->_lchild) { q.push(front->_lchild); }  if (front->_rchild) {  q.push(front->_rchild); } } } 二叉树的非递归遍历：public: void PreOrder()//先序遍历打印树的各个节点 { cout<<"先序遍历:"; preorderR(_root); cout<<endl; } void InOrder()//中序遍历打印树的各个节点 { cout<<"中序遍历:"; inorderR(_root); cout<<endl; } void PostOrder()//后序遍历打印树的各个节点 { cout<<"后序遍历:"; postorderR(_root); cout<<endl; } void LevelOrder()//层序遍历打印树的各个节点 { cout<<"层序遍历:"; levelorder(_root); cout<<endl; }算法:void preorderR(Node* root)//先序遍历打印树的各个节点 { Node* cur = root; stack<Node*> s; while (!s.empty() || cur)//只要当前节点和栈不同时为空，就说明树没遍历完 { while(cur)//先序遍历，遇到树根节点直接访问数据并将其压栈 { cout<<cur->_value<<" "; s.push(cur); cur = cur->_lchild; } Node* top = s.top();//取出栈顶元素，到此说明此节点以及其左子树已经访问过了 s.pop(); cur = top->_rchild;//以子问题的方式去访问右子树 } cout<<endl; } void inorderR(Node* root)//中序遍历打印树的各个节点 { Node* cur = root; stack<Node*> s; while(!s.empty() || cur)//只要当前节点和栈不同时为空，就说明树没遍历完 { while(cur)//中序遍历，遇到树根节点直接将其压栈 { s.push(cur); cur = cur->_lchild; } Node* top = s.top();//取出栈顶元素，到此说明此节点的左子树已经访问过了 cout<<top->_value<<" ";//访问栈顶元素（即根节点） s.pop(); cur = top->_rchild;//以子问题的方式去访问右子树 } cout<<endl; } void postorderR(Node* root)//后序遍历打印树的各个节点 { Node* cur = root; Node* prev = NULL;//上一个访问过的数据 stack<Node*> s; while(!s.empty() || cur)//只要当前节点和栈不同时为空，就说明树没遍历完 { //后序遍历，遇到树根节点直接将其压栈 while(cur) { s.push(cur); cur = cur->_lchild; } Node* top = s.top();//取栈顶元素，但不一定能访问 //当节点右子树为空或已经访问过时对其直接进行访问 if (top->_rchild==NULL || top->_rchild==prev) { cout<<top->_value<<" "; prev = top;//将prev更新为已经访问的节点 s.pop(); } else//以子问题的方式去访问右子树 { cur = top->_rchild; } } cout<<endl; } void levelorder(Node* root)//层序遍历打印树的各个节点 { queue<Node*> q; if (root) { q.push(root);//将根节点插进队列 } while(!q.empty()) { Node* front = q.front(); q.pop(); cout<<front->_value<<" "; if (front->_lchild) { q.push(front->_lchild); } if (front->_rchild) { q.push(front->_rchild); } } }