BiTreeNode.h
#pragma once
#include
using namespace std;
template<class T>
class BiTreeNode
{
private:
BiTreeNode<T>* leftChild;
BiTreeNode<T>* rightChild;
public:
T data;
BiTreeNode():leftChild(NULL),rightChild(NULL){}
BiTreeNode(T item, BiTreeNode<T>* left = NULL, BiTreeNode<T>* right = NULL ):data(item),leftChild(left),rightChild(right){}
~BiTreeNode(){}
BiTreeNode<T>*& Left() { return leftChild; }
BiTreeNode<T>*& Right() { return rightChild; }
};
BiTreeLib.h
#pragma once
#include"BiTreeNode.h"
//构造二叉树
template <class T>
BiTreeNode<T>* GetTreeNode(const T item, BiTreeNode<T>* left = NULL, BiTreeNode<T>* right = NULL)
{
BiTreeNode* p = new BiTreeNode(item, left, right);
return p;
}
//前序遍历
template <class T>
void PreOrder(BiTreeNode<T>* t, void Visit(T item))
{
if (t != NULL)
{
Visit(t->data);
PreOrder(t->Left(), Visit);
PreOrder(t->Right(), Visit);
}
}
//中序遍历
template <class T>
void InOrder(BiTreeNode<T>* t, void Visit(T item))
{
if (t != NULL)
{
InOrder(t->Left(), Visit);
Visit(t->data);
InOrder(t->Right(), Visit);
}
}
//后序遍历
template <class T>
void PostOrder(BiTreeNode<T>* t, void Visit(T item))
{
if (t != NULL)
{
PostOrder(t->Left(), Visit);
PostOrder(t->Right(), Visit);
Visit(t->data);
}
}
//后序遍历实现撤销
template <class T>
void Destroy(BiTreeNode<T>*& root)
{
if (root != NULL && root->Left != NULL)
{
Destroy(root->Left());
}
if (root != NULL && root->Right!= NULL)
{
Destroy(root->Right());
}
//cout << root->data << " ";
delete root;
}
//打印
template<class T>
void PrintBiTree(BiTreeNode<T>*& root, int level)
{
if (root != NULL)
{
PrintBiTree(root->Right(), level + 1);
if (level != 0)
{
for (int i = 0; i < 6 * (level - 1) ; i++)
{
cout << " ";
}
cout << "----";
}
PrintBiTree(root->Left(), level + 1);
}
}
//查找
template<class T>
BiTreeNode<T>* Search(BiTreeNode<T>* t, T x)
{
BiTreeNode* p;
if (t == NULL)
{
return NULL;
}
if (t->data == x)
{
return t;
}
if (t->Left() != NULL)
{
p = Search(t->Left(), x);
if (p != NULL)
{
return p;
}
}
if (t->Right() != NULL)
{
p = Search(t->Right(), x);
if (p != NULL)
{
return p;
}
}
return NULL;//查找失败
}
SeqStack.h
#pragma once
#include
using namespace std;
typedef BiTreeNode<char> DataType;
const int MaxStackSize = 100;
class SeqStack
{
private:
DataType *data[MaxStackSize];
int top;
public:
SeqStack();
~SeqStack();
void Push( DataType *item);
DataType *Pop();
DataType *GetTop()const;
bool NotEmpty()const;
};
SeqStack::SeqStack() { top = 0; };
SeqStack::~SeqStack() {}
//入栈
void SeqStack::Push( DataType *item)
{
if (top == MaxStackSize)
{
cout << "堆栈已满" << endl;
exit(0);
}
else
{
data[top] = item;
top++;
}
}
//出栈
DataType *SeqStack::Pop()
{
if (top == 0)
{
cout << "堆栈已空" << endl;
exit(0);
}
else
{
top--;
return data[top];
}
}
//取栈顶元素
DataType *SeqStack::GetTop()const
{
if (top == 0)
{
cout << "堆栈空" << endl;
exit(0);
}
return data[top - 1];
}
//判断是否非空
bool SeqStack::NotEmpty()const
{
if (top != 0)
{
return true;
}
else
{
return false;
}
}
#include"SeqStack.h"
void MakeCharBiTree(BiTreeNode<char>*& root)
{
BiTreeNode<char>*a,* b, * c, * d, * e, * f, * g, * null = NULL;
g = GetTreeNode('G', null, null);
d = GetTreeNode('D', null, g);
b = GetTreeNode('B', d, null);
e = GetTreeNode('E', null, null);
f = GetTreeNode('F', null, null);
c = GetTreeNode('C', e, f);
a = GetTreeNode('A', b, c);
}
void Print(char item)
{
cout << item << " ";
}
//非递归
void NotRecurPreOrder(DataType* t, void Visit(char item))
{
SeqStack stack;
DataType* p;
stack.Push(t);
while (stack.NotEmpty())
{
p = stack.Pop();
Visit(p->data);
if (p->Right() != NULL)
{
stack.Push(p->Right());
}
if (p->Left() != NULL)
{
stack.Push(p->Left());
}
}
}
int main()
{
BiTreeNode<char>* root1;
MakeCharBiTree(root1);
cout << "递归:";
PreOrder(root1, Print);
}
在前序遍历中引发访问权限冲突,请问是什么问题,怎么修改
MakeCharBiTree函数的参数root有啥用?函数代码跟它似乎没有关系啊