图片说明
上代码：

 Stack.h:

#pragma once

//栈定义
template
class Stack
{
public:
const int maxSize = 50;
Stack();
virtual void Push(const T& x) = 0;
virtual bool Pop(T& x) = 0;
virtual bool getTop(T& x)const = 0;
virtual bool IsEmpty()const = 0;
virtual bool IsFull()const = 0;
virtual int getSize()const = 0;

};

 LinkedStack.h:

#pragma once

#include "Stack.h"
#include "Nodes.h"
#include
using namespace std;

template
class LinkedStack:public Stack //链式栈
{
public:
LinkedStack() :top(NULL){}
~LinkedStack(){ MakeEmpty(); }
void Push(const T& x);
bool Pop(T& x);
bool GetTop(T& x)const;
bool IsEmpty()const{ return (top == NULL) ? true : false; }
int GetSize()const;
void MakeEmpty();
friend ostream& operator<<(ostream& os, LinkedStack& s);
private:
LinkNode *top;
};

template
void LinkedStack::MakeEmpty()
{
LinkNode *p;
while (top)
{
p = top;
top = top->link;
delete p;
}
}

template
void LinkedStack::Push(const T& x)
{
top = new LinkNode(x, top);
assert(top);
}

template
bool LinkedStack::Pop(T& x)
{
if (IsEmpty())
return false;
LinkNode *p = top;
x = p->data;
top = top->link;
delete p;
}

template
bool LinkedStack::GetTop(T& x)const
{
if (IsEmpty())
return false;
x = top->data;
return true;
}

template
int LinkedStack::GetSize()const
{
int count = 0;
LinkNode *p = top;
while (p)
{
p = p->link;
count++;
}
return count;
}

template
ostream& operator<<(ostream& os, LinkedStack& s)
{
os << "栈中元素个数：" << s.GetSize() << endl;
int i = 1;
LinkNode *p = s.top;
while (p)
{
os << i++ << ":" << p->data << endl;
p = p->link;
}
return os;
}

template
bool LinkedStack::IsFull()const
{
return false; //链表栈空间无限制，不会满
}

 BinaryTree.h:

#include
#include "LinkedStack.h"
using namespace std;

template
struct BinTreeNode //二叉树节点类定义
{
T data;
BinaryTreeNode *leftChild,*rightChild;
BinaryTreeNode() :leftChild(NULL), rightChild(NULL){}
BinaryTreeNode(T x, BinaryTreeNode *l = NULL, BinaryTreeNode *r = NULL) :data(x), leftChild(l), rightChild(r){}
};

template
class BinaryTree //二叉树类定义
{
public:
BinaryTree() :root(NULL){}
BinaryTree(T value) : refValue(value), root(NULL){}
BinaryTree(BinaryTree& s);
~BinaryTree(){ destroy(root); }
bool IsEmpty(){ return (root == NULL) ? true : false; }
BinTreeNode *GetParent(BinTreeNode *current)
{
return (root == NULL || root == current) ? NULL : GetParent(root, current);
}
BinTreeNode *GetLeftChild(BinTreeNode *current)
{
return (current == NULL) ? NULL : current->leftChild;
}
BinTreeNode *GetRightChild(BinTreeNode *current)
{
return (current == NULL) ? NULL : current->rightChild;
}
int GetHeight(){ return Height(root); } //返回树高度
int GetSize(){ return Size(root); } //返回节点数
BinTreeNode *GetRoot()const{ return root; }
void PreOrder(void(*visit)(BinTreeNode *p)) //前序遍历
{
PreOrder(root, visit);
}
void InOrder(void(*visit)(BinTreeNode *p)) //中序遍历
{
InOrder(root, visit);
}
void PostOrder(void(*visit)(BinTreeNode *p)) //后序遍历
{
PostOrder(root, visit);
}
void LevelOrder(void(*visit)(BinTreeNode *p)); //层次序遍历
int Insert(const T& item);
BinTreeNode *Find(T& item)const;

protected:
BinTreeNode *root; //根指针
T refValue; //数据输入停止标识
void CreateBinTree(istream& in, BinTreeNode *& subTree);
bool Insert(BinTreeNode * & subTree, const T& x);
void Destroy(BinTreeNode * & subTree);
bool Find(BinTreeNode * subTree, const T& x)const;
BinTreeNode * Copy(BinTreeNode * orignode);
int GetHeight(BinTreeNode * subTree);
int GetSize(BinTreeNode * subTree);
BinTreeNode * GetParent(BinTreeNode * subTree, BinTreeNode * current);
BinTreeNode * Find(BinTreeNode * subTree, const T& x)const;
void Traverse(BinTreeNode * subTree, ostream& out); //前序遍历输出
void PreOrder(BinTreeNode& subTree, void(*visit)(BinTreeNode * p)); //前序遍历
void InOrder(BinTreeNode& subTree, void(*visit)(BinTreeNode * p)); //中序遍历
void PostOrder(BinTreeNode& subTree, void(*visit)(BinTreeNode * p)); //后序遍历
friend istream& operator >> (istream& in, BinaryTree& Tree); //重载操作：输入
friend ostream& operator << (ostream& out, BinaryTree& Tree); //重载操作：输出
};

template
void BinaryTree::Destroy(BinaryTree * subTree)
{
if (subTree != NULL) //递归终止条件
{
Destroy(subTree->leftChild);
Destroy(subTree->rightChild);
delete subTree; //必须先删除左右子女树再删除自己，若先删除自己，则leftChlid,rightChild不存在，无法访问子女树
}
}

template
BinTreeNode * BinaryTree::GetParent(BinTreeNode * subTree, BinTreeNode * current)
{
//私有函数，从subTree节点开始，搜索节点current的父节点
if (subTree == NULL)
return NULL;
if (subTree->leftChild == current || subTree->rightChild == current)
{
return subTree;
}
BinTreeNode * p;
if (p = GetParent(subTree->leftChild, current) != NULL) //递归在左子树中搜索
return p;

else
return GetParent(subTree->rightChild, current); //递归在右子树中搜索
}

template
void BinaryTree::Traverse(BinTreeNode * subTree, ostream& out)
{
//私有函数，前序输出subTree二叉树的所有数据
if (subTree != NULL)
{
out << subTree->data << '';
Traverse(subTree->leftChild,out);
Traverse(subTree->rightChild,out);
}
}

template
ostream& operator << (ostream& out, BinaryTree& Tree)
{
//重载操作，输出一颗二叉树Tree
out << "二叉树的前序遍历\n";
Tree.Traverse(Tree.root, out);
out << endl;
return out;
}

template
istream& operator >> (istream& in, BinaryTree& Tree)
{
//重载操作，输入并建立一颗二叉树Tree
CreateBinTree(in, Tree.root);
return in;
}

void CreateBinTree(istream& in, BinTreeNode * &BT)
{
//从输入流in输入二叉树的广义表表示建立对应点的二叉链表
LinkedStack *> s;
BT = NULL;
BinTreeNode *p, *t;
int k; //用k作为处理左右子树的标记
char ch;
in >> ch;
while (ch != '#') //书上是 ch!=RefValue
{
switch (ch)
{
case '(':
s.Push(p);
k = 1;
break;
case ')':
s.Pop(t);
break;
case ',':
k = 2;
break;
default:
p = new BinTreeNode(ch);
if (BT == NULL)
BT = p;
else if (k==1)
{
s.GetTop(t);
t->leftChild = p;
}
else
{
s.GetTop(t);
t->rightChild = p;
}
}
in >> ch;
}
}

 Main.cpp:

#include
using namespace std;
#include "BinaryTree.h"

void main()
{
BinTreeNode * node=NULL;
//BinaryTree * p = new BinaryTree('#');
CreateBinTree(cin, node);

system("pause");

}

这代码怎么格式不对啊……
需要的话我可以发源码

zhxue_11

C++在链表递归的过程中使用临时节点并且置NULL，那么二叉树需要吗？

1条回答

为你推荐