目录
一、双亲表示法：
#include<iostream>
using namespace std;
#define MAX_TREE_SIZE 100
template <typename DataType>
struct PNode
{
DataType data;
int parent;
};
//树的存储结构：双亲表示法
template <typename DataType>
class MyTree
{
public:
MyTree();
~MyTree();
PNode<DataType>* AddTreeNode(DataType data,int parent);
void Insert(DataType data,int parent);
void GetDepth();
void PrintTree();
private:
PNode<DataType> *arr[MAX_TREE_SIZE];
int num;//记录节点个数
int depth;//记录深度
};
template <typename DataType>
MyTree<DataType>::MyTree()
{
num=0,depth=0;
for(int i=0;i<MAX_TREE_SIZE;i++)
{
arr[i]=nullptr;
}
}
template <typename DataType>
MyTree<DataType>::~MyTree()
{
for (int i = 0; i < num; i++)
{
delete arr[i];
}
}
template <typename DataType>//创建节点
PNode<DataType>* MyTree<DataType>::AddTreeNode(DataType data,int parent)
{
PNode<DataType> *s=new PNode<DataType>;
s->data=data;
s->parent=parent;
return s;
}
template <typename DataType>
void MyTree<DataType>::Insert(DataType data,int parent)
{
arr[num]=AddTreeNode(data,parent);
num++;
}
template <typename DataType>
void MyTree<DataType>::GetDepth()
{
int dep;
for (int i = 0; i <num; i++)
{
dep = 0;
for (int j = i; j >= 0; j = arr[j]->parent)
{
dep++;
}
if (dep >depth)
depth = dep;
}
}
template <typename DataType>
void MyTree<DataType>::PrintTree()
{
// int num1=num;//结点个数控制输出完所有结点
// int i=0;//顺序打印
// int count=1;//记录外层循环次数
// while(num1--)
// {
// printf("第%d层：",count);
// cout<<arr[i]->data <<","<<arr[i]->parent<<" " ;
// while(arr[i+1]!=nullptr&&arr[i]->parent==arr[i+1]->parent)//同父母兄弟同行打印输出
// {
// i++;
// cout<<arr[i]->data <<","<<arr[i]->parent<<" " ;
// num1--;
// }
// i++;
// count++;
// cout<<endl;
// }
GetDepth();
cout<<"树的深度为：" <<depth<<endl;
//第二种打印法
for(int i=0;i<num;i++)
{
printf("第%d个结点：",i+1);
cout<<arr[i]->data <<" "<<"父亲结点为："<<arr[i]->parent<<endl;
}
}
int main()
{
MyTree<char> tree1;
tree1.Insert('A',-1) ;
tree1.Insert('B',0) ;
tree1.Insert('C',0) ;
tree1.Insert('D',1) ;
tree1.Insert('E',1) ;
tree1.Insert('F',2) ;
tree1.PrintTree();
return 0;
}伪代码说明：
伪代码：
//创建模板类，在私有变量中设置结构体数组，结点个数和深度
//构造函数初始化结构体数组
//析构函数释放结构体数组
//AddTreeNode函数创建结点，将结点地址返回给Insert函数
//Insert函数接收结点地址并插入至结构体数组，结点数num++
//GetDepth()函数计算树的深度，原理是遍历结点，得出每个结点深度，将最大深度记作树的深度
//最后打印树 二、孩子表示法：
#include<iostream>
using namespace std;
#define MAX_TREE_SIZE 10
//树的存储结构：孩子表示法
struct CTNode//孩子结点
{
int child;//孩子结点下标
CTNode*next;
};
template <typename DataType>
struct CBNode//表头结点
{
DataType data;
CTNode*firstchild;//指向孩子链表的头指针
};
template <typename DataType>
class MyTree
{
public:
MyTree();
~MyTree();
CBNode<DataType>* AddTreeNode(DataType data);
void Insert(DataType data,int n);
void PrintTree();
void PreOrderTree(int root);
void BackOrderTree(int root) ;
void LevelOrderTree();
private:
CBNode<DataType> *arr[MAX_TREE_SIZE];
int num;//记录节点个数
int depth;//记录深度
int c;//记录孩子位置
};
template <typename DataType>
MyTree<DataType>::MyTree()
{
num=0,depth=1,c=1;
for(int i=0;i<MAX_TREE_SIZE;i++)
{
arr[i]=nullptr;
}
}
template <typename DataType>
MyTree<DataType>::~MyTree()
{
for (int i = 0; i < num; i++)
{
while(arr[i]->firstchild!=NULL)
{
CTNode*s =arr[i]->firstchild->next;
delete arr[i]->firstchild;
arr[i]->firstchild=s;
}
delete arr[i];
}
}
template <typename DataType>
CBNode<DataType>* MyTree<DataType>::AddTreeNode(DataType data)
{
CBNode<DataType>*s=new CBNode<DataType>;
s->data=data;
s->firstchild=NULL;
return s;
}
template <typename DataType>
void MyTree<DataType>::Insert(DataType data,int n)
{
arr[num]=AddTreeNode(data);
if(n!=0)
{
CTNode*ptr=arr[num]->firstchild;//移动指针
CTNode*newnode=new CTNode;
newnode->child=c;
c++;
newnode->next=NULL;//创建孩子结点
ptr=arr[num]->firstchild=newnode;//链接到表头结点上
n--;
while(n--)
{
CTNode*newnode=new CTNode;
newnode->child=c;
c++;
newnode->next=NULL;//创建孩子结点
ptr->next=newnode;
ptr=ptr->next;
}
depth++;
}
num++;
}
template <typename DataType>
void MyTree<DataType>::PrintTree()
{
cout<<"树的深度为："<<depth<<endl;
// int i=1;//下一层结点数
// int index=0; //记录下标位置
// for(int m=0;m<num;m++)
// {
// for(int n=0;n<i;n++)//打印层结点数
// {
// cout<<arr[index]->data<<" ";
// index++;
// }
// cout<<endl;
//
//
// int c=m;
// int count=0;
// int b=i;//上一层结点数
// for(int n=0;n<i;n++)//计算下一层结点数
// {
// CTNode*ptr=arr[c]->firstchild;
// c++;
// while(ptr!=NULL)
// {
// count++;//记录一个结点有几个孩子
// ptr=ptr->next;
// }
//
// }
// i+=count;
// i=i-b;;//把上一层循环的次数即上一层结点数减去，使i为下一层结点数
// }
//第二种打印法
for(int i=0;i<num;i++)
{
printf("第%d个结点：",i+1);
cout<<arr[i]->data <<" "<<"孩子结点为：";
CTNode*ptr=arr[i]->firstchild;
if(ptr==NULL)
cout<<"NULL";
while(ptr!=NULL)
{
cout<<arr[ptr->child]->data<<" ";
ptr=ptr->next;
}
cout<<endl;
}
}
template <typename DataType>
void MyTree<DataType>::PreOrderTree(int root) //递归算法，以Tree[root]为根的子树
{
if(root>=0 && root<num)
{
//存在该结点
cout<<arr[root]->data <<" ";
}
CTNode* p=arr[root]->firstchild; //Tree[root]->firstChild
while(p!=NULL)
{
//依次前序遍历root结点的每一棵子树
PreOrderTree(p->child);
p=p->next;
}
}
template <typename DataType>
void MyTree<DataType>::BackOrderTree(int root)
{
CTNode* p=arr[root]->firstchild;
while(p!=NULL)
{
BackOrderTree(p->child);
if(p->child>=0 && p->child<num)
{
//存在该结点
cout<<arr[p->child]->data <<" ";
}
p=p->next;
}
if(root==0)
{
cout<<arr[root]->data <<" ";
}
}
template <typename DataType>
void MyTree<DataType>::LevelOrderTree()
{
cout<<arr[0]->data <<" ";
for(int i=0;i<num;i++)
{
CTNode*ptr=arr[i]->firstchild;
while(ptr!=NULL)
{
cout<<arr[ptr->child]->data<<" ";
ptr=ptr->next;
}
}
}
int main()
{
MyTree<char> Tree2;
Tree2.Insert('A',2) ;
Tree2.Insert('B',3) ;
Tree2.Insert('C',0) ;
Tree2.Insert('D',1) ;
Tree2.Insert('E',0) ;
Tree2.Insert('F',0) ;
Tree2.Insert('G',0) ;
//Tree2.PreOrderTree(0);
//Tree2.BackOrderTree(0);
//Tree2.LevelOrderTree();
Tree2.PrintTree() ;
return 0;
}
伪代码说明：
伪代码：
//定义树的最大节点数 MAX_TREE_SIZE 为 10
//
//定义孩子节点结构 CTNode:
// 包含整数 child，表示孩子节点的下标
// 包含指向下一个 CTNode 的指针 next
//
//定义表头节点结构 CBNode<DataType>:
// 包含数据类型 DataType 的数据
// 包含指向孩子链表头指针的 CTNode* firstchild
//
//定义模板类 MyTree<DataType>:
// 包含以下成员变量:
// CBNode<DataType>* 数组 arr[MAX_TREE_SIZE]，用于存储树的节点
// 整数 num，记录当前节点数
// 整数 depth，记录树的深度
// 整数 c，用于记录孩子节点的位置（下标）
//
// 包含以下成员函数:
// 构造函数 MyTree()
// 初始化 num, depth, c，并将 arr 数组的所有元素设置为 nullptr
//
// 析构函数 ~MyTree()
// 遍历 arr 数组，释放每个节点及其孩子链表所占用的内存
//
// CBNode<DataType>* AddTreeNode(DataType data)
// 创建一个新的 CBNode<DataType> 节点，设置其数据为 data，firstchild 设置为 nullptr，并返回该节点
//
// void Insert(DataType data, int n)
// 在树中添加一个新节点，数据为 data，n 表示该节点的父节点下标（若为 0 则表示该节点为根节点）
// 创建新节点并添加到 arr 数组中
// 若 n 不为 0，则创建孩子链表，并将新节点链接到其父节点的 firstchild 链表上
// 增加 num 和 depth（若添加了新层级的节点）
//
// void PrintTree()
// 打印树的结构，包括每个节点的数据和孩子节点
// 遍历 arr 数组，对于每个节点，打印其数据，然后遍历其孩子链表，打印孩子节点的数据
//
// void PreOrderTree(int root)
// 递归地前序遍历以 root 为根的子树
// 若 root 节点存在，则先打印 root 节点，然后遍历其孩子链表，对每个孩子节点递归调用 PreOrderTree
//
// void BackOrderTree(int root)
// 递归地后序遍历以 root 为根的子树
// 遍历 root 节点的孩子链表，对每个孩子节点递归调用 BackOrderTree，然后打印 root 节点
// 注意：这里的后序遍历实现有误，因为打印 root 节点的逻辑应该放在递归调用之后，并且应该在确认孩子节点存在时才递归
//
// void LevelOrderTree()
// 按层级顺序打印树的所有节点
// 首先打印根节点，然后遍历 arr 数组，对每个节点的孩子链表进行遍历，打印孩子节点的数据
//
// int main()
// 调用函数调试