对于普通树实现的细节包括
1 树结点的结构体
2 初始化及删除树结点（关注内存泄露）
3 递归先序遍历
4 通过关键值的查询操作，返回关键值的结点
5 凹入表实现
6 广义表实现
7 非递归先序遍历，利用栈作为辅助的数据结构
#include <iostream>
#include <crtdbg.h>
#include <cstring>
#include <assert.h>
using namespace std; typedef int DataType;
struct TreeNode
{
TreeNode()
{
sibling = NULL;
child = NULL;
}
DataType data;
TreeNode * sibling; //右兄弟结点
TreeNode * child; //左子结点
};
typedef TreeNode *DataStack; // 存储类型为 TreeNode*
//普通树
class Tree
{
private:
TreeNode *root;
Tree(const Tree &) {}//防止拷贝构造 与 赋值
Tree & operator=(const Tree &) { return *this; }
public:
Tree(const DataType &data);
~Tree();
const TreeNode * GetRoot()const { return root;}
TreeNode * GetRoot() { return root;}
void Init(const DataType &data);
void Destroy(TreeNode * p);//删除根结点
void DestroySub(TreeNode * p);//删除子结点;
TreeNode * InsertChild(TreeNode *p, DataType data);
TreeNode * InsertSibling(TreeNode *p, DataType data);
void Print(const TreeNode * p); //先序遍历
TreeNode * Find(TreeNode * p, DataType data);//寻找data返回并返回结点
void Print2(); //非递归先序遍历
};
//辅助类栈
class Stack
{
private:
struct Node
{
DataStack data;
Node *next;
};
Node * head;
void Init()
{
head = NULL;
}
void Destroy()
{
for (Node* p = head; p != NULL;)
{
Node *pTemp = p->next;
delete p ;
p = pTemp;
}
head = NULL;
}
public:
Stack()
{
Init();
}
~Stack()
{
Destroy();
}
void Push(DataStack data)
{
Node *p = new Node;
p->data = data;
p->next = head;
head = p;
}
DataStack Pop()
{
if (head == NULL)
{
return NULL;
}
Node *p = head;
DataStack temp = p->data;
head = head->next;
delete p;
p = NULL;
return temp;
}
int Getlenth()
{
int n = ;
for (Node *p = head; p != NULL; p = p->next)
{
++n;
}
return n;
}
DataStack Getop()
{
if (head == NULL)
{
return NULL;
}
return head->data;
}
bool Empty()
{
return (head == NULL);
}
};
//普通树方法实现
Tree::Tree(const DataType &data)
{
Init(data);
}
Tree::~Tree ()
{
Destroy(root);
}
void Tree::Init(const DataType &data)
{
root = new TreeNode;
root->child = NULL;
root->sibling = NULL;
root->data = data;
}
void Tree::Destroy(TreeNode * p)
{
if (p == NULL)
{
return;
}
Destroy(p->sibling);
Destroy(p->child);
delete p;
p = NULL;
}
void Tree::DestroySub(TreeNode * p)
{
if (p->child)
{
Destroy(p->child);
p->child = NULL;
}
}
TreeNode * Tree::InsertChild(TreeNode * p, DataType data)
{
if (p->child)
{
return p->child; //已有子结点
}
TreeNode *pNew = new TreeNode;
pNew->data = data;
p->child = pNew;
return pNew;
}
TreeNode * Tree::InsertSibling(TreeNode * p, DataType data)
{
if (p->sibling)
{
return p->sibling;//已有兄弟结点
}
TreeNode *pNew = new TreeNode;
pNew->data = data;
p->sibling = pNew;
return pNew;
}
//先序遍历
void Tree::Print(const TreeNode * p)
{
if(p==NULL)
{
return;
}
cout << p->data << endl;
Print(p->child);
Print(p->sibling);
}
//寻找data并返回结点
TreeNode * Tree::Find(TreeNode * p, DataType data)
{
if(p == NULL)
return NULL;
if (p->data == data)
{
return p;
}
TreeNode *pFind = Find(p->child, data);
if (pFind != NULL)
{
return pFind;
} return Find(p->sibling, data);
}
//非递归先序遍历
void Tree::Print2()
{
TreeNode *p = GetRoot();
if (p == NULL)
{
return;
}
Stack stack; while( (p != NULL) || (!stack.Empty()) )
{
if (p != NULL)
{
cout << p->data << endl;
stack.Push(p);
p = p->child;
}
else
{
p = stack.Pop();
p = p->sibling;
}
}
}
void AoRuBiao(const TreeNode *p, int depth)
{
if (p == NULL)
{
return;
}
for (int i=; i<depth; ++i)
{
cout << " ";
}
cout << p->data;
for (int i=; i<-depth; ++i)
{
cout << " - ";
}
cout << endl;
AoRuBiao(p->child, depth+);
AoRuBiao(p->sibling, depth);
}
void GuangYiBiao(const TreeNode *p)
{
if (p == NULL)
{
return;
}
cout << p->data;
if (p->child)
{
cout << "(";
}
GuangYiBiao(p->child);
if (p->child)
{
cout << ")";
}
if (p->sibling)
{
cout << ",";
}
GuangYiBiao(p->sibling);
} void main()
{
_CrtSetDbgFlag(_CRTDBG_ALLOC_MEM_DF | _CRTDBG_LEAK_CHECK_DF); Tree tree(); //Stack s;
//s.Push(tree.GetRoot());
//cout << s.Getop()->data; TreeNode * p11 = tree.InsertChild(tree.GetRoot(), );
TreeNode * p12 = tree.InsertSibling(p11,);
TreeNode * p13 = tree.InsertSibling(p12,); TreeNode * p111 = tree.InsertChild(p11, );
TreeNode * p112 = tree.InsertSibling(p111,); TreeNode * p121 = tree.InsertChild(p12, );
TreeNode * p122 = tree.InsertSibling(p121,); tree.Print(tree.GetRoot());
//tree.DestroySub(p12);
//tree.Print(tree.GetRoot());
cout << "\n\nSearch p12" << endl;
TreeNode * temp = tree.Find(tree.GetRoot(),);
if (temp != NULL)
{
cout << temp->child->data <<endl;
cout << temp->sibling->data << endl;
} cout << "\n\nAoRuBiao " << endl;
AoRuBiao(tree.GetRoot(),); cout << "\nGuangYiBiao" << endl;
GuangYiBiao(tree.GetRoot()); cout << "\n\n非递归遍历" << endl;
tree.Print2(); system("pause");
}
（转载请注明作者和出处^_* Seven++ http://www.cnblogs.com/sevenPP/ ）