BinaryTree_.h_.cpp

.h文件

#pragma once

#include <iostream>

using namespace std;

class BinaryTree;

class BinTreeNode {

friend BinaryTree;

private:

BinTreeNode * leftChild, *rightChild;

char data;

public:

BinTreeNode() {

leftChild = NULL;

rightChild = NULL;

}

BinTreeNode(char x,BinTreeNode *left=NULL,BinTreeNode *right=NULL) :data(x),leftChild(left),rightChild(right) {}

};

class BinaryTree {

private:

char endtag;

BinTreeNode *root;

void createBinTree(BinTreeNode *subTree);

int height(BinTreeNode *subTree);

int size(BinTreeNode *subTree);

void preOrder(BinTreeNode *subTree);

void inOrder(BinTreeNode *subTree);

void postOrder(BinTreeNode *subTree);

void destroy(BinTreeNode *&subTree);//*&why???

BinTreeNode *parent(BinTreeNode *subTree, BinTreeNode *current);

public:

BinaryTree(char value) {

endtag = value;

root = NULL;

}

BinaryTree() { destroy(root); }

void creaeBinTree() {

createBinTree(root);

}

bool isEmpty() { return (root == NULL) ? true : false; }

int height() { height(root); }

int size() { size(root); }

void preOrder(){ preOrder(root); }

void inOrder() { inOrder(root); }

void postOrder() { postOrder(root); }

BinTreeNode *parent(BinTreeNode *current) {

return (root == NULL || root == current) ? NULL : parent(root, current);

}

BinTreeNode *leftChild(BinTreeNode *current) { return (current != NULL) ? current->leftChild : NULL; }

BinTreeNode *rightChild(BinTreeNode *current) { return (current != NULL) ? current->rightChild : NULL; }

};

.cpp文件

#include "stdafx.h"

#include "標頭.h"

void BinaryTree::createBinTree(BinTreeNode * subTree)

{

char item;

cin >> item;

if (item != endtag) {

subTree = new BinTreeNode(item);

createBinTree(subTree->leftChild);

createBinTree(subTree->rightChild);

}

subTree = NULL;

}

int BinaryTree::height(BinTreeNode * subTree)

{

if (subTree == NULL) return 0;

else if (height(subTree->leftChild) > height(subTree->rightChild)) {

return height(subTree->leftChild);

}

else { return height(subTree->rightChild); }

}

int BinaryTree::size(BinTreeNode * subTree)

{

if (subTree == NULL) { return 0; }

else { return 1 + size(subTree->leftChild) + size(subTree->rightChild); }

}

void BinaryTree::preOrder(BinTreeNode * subTree)

{

if (subTree != NULL) {

cout << subTree->data;

preOrder(subTree->leftChild);

preOrder(subTree->rightChild);

}

}

void BinaryTree::inOrder(BinTreeNode * subTree)

{

if (subTree != NULL) {

inOrder(subTree->leftChild);

cout << subTree->data;

inOrder(subTree->rightChild);

}

}

void BinaryTree::postOrder(BinTreeNode * subTree)

{

postOrder(subTree->leftChild);

postOrder(subTree->rightChild);

cout << subTree->data;

}

void BinaryTree::destroy(BinTreeNode *& subTree)

{

if (subTree != NULL) {

destroy(subTree->leftChild);

destroy(subTree->rightChild);

delete subTree;

}

}

BinTreeNode * BinaryTree::parent(BinTreeNode * subTree, BinTreeNode * current)

{

if (subTree != NULL) { return NULL; }

if (subTree->leftChild == current || subTree->rightChild == current) {

return subTree;

}

BinTreeNode *p = parent(subTree->leftChild, current);

if (p != NULL) { return p; }

else

return (parent(subTree->rightChild, current));

}