二叉排序树的构造_二叉排序树唯一吗_二叉排序树的建立

#include <iostream>

#include <string>

#include <stack>

using namespace std;

struct node;

typedef node *pNode;

struct node {

char data;

pNode left, right;

};

string line;

string::iterator it;

// 前序扩展序列建立二叉树

void plant(pNode &root)

{

if (it == line.end())

return;

char data = *it++;

if (data == '/')

root = NULL;

else {

root = new node();

root->data = data;

plant(root->left);

plant(root->right);

}

}

// 先序遍历

void pre_order(pNode root)

{

stack<pNode> s;

while (root != NULL || !s.empty())

{

if (root != NULL) {

cout << root->data << " ";

s.push(root);

root = root->left;

} else {

root = s.top();

s.pop();

root = root->right;

}

}

}

// 中序遍历

void in_order(pNode root)

{

stack<pNode> s;

while (root != NULL || !s.empty())

{

if (root != NULL) {

s.push(root);

root = root->left;

} else {

root = s.top();

s.pop();

cout << root->data << " ";

root = root->right;

}

}

}

// 压栈的参数类型，包括局部变量和行号

struct stack_arg {

stack_arg(pNode _root, int _line)

: root(_root), line(_line) { }

pNode root;

int line;

};

// 后序遍历

void post_order(pNode root)

{

stack<stack_arg> s;

s.push(stack_arg(root, 1));

while (!s.empty())

{

switch (s.top().line) {

case 1:

if (s.top().root == NULL)

s.pop();

else

s.top().line = 2;

break;

case 2:

s.top().line = 3;

s.push(stack_arg(s.top().root->left, 1));

break;

case 3:

s.top().line = 4;

s.push(stack_arg(s.top().root->right, 1));

break;

case 4:

cout << s.top().root->data << " ";

s.pop();

本文来自电脑杂谈，转载请注明本文网址：
https://www.pc-fly.com/a/jisuanjixue/article-31416-1.html