数据结构 二叉树 基本操作实例
该程序分为五个文件：
（1）BTree.h
//
// Created by Venus on 2016/10/24.
//
#ifndef BTREE_H
#define BTREE_H
#endif
class BTree {
public:
BTree* parent;
BTree* leftChild;
BTree* rightChild;
int data;
public:
BTree(int data, BTree* parent, BTree* leftChild, BTree* rightChild);
~BTree();
};
（2）BTree.cpp
//
// Created by Venus on 2016/10/24.
//
#include
#include "BTree.h"
using namespace std;
BTree::BTree(int data, BTree *parent, BTree *leftChild, BTree *rightChild) : data(data), parent(parent), leftChild(leftChild), rightChild(rightChild) {
}
BTree::~BTree() {
if (parent != NULL) {
delete parent;
}
if (leftChild != NULL) {
delete leftChild;
}
if (rightChild != NULL) {
delete rightChild;
}
}
（3）BinaryTree.h
//
// Created by Venus on 2016/10/24.
//
#ifndef BINARYTREE_H
#define BINARYTREE_H 1
#endif
#include
#include "BTree.h"
using namespace std;
class BinaryTree {
private:
BTree* root;
int count;
private:
BTree* findParentHasEmptyChild(BTree* root);
int getNodeLevel(BTree* bt, BTree* root, int level);
void preorderTraversalRec(BTree* root);
void inorderTraversalRec(BTree* root);
void postorderTraversalRec(BTree* root);
void levelorderTraversalRec(BTree* root);
int getTreeDeepth(BTree* root);
public:
BinaryTree();
~BinaryTree();
bool add(int data);
int size();
void preorderTraversal();
void inorderTraversal();
void postorderTraversal();
void levelorderTraversal();
void preorderTraversalRecursion();
void inorderTraversalRecursion();
void postorderTraversalRecursion();
void levelorderTraversalRecursion();
int treeDeepth();
};
（4）BinaryTree.cpp
//
// Created by Venus on 2016/10/24.
//
#include
#include
#include "BinaryTree.h"
using namespace std;
BinaryTree::BinaryTree() : root(NULL), count(0) {
}
BinaryTree::~BinaryTree() {
if (root != NULL) {
delete root;
}
}
int BinaryTree::size() {
return this->count;
}
BTree* BinaryTree::findParentHasEmptyChild(BTree *root) {
deque de;
while (root != NULL) {
if (de.empty()) {
de.push_back(root);
} else {
BTree* pre = de.front();
de.pop_front();
if (pre->leftChild != NULL && pre->rightChild != NULL) {
de.push_back(pre->leftChild);
de.push_back(pre->rightChild);
} else {
return pre;
}
}
}
return NULL;
}
bool BinaryTree::add(int data) {
BTree* bt = new BTree(data, NULL, NULL, NULL);
BTree* p = findParentHasEmptyChild(root);
if (p == NULL) {
root = bt;
} else {
bt->parent = p;
if (p->leftChild != NULL) {
p->rightChild = bt;
} else {
p->leftChild = bt;
}
}
count ++;
return true;
}
int BinaryTree::getNodeLevel(BTree *bt, BTree *root, int level) {
if (root == bt) {
return level;
} else {
int la = -1, lb = -1;
if (root->leftChild != NULL) {
la = getNodeLevel(bt, root->leftChild, level + 1);
}
if (root->rightChild != NULL) {
lb = getNodeLevel(bt, root->rightChild, level + 1);
}
if (la == -1 && lb == -1) {
return -1;
} else {
return la == -1 ? lb : la;
}
}
}
void BinaryTree::levelorderTraversal() {
if (root == NULL) {
cout << "The binary tree is empty!" << endl;
return;
}
deque de;
de.push_back(root);
int level = 0;
cout << "The " << level + 1 << " level:" << endl << endl;
while (!de.empty()) {
BTree* p = de.front();
de.pop_front();
int l = getNodeLevel(p, root, 0);
if (l == level) {
cout << " " << p->data;
} else {
cout << endl << endl;
level = l;
cout << "The " << level + 1 << " level:" << endl << endl;
cout << " " << p->data;
}
if (p->leftChild != NULL) {
de.push_back(p->leftChild);
}
if (p->rightChild != NULL) {
de.push_back(p->rightChild);
}
}
cout << endl;
}
void BinaryTree::preorderTraversal() {
if (root == NULL) {
cout << "The binary tree is empty!" << endl;
return;
}
deque de;
BTree* p = root;
cout << endl << "Preorder traversal as follow:" << endl;
cout << "------------------------------------------------------------------" << endl;
while (p != NULL) {
cout << " " << p->data;
if (p->leftChild != NULL) {
de.push_back(p);
p = p->leftChild;
} else {
if (p->rightChild == NULL && !de.empty()) {
do {
p = de.back()->rightChild;
de.pop_back();
} while (p == NULL && !de.empty());
if (p != NULL) {
continue;
}
}
p = p->rightChild;
}
}
cout << endl << "------------------------------------------------------------------" << endl;
}
void BinaryTree::inorderTraversal() {
if (root == NULL) {
cout << "The binary tree is empty!" << endl;
return;
}
deque de;
BTree* p = root;
cout << endl << "Inorder traversal as follow:" << endl;
cout << "------------------------------------------------------------------" << endl;
while(p != NULL) {
if (p->leftChild != NULL) {
de.push_back(p);
p = p->leftChild;
} else {
cout << " " << p->data;
if (p->rightChild == NULL && !de.empty()) {
do {
p = de.back();
de.pop_back();
cout << " " << p->data;
p = p->rightChild;
} while (p == NULL && !de.empty());
if (p != NULL) {
continue;
}
}
p = p->rightChild;
}
}
cout << endl << "------------------------------------------------------------------" << endl;
}
void BinaryTree::postorderTraversal() {
if (root == NULL) {
cout << "The binary tree is empty!" << endl;
return;
}
deque de;
deque detag;
BTree* p = root;
cout << endl << "Postorder traversal as follow:" << endl;
cout << "------------------------------------------------------------------" << endl;
while(p != NULL || !de.empty()) {
while (p != NULL) {
de.push_back(p);
detag.push_back(0);
p = p->leftChild;
}
p = de.back();
if (detag.back() == 0) {
detag.pop_back();
detag.push_back(1);
p = p->rightChild;
} else {
cout << " " << p->data;
de.pop_back();
detag.pop_back();
p = NULL;
}
}
cout << endl << "------------------------------------------------------------------" << endl;
}
void BinaryTree::preorderTraversalRec(BTree* root) {
cout << " " << root->data;
if (root->leftChild != NULL) {
preorderTraversalRec(root->leftChild);
}
if (root->rightChild != NULL) {
preorderTraversalRec(root->rightChild);
}
}
void BinaryTree::preorderTraversalRecursion() {
if (root == NULL) {
cout << "The binary tree is empty!" << endl;
return;
}
cout << endl << "Preorder traversal with recursion as follow:" << endl;
cout << "------------------------------------------------------------------" << endl;
preorderTraversalRec(root);
cout << endl << "------------------------------------------------------------------" << endl;
}
void BinaryTree::inorderTraversalRec(BTree* root) {
if (root->leftChild != NULL) {
preorderTraversalRec(root->leftChild);
}
cout << " " << root->data;
if (root->rightChild != NULL) {
preorderTraversalRec(root->rightChild);
}
}
void BinaryTree::inorderTraversalRecursion() {
if (root == NULL) {
cout << "The binary tree is empty!" << endl;
return;
}
cout << endl << "Inorder traversal with recursion as follow:" << endl;
cout << "------------------------------------------------------------------" << endl;
inorderTraversalRec(root);
cout << endl << "------------------------------------------------------------------" << endl;
}
void BinaryTree::postorderTraversalRec(BTree* root) {
if (root->leftChild != NULL) {
preorderTraversalRec(root->leftChild);
}
if (root->rightChild != NULL) {
preorderTraversalRec(root->rightChild);
}
cout << " " << root->data;
}
void BinaryTree::postorderTraversalRecursion() {
if (root == NULL) {
cout << "The binary tree is empty!" << endl;
return;
}
cout << endl << "Postorder traversal with recursion as follow:" << endl;
cout << "------------------------------------------------------------------" << endl;
postorderTraversalRec(root);
cout << endl << "------------------------------------------------------------------" << endl;
}
int BinaryTree::getTreeDeepth(BTree *root) {
if (root == NULL) {
return 0;
}
int leftDeepth, rightDeepth;
leftDeepth = getTreeDeepth(root->leftChild);
rightDeepth = getTreeDeepth(root->rightChild);
return leftDeepth > rightDeepth ? leftDeepth + 1 : rightDeepth + 1;
}
int BinaryTree::treeDeepth() {
return getTreeDeepth(root);
}
（5）main.cpp
#include
#include "BinaryTree.h"
using namespace std;
int main() {
BinaryTree* bt = new BinaryTree();
bt->add(10);
bt->add(20);
bt->add(30);
bt->add(40);
bt->add(50);
bt->add(60);
bt->add(70);
bt->add(80);
cout << "The binary tree size is :" << bt->size() << endl << endl;
bt->levelorderTraversal();
bt->preorderTraversal();
bt->inorderTraversal();
bt->postorderTraversal();
bt->preorderTraversalRecursion();
bt->inorderTraversalRecursion();
bt->postorderTraversalRecursion();
cout << "The tree deepth is :" << bt->treeDeepth() << endl;
}
运行结果：
