二叉樹遍歷：

#include <iostream> #include <vector> #include <string> #include <sstream> #include<stack> #include<queue> using namespace std; struct BiTreeNode {char data;struct BiTreeNode *left_child;struct BiTreeNode *right_child; };int N = 0;void CreateBiTree(BiTreeNode* &T,char array[]){ //按先序輸入二叉樹中結點的值（一個字符），空格字符代表空樹， //構造二叉樹表表示二叉樹T。 char ch = array[N];N = N + 1; if(ch =='*') T=NULL;//其中getchar（）為逐個讀入標準庫函數 else{ T=new BiTreeNode;//產生新的子樹 T->data=ch;//由getchar（）逐個讀入來 CreateBiTree(T->left_child,array);//遞歸創建左子樹 CreateBiTree(T->right_child,array);//遞歸創建右子樹 } }//CreateTree void create_T(BiTreeNode* &T, char array[]) {char ch = array[N];N=N+1;if (ch == '*') {T = NULL;} else {T = new BiTreeNode;T->data = ch;create_T(T->left_child, array);create_T(T->right_child, array);} }// 遞歸 先序遍歷 void pre_order_traverse(BiTreeNode* &T) {// 先序遍歷if (T) {cout << T->data << " ";pre_order_traverse(T->left_child);pre_order_traverse(T->right_child);} }//先序遍歷 非遞歸； void pre_order_traverse_no_recurse(BiTreeNode* &T) {// 非遞歸先序遍歷二叉樹stack<BiTreeNode*> s;BiTreeNode *p = T;// 當棧非空或者p指針非空時調用循環while (p != nullptr || !s.empty()) {while ( p != nullptr) {cout << p->data << " ";s.push(p);p = p->left_child;}if (!s.empty()) {p = s.top();s.pop();p = p->right_child;}} }// 遞歸 中序遍歷 void in_order_traverse(BiTreeNode* &T) {// 中序遍歷if (T) {in_order_traverse(T->left_child);cout << T->data << " ";in_order_traverse(T->right_child);} }// 中序遍歷 非遞歸 void in_order_traverse_no_recurse(BiTreeNode* &T) {stack<BiTreeNode*> s;BiTreeNode *p = T;while (p != nullptr || !s.empty()) {while ( p != nullptr) {s.push(p);p = p->left_child;}if (!s.empty()) {p = s.top();cout << p->data << " ";s.pop();p = p->right_child;}} }// 遞歸 后序遍歷 void pos_order_traverse(BiTreeNode* &T) {// 中序遍歷if (T) {pos_order_traverse(T->left_child);pos_order_traverse(T->right_child);cout << T->data << " ";} }// 后序遍歷 非遞歸 void pos_order_traverse_no_recurse(BiTreeNode* &T) {stack<BiTreeNode*> s;BiTreeNode *p = T;BiTreeNode*pp = NULL;while (p != nullptr || !s.empty()) {while ( p != nullptr) {s.push(p);p = p->left_child;}if (!s.empty()) {p = s.top();if(p->right_child==NULL || p->right_child == pp){cout<<p->data<<" ";s.pop();pp = p;p = NULL;}else{p=p->right_child;}}} }void BFS(BiTreeNode* &T) {queue<BiTreeNode*>s;BiTreeNode *p = T;s.push(T);while(!s.empty()){p = s.front();s.pop();cout<<p->data<<" ";if(p->left_child){s.push(p->left_child);}if(p->right_child){s.push(p->right_child);}}}int main(){ char array[]= "abce***d**mn*k**o*jh***"; BiTreeNode*T; // create_T(T,array); CreateBiTree(T,array);//pre_order cout<<"pre_order_traverse"<<endl; pre_order_traverse(T); cout<<endl; cout<<"pre_order_traverse_no_recurse"<<endl; pre_order_traverse_no_recurse(T); cout<<endl;//in_order cout<<"in_order_traverse"<<endl; in_order_traverse(T); cout<<endl; cout<<"in_order_traverse_no_recurse"<<endl; in_order_traverse_no_recurse(T); cout<<endl;//pos_order cout<<"pos_order_traverse"<<endl; pos_order_traverse(T); cout<<endl; cout<<"pos_order_traverse_no_recurse"<<endl; pos_order_traverse_no_recurse(T); cout<<endl;//層次遍歷 BFS(T);return 0; }

?

轉載于:https://www.cnblogs.com/lovychen/p/11329117.html

總結

以上是生活随笔為你收集整理的二叉树，建树，前序，中序，后序，递归 非递归的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。