二叉树的简单创建 遍历等
题目:不分行从上到下打印二叉树
从上到下打印出二叉树的每个节点,同一层的节点按照从左到右的顺序打印,则一次打印出8,6,10,5,7,9,11
//
// NewTree.hpp
// 二叉树的基本
//
// Created by 张传奇 on 2018/8/7.
// Copyright © 2018年 张传奇. All rights reserved.
//
#ifndef NewTree_hpp
#define NewTree_hpp
#include <stdio.h>
#include <iostream>
using namespace std;
class NewNode {
public:
char data;
NewNode * lchild, * rchild;
};
class NewTree {
private:
NewNode * root;
int height;
void pre_Order(NewNode * t);
void in_Order(NewNode * t);
void post_Order(NewNode * t);
NewNode * create(string &s,int &pos);
public:
NewTree(){root = nullptr;height = 0;};
///按照前序遍历序列创建二叉树
void createBiTree(string s);
///前序遍历二叉树
void preOrder();
///中序遍历二叉树
void inOrder();
///后序遍历二叉树(递归方法)
void postOrder();
///后序遍历二叉树(使用栈的非递归方法)
void postOrder1();
///层序遍历二叉树
void levelOrder();
///求树的高度
int getHeight();
void get_Height(NewNode *t,int h);
};
#endif /* NewTree_hpp */
//
// NewTree.cpp
// 二叉树的基本
//
// Created by 张传奇 on 2018/8/7.
// Copyright © 2018年 张传奇. All rights reserved.
//
#include "NewTree.hpp"
#include <iostream>
#include "stack"
#include "queue"
using namespace std;
NewNode * NewTree::create(string &s, int &pos) {
++ pos;
NewNode * t;
if ((unsigned) pos >= s.size()) {
return nullptr;
}else
{
if (s[pos] == '#') {
t = nullptr;
}
else
{
t = new NewNode;
t->data = s[pos];
t->lchild = create(s, pos);
t->rchild = create(s, pos);
}
return t;
}
}
void NewTree::createBiTree(std::string s) {
int pos = -1;
root = create(s, pos);
}
void NewTree::preOrder() {
pre_Order(root);
cout<<endl;
}
void NewTree::pre_Order(NewNode *t){
if (t != nullptr) {
cout<<t->data<<" ";
pre_Order(t->lchild);
pre_Order(t->rchild);
}
}
void NewTree::inOrder() {
in_Order(root);
cout<<endl;
}
void NewTree::in_Order(NewNode *t) {
if (t != nullptr) {
in_Order(t->lchild);
cout<<t->data<<" ";
in_Order(t->rchild);
}
}
void NewTree::postOrder() {
post_Order(root);
cout<<endl;
}
void NewTree::post_Order(NewNode *t) {
if (t != nullptr) {
post_Order(t->lchild);
post_Order(t->rchild);
cout<<t->data<<" ";
}
}
void NewTree::postOrder1() {
NewNode *p,*r;
r = nullptr;
p = root;
stack<NewNode *> my_stack;
while (p != nullptr || !my_stack.empty()) {
if (p) {
//把左子树 便利完了
my_stack.push(p);
p = p->lchild;
}
else
{
//栈顶元素
p = my_stack.top();
if (p->rchild != nullptr && p->rchild != r) {
//先便利右子树,再便利右子树的左子树
p = p->rchild;
my_stack.push(p);
p = p->lchild;
}
else
{
// 左面便利完了,右面也便利完了,该根节点了
p = my_stack.top();
my_stack.pop();
cout<<p->data<<" ";
///更新最近遍历的节点
r = p;
///将遍历后的节点设为NULL,进行下一个节点的遍历
p = nullptr;
}
}
}
cout<<endl;
}
void NewTree::levelOrder() {
if (root == nullptr) {
return;
}
queue<NewNode *> my_queue;
my_queue.push(root);
while (!my_queue.empty()) {
NewNode * t;
t = my_queue.front();
my_queue.pop();
cout<<t->data<<" ";
if (t->lchild != nullptr) {
my_queue.push(t->lchild);
}
if (t->rchild != nullptr) {
my_queue.push(t->rchild);
}
}
cout<<endl;
}
int NewTree::getHeight() {
get_Height(root,0);
return height;
}
void NewTree::get_Height(NewNode *t, int h) {
if (t != nullptr) {
++ h;
if (h> height) {
height = h;
get_Height(t->lchild, h);
get_Height(t->rchild, h);
}
}
}
/**
前序遍历 非递归版本
*/
void BiTree::preOrder1() {
stack<BigNode *>my_stack;
my_stack.push(root);
BigNode * p;
while (!my_stack.empty()) {
p = my_stack.top();
my_stack.pop();
if (p != nullptr) {
cout<<p->data<<" ";
if (p->rchild != nullptr) {
my_stack.push(p->rchild);
}
if (p->lchild != nullptr) {
my_stack.push(p->lchild);
}
}
}
cout<<endl;
}
/**
中序遍历非递归版本
*/
void BiTree::inOrder1() {
stack<BigNode *> my_stack;
BigNode * p = root;
do {
while (p != nullptr) {
my_stack.push(p);
p = p->lchild;
}
p = my_stack.top();
my_stack.pop();
cout<<p->data<<" ";
if (p->rchild != nullptr) {
p = p->rchild;
}else
{
p = nullptr;
}
} while (p != nullptr || !my_stack.empty());
cout<<endl;
}
int main(int argc, const char * argv[]) {
// insert code here...
std::cout << "Hello, World!\n";
NewTree a;
string s;
s="ABD##E#F##C##";
a.createBiTree(s);
cout<<"前序遍历:"<<endl;
a.preOrder();
cout<<"中序遍历:"<<endl;
a.inOrder();
//
cout<<"后序遍历1:"<<endl;
a.postOrder();
cout<<"后序遍历2:"<<endl;
a.postOrder1();
cout<<"层序遍历:"<<endl;
a.levelOrder();
cout<<"树高:"<<endl;
cout<<a.getHeight()<<endl;
return 0;
}
网友评论