二叉樹的層序遍歷

void printTree(BinaryTree* arr[])
{queue<BinaryTree*> rel; rel.push(arr[0]);while (!rel.empty()){BinaryTree* front = rel.front();printf("%d\n", front->vec);rel.pop(); if (front->left != nullptr) //判斷最前面的左節點是否為空，不是則放入隊列rel.push(front->left);if (front->right != nullptr)//判斷最前面的右節點是否為空，不是則放入隊列rel.push(front->right);}
}

前序遍歷

遞歸版本

void PreOrder(bintree t){if(t){printf("%c ",t->data);PreOrder(t->lchild);PreOrder(t->rchild);}

非遞歸版本

void preOrder2(BinTree *root)     //非遞歸前序遍歷 
{stack<BinTree*> s;BinTree *p=root;while(p!=NULL||!s.empty()){while(p!=NULL){cout<<p->data<<" ";s.push(p);p=p->lchild;}if(!s.empty()){p=s.top();s.pop();p=p->rchild;}}
}

中序遍歷

遞歸版本

void inOrder1(BinTree *root)      //遞歸中序遍歷
{if(root!=NULL){inOrder1(root->lchild);cout<<root->data<<" ";inOrder1(root->rchild);}
}

非遞歸版本

void inOrder2(BinTree *root)      //非遞歸中序遍歷
{stack<BinTree*> s;BinTree *p=root;while(p!=NULL||!s.empty()){while(p!=NULL){s.push(p);p=p->lchild;}if(!s.empty()){p=s.top();cout<<p->data<<" ";s.pop();p=p->rchild;}}    
}

后序遍歷

遞歸版本

void postOrder1(BinTree *root)    //遞歸后序遍歷
{if(root!=NULL){postOrder1(root->lchild);postOrder1(root->rchild);cout<<root->data<<" ";}    
}

非遞歸版本

void postOrder2(BinTree *root)    //非遞歸后序遍歷
{stack<BTNode*> s;BinTree *p=root;BTNode *temp;while(p!=NULL||!s.empty()){while(p!=NULL)              //沿左子樹一直往下搜索，直至出現沒有左子樹的結點 {BTNode *btn=(BTNode *)malloc(sizeof(BTNode));btn->btnode=p;btn->isFirst=true;s.push(btn);p=p->lchild;}if(!s.empty()){temp=s.top();s.pop();if(temp->isFirst==true)     //表示是第一次出現在棧頂{temp->isFirst=false;s.push(temp);p=temp->btnode->rchild;    }else                        //第二次出現在棧頂 {cout<<temp->btnode->data<<" ";p=NULL;}}}    
}