二叉树的几种遍历方式-创新互联

#include
#include
#include
using namespace std;
template
class BinaryTreeNode {
 private:
     T element;
     BinaryTreeNode*leftChild;
     BinaryTreeNode*rightChild;
 public:
     BinaryTreeNode() {};
     BinaryTreeNode(const T& ele):element(ele),leftChild(NULL),rightChild(NULL) {};
     BinaryTreeNode(const T& ele,BinaryTreeNode*l,BinaryTreeNode*r);
     BinaryTreeNode* getLeftChild()const {
         return leftChild;
     };
     BinaryTreeNode* getRightChild()const {
         return rightChild;
     };
     void setLeftChild(BinaryTreeNode*l) {
         leftChild=l;
     };
     void setRightChild(BinaryTreeNode*r) {
         rightChild=r;
     };
     void createLeftChild();
     void createRightChild();
     T getvalue() const {
         return element;
     };
     void setvalue(const T& val) {
         element=val;
     };
     bool isLeaf()const;
};
template
class BinaryTree {

创新互联的客户来自各行各业，为了共同目标，我们在工作上密切配合，从创业型小企业到企事业单位，感谢他们对我们的要求，感谢他们从不同领域给我们带来的挑战，让我们激情的团队有机会用头脑与智慧不断的给客户带来惊喜。专业领域包括成都网站设计、成都网站建设、电商网站开发、微信营销、系统平台开发。

 public:
     BinaryTreeNode* root;
     BinaryTree();
     BinaryTree(BinaryTreeNode*a):root(a) {
     };
     bool isEmpty() const;
     BinaryTreeNode* getRoot() {
         return root;
     };
     BinaryTreeNode* getparent(BinaryTreeNode* current)const;
     BinaryTreeNode* getLeftsibling(BinaryTreeNode* current)const;
     void levelOrder(BinaryTreeNode*root);
     void preOrder(BinaryTreeNode*root);
     void PreOrderWithoutRecursion(BinaryTreeNode*root);
     void inOrder(BinaryTreeNode*root);
     void InOrderWithoutRecursion(BinaryTreeNode*root);
     void postorder(BinaryTreeNode*root);
     void PostOrderWithoutRecursion(BinaryTreeNode*root);
     void visit(BinaryTreeNode* t);
     void PreInBuild(T* a,T* b,int num);
     void Getroot(BinaryTreeNode*a);
     void maketree(BinaryTree* b1,BinaryTree* b2);
};
template
void BinaryTree::Getroot(BinaryTreeNode*a) {
 root=a;
}
template
void BinaryTree::maketree(BinaryTree* b1,BinaryTree* b2) {
 this->root->setLeftChild(b1->getRoot());
 this->root->setRightChild(b2->getRoot());
}
template
void BinaryTree::levelOrder(BinaryTreeNode*root) {
 queue*>nodeQueue;
 BinaryTreeNode*pointer=root;
 if(pointer)
     nodeQueue.push(pointer);
 while(!nodeQueue.empty() ) {
     pointer=nodeQueue.front();
     visit(pointer);
     nodeQueue.pop();
     if(pointer->getLeftChild())
         nodeQueue.push(pointer->getLeftChild());
     if(pointer->getRightChild())
         nodeQueue.push(pointer->getRightChild());
 }
}
template
void BinaryTree::preOrder(BinaryTreeNode*root) {
 if(root!=NULL) {
     visit(root);
     preOrder(root->getLeftChild());
     preOrder(root->getRightChild());
 }
}
template
void BinaryTree::PreOrderWithoutRecursion(BinaryTreeNode*root) {
 stack*>nodeStack;
 BinaryTreeNode*pointer=root;
 while(!nodeStack.empty()||pointer) {
     if(pointer) {
         visit(pointer);
         if(pointer->getRightChild()!=NULL)
             nodeStack.push(pointer->getRightChild());
         pointer=pointer->getLeftChild();
     } else {
         pointer=nodeStack.top();
         nodeStack.pop();
     }
 }
}
template
void BinaryTree::inOrder(BinaryTreeNode*root) {
 if(root!=NULL) {
     inOrder(root->getLeftChild());
     visit(root);
     inOrder(root->getRightChild());
 }
}
template
void BinaryTree::InOrderWithoutRecursion(BinaryTreeNode*root) {
 stack*>nodeStack;
 BinaryTreeNode*pointer = root;
 while(!nodeStack.empty() ||pointer) {
     if(pointer) {
         nodeStack.push(pointer);
         pointer = pointer->getLeftChild();
     } else {
         pointer= nodeStack.top();
         visit(pointer);
         pointer= pointer->getRightChild();
         nodeStack.pop();
     }
 }
}
template
void BinaryTree::postorder(BinaryTreeNode*root) {
 if(root!=NULL) {
     postorder(root->getLeftChild());
     postorder(root->getRightChild());
     visit(root);
 }
}
template
void BinaryTree::PostOrderWithoutRecursion(BinaryTreeNode*root) {
 stack* >nodeStack;
 BinaryTreeNode*pointer =root;
 BinaryTreeNode*pre =root;
 while(pointer) {
     for(; pointer->getLeftChild() != NULL; pointer = pointer->getLeftChild())
         nodeStack.push (pointer);
     while(pointer != NULL && (pointer->getRightChild() == NULL || pointer->getRightChild() == pre)) {
         visit(pointer);
         pre = pointer;
         if(nodeStack.empty())
             return;
         pointer = nodeStack.top();
         nodeStack.pop();
     }
     nodeStack.push(pointer);
     pointer = pointer->getRightChild();
 }
}
template
void BinaryTree::visit(BinaryTreeNode* t) {
 cout<getvalue()<<" ";
}
template
void BinaryTree::PreInBuild(T* pre,T* in,int num) {
}
int main() {
 BinaryTreeNode*x=new  BinaryTreeNode(1);
 BinaryTreeNode*s=new  BinaryTreeNode(4);
 BinaryTreeNode*t=new  BinaryTreeNode(5);
 BinaryTreeNode*r=new  BinaryTreeNode(2);
 r->setRightChild(t);
 r->setLeftChild(s);
 BinaryTreeNode*u=new  BinaryTreeNode(3);
 BinaryTreeNode*v=new  BinaryTreeNode(6);
 u->setRightChild(v);
 BinaryTree* b1=new BinaryTree(r);
 BinaryTree* b2=new BinaryTree(u);
 BinaryTree* b3=new BinaryTree(x);
 b3->maketree(b1,b2);
 cout<<"广度优先  :"; 
 b3->levelOrder(x);
 cout<  cout<<"前序递归  :";
 b3->preOrder(x);
 cout<  cout<<"前序非递归:";
 b3->PreOrderWithoutRecursion(x);
 cout<  cout<<"中序递归  :"; 
 b3->inOrder(x);
 cout<  cout<<"中序非递归:";
 b3->InOrderWithoutRecursion(x);
 cout<  cout<<"后序递归  :";
 b3->postorder(x);
 cout<  cout<<"后序非递归:";
 b3->PostOrderWithoutRecursion(x);
}

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧

名称栏目：二叉树的几种遍历方式-创新互联
文章位置：http://6mz.cn/article/gohpc.html