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

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

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

其他资讯