二叉树的五种遍历:
递归遍历:前序,中序,后序,非递归方法(栈);
层次遍历(bfs+队列);
#include <vector>
#include <iostream>
#include <stack>
#include <queue>
using namespace std;struct BitNode
{int data;BitNode *left, *right;BitNode(int x) :data(x), left(0), right(0){}
};
//二叉树的建立
void Create(BitNode *&root)
{int key;cin >> key;if (key == -1) //-1表示无结点root = NULL;else{root = new BitNode(key);Create(root->left);Create(root->right);}
}
//先序遍历二叉数
void PreOrderTraversal(BitNode *root)
{if (root){cout << root->data << " ";PreOrderTraversal(root->left);PreOrderTraversal(root->right);}
}
//中序遍历二叉树
void InOrderTraversal(BitNode *root)
{if (root){InOrderTraversal(root->left);cout << root->data << " ";InOrderTraversal(root->right);}
}
//后序遍历二叉树
void PosOrderTraversal(BitNode *root)
{if (root){PosOrderTraversal(root->left);PosOrderTraversal(root->right);cout << root->data << " ";}
}//深度优先搜索
//利用栈,现将右子树压栈再将左子树压栈
void DepthFirstSearch(BitNode *root)
{stack<BitNode*> nodeStack;nodeStack.push(root);while (!nodeStack.empty()){BitNode *node = nodeStack.top();cout << node->data << ' ';nodeStack.pop();if (node->right){nodeStack.push(node->right);}if (node->left){nodeStack.push(node->left);}}
}//广度优先搜索 ,队列实现
void BreadthFirstSearch(BitNode *root)
{queue<BitNode*> nodeQueue;nodeQueue.push(root);while (!nodeQueue.empty()){BitNode *node = nodeQueue.front();cout << node->data << ' ';nodeQueue.pop();if (node->left){nodeQueue.push(node->left);}if (node->right){nodeQueue.push(node->right);}}
}int main()
{BitNode *root = NULL;Create(root);//前序遍历PreOrderTraversal(root);//深度优先遍历cout << endl << "dfs" << endl;DepthFirstSearch(root);//广度优先搜索cout << endl << "bfs" << endl;BreadthFirstSearch(root);
}