|
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
typedef struct treeNode_t
{
? ? int value;
? ? struct treeNode_t *plchild;
? ? struct treeNode_t *prchild;
? ??
? ? treeNode_t(int v, struct treeNode_t *pl, struct treeNode_t *pr)
? ? {
? ? ? ? value = v;
? ? ? ? plchild = pl;
? ? ? ? prchild = pr;
? ? }
}treeNode;
//递归遍历
void levelOrder1(treeNode *root, int pos, vector<treeNode *> &v)
{
? ? if (nullptr == root)
? ? {
? ? ? ? return;
? ? }
? ??
? ? if (v.capacity() <= pos)
? ? {
? ? ? ? v.resize(pos + 1, 0);
? ? }
? ? v[pos] = root;
? ??
? ? if (root->plchild)
? ? {
? ? ? ? levelOrder1(root->plchild, 2 * pos, v);
? ? }
? ??
? ? if (root->prchild)
? ? {
? ? ? ? levelOrder1(root->prchild, 2 * pos + 1, v);
? ? }
}
//迭代遍历
void levelOrder2(treeNode *root)
{
? ? if (nullptr == root)
? ? {
? ? ? ? return;
? ? }
? ??
? ? queue<treeNode *> ?q;
? ? q.push(root);
? ??
? ? while(!q.empty())
? ? {
? ? ? ? treeNode *tmp = q.front();
? ? ? ? q.pop();
? ? ? ? cout << tmp->value << endl;
? ? ? ? if (tmp->plchild)
? ? ? ? {
? ? ? ? ? ? q.push(tmp->plchild);
? ? ? ? }
? ? ? ? if (tmp->prchild)
? ? ? ? {
? ? ? ? ? ? q.push(tmp->prchild);
? ? ? ? }
? ? }
? ??
? ??
}
int main() {
? ? treeNode *node11 = new treeNode(11, nullptr, nullptr);
? ? treeNode *node10 = new treeNode(10, nullptr, nullptr);
? ? treeNode *node9 = new treeNode(9, nullptr, nullptr);
? ? treeNode *node8 = new treeNode(8, nullptr, nullptr);
? ? treeNode *node7 = new treeNode(7, nullptr, node11);
? ? treeNode *node6 = new treeNode(6, node9, node10);
? ? treeNode *node5 = new treeNode(5, node8, nullptr);
? ? treeNode *node4 = new treeNode(4, nullptr, nullptr);
? ? treeNode *node3 = new treeNode(3, node6, node7);
? ? treeNode *node2 = new treeNode(2, node4, node5);
? ? treeNode *node1 = new treeNode(1, node2, node3);
? ??
? ??
? ? vector<treeNode *> v;
? ? levelOrder1(node1, 1, v);
? ? cout << "levelOrder1:" << endl;
? ? for (int i = 0; i < v.capacity(); i++)
? ? {
? ? ? ? if (v[i])
? ? ? ? {
? ? ? ? ? ? cout << v[i]->value << endl;
? ? ? ? }
? ? }
? ??
? ? cout << "levelOrder2:" << endl;
? ? levelOrder2(node1);
? ??
? ??
? ? return 0;
}
?
|