#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://cdkjz.cn/article/gohpc.html
