线性表是一对一,但是树就不一样了,一对多的性质扑面而来,先看一下百度的说法吧, 树:它是由n(n≥1)个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。
就用这张图来描述树的特征:
是以B为结点的子树
下面我们来将结点分一下类:
结点的关系: 这块有点像我们的家庭关系,比较好理解 像上图A为B,C的双亲,B,C互为兄弟,对于#来说,D,B,A,都是它的祖先,反之A的子孙有B,D,#
其他相关概念,特定情况才会用到
引入了深度,可以说是有几层就有多少深度. 无序树:如果将树中结点的各子树看成从左到右都是没有次序,都可以随意互换,则称为无序树,反之为有序树
树真的太像人了,人可能暂时没有孩子但是一定有且只有一个父母,树也一样除了根结点外,其余每个结点,它不一定有孩子,但是一定有且只有一个双亲
/*
Project: Tree_parent(树-双亲表示法)
基本操作函数:
InitTree(Tree &T) 参数T,树根节点 作用:初始化树,先序递归创建
InsertNode(Tree &T, TElemType node) 插入树的结点 参数:树T,结点node 作用:在双亲数组中插入结点,增加树的结点值
InsertParent(Tree &T, TElemType node1, TElemType node2)//插入双亲数组的双亲域 参数:树T ,结点node1,结点node2
//作用:使双亲数组中,node2对应的双亲域为node1的下标
GetIndegree(Tree &T, TElemType node) //得到某结点入度 参数:树T,结点node 结点不存在返回-1
GetOutdegree(Tree &T, TElemType node) //得到某结点出度 参数:树T,结点node 结点不存在返回-1
PreOrder(Tree T) 参数:树T,根节点下标 作用:先序遍历树
PostOrder(Tree T) 参数:树T,根节点下标 作用:后序遍历树
LevelOrder(Tree T)参数:树T 作用:层序遍历树
功能实现函数:
CreateTree(Tree &T) 参数T,树根节点 作用:创建树,调用InsertNode,InsertParent
Traverse(Tree T) 参数T,树根节点 作用:PreOrder InOrder PostOrder LevelOrder遍历树
*/
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<string>
#include<stack>
#include<queue>
#include<algorithm>
#include<iostream>
#define TElemType char
#define Max 100
using namespace std;
//树的结点数据结构
typedef struct TNode
{
TElemType data;//数据域
int parent; //双亲
}TNode;
//树的数据结构
typedef struct Tree
{
TNode parent[Max];
int NodeNum;
}Tree;
//********************************基本操作函数********************************//
//初始化树函数 参数:树T 作用:规定数据域为#,则为空,双亲为-1,则为空
void InitTree(Tree &T)
{
for (int i=0;i<Max;i++)
{
T.parent[i].data = '#';
T.parent[i].parent = -1;
}
T.NodeNum = 0;
}
//插入树的结点 参数:树T,结点node 作用:在双亲数组中插入结点,增加树的结点值
bool InsertNode(Tree &T, TElemType node)
{
if (node != '#')
{
T.parent[T.NodeNum++].data = node;//插入到双亲数组中
return true;
}
return false;
}
//插入双亲数组的双亲域 参数:树T ,结点node1,结点node2
//作用:使双亲数组中,node2对应的双亲域为node1的下标
bool InsertParent(Tree &T, TElemType node1, TElemType node2)
{
int place1, place2;
place1 = -1;place2 = -1;
for (int i=0;i<T.NodeNum;i++)//查找两点是否存在
{
if (node1 == T.parent[i].data)place1 = i;
if (node2 == T.parent[i].data)place2 = i;
}
if (place1 != -1 && place2 != -1)//两点均存在
{
T.parent[place2].parent = place1;
return true;
}
return false;
}
//得到某结点入度 参数:树T,结点node 结点不存在返回-1
int GetIndegree(Tree &T, TElemType node)
{
int place = -1;
for (int i = 0;i<T.NodeNum;i++)
{
if (T.parent[i].data == node)place = i;
}
if (place!=-1)//结点存在
{
if(T.parent[place].parent!=-1)return 1;//双亲只能有一个
else return 0; //根节点没有双亲,即没有入度
}
return -1;
}
//得到某结点出度 参数:树T,结点node 结点不存在返回-1
int GetOutdegree(Tree &T, TElemType node)
{
int place = -1;
int outdegree = 0;
for (int i = 0;i<T.NodeNum;i++)
{
if (T.parent[i].data == node)place = i;
}
if (place != -1)
{
for (int i = 0;i < T.NodeNum;i++)
{
if (T.parent[i].parent == place)outdegree++;
}
return outdegree;
}
return -1;
}
//先序遍历 参数:树T,根节点下标
void PreOrder(Tree T,int i)
{
if (T.NodeNum != 0)
{
cout << T.parent[i].data << " ";
for(int j=0;j<T.NodeNum;j++)
{
if(T.parent[j].parent==i)
PreOrder(T,j);//按左右先序遍历子树
}
}
}
//后序遍历 参数:树T,根节点下标
void PostOrder(Tree T,int i)
{
if (T.NodeNum != 0)
{
for (int j = 0;j<T.NodeNum;j++)
{
if (T.parent[j].parent == i)
PostOrder(T, j);//按左右先序遍历子树
}
cout << T.parent[i].data << " ";
}
}
//层序遍历 参数:树T
void LevelOrder(Tree T)
{
queue<TNode> q;//借助队列
if (T.NodeNum!=0)
{
TNode temp;//暂存要出队的结点
q.push(T.parent[0]);//根结点入队
while (!q.empty())//队列非空
{
temp = q.front();
q.pop();
cout<<temp.data<<" ";
for (int j = 0;j<T.NodeNum;j++)
{
if (T.parent[T.parent[j].parent].data == temp.data)//当前结点的父节点的数据域与弹出的相同
//因为temp没有保存下标,只能按这种方式比较,默认结点名称不同
q.push(T.parent[j]);//队列先进先出,先入左孩子
}
}
}
}
//**********************************功能实现函数*****************************//
//创建树,调用InsertNode,InsertParent
void CreateTree(Tree &T)
{
int nodenum = 0;
int parent;
TElemType node,node1,node2;
printf("请输入树的结点个数:");
cin >> nodenum;
parent = nodenum - 1;
printf("请输入树的结点名称(空格隔开):");
while (nodenum--)
{
cin >> node;
InsertNode(T,node);
}
printf("请输入树的结点间的双亲关系(一对为一双亲关系,A B表示A为B的双亲):\n");
while (parent--)
{
cin >> node1>>node2;
InsertParent(T,node1,node2);
}
printf("\n");
}
//入度
void Indegree(Tree &T)
{
TElemType node;
int indegree;
printf("请输入结点名称:\n");
cin >> node;
indegree = GetIndegree(T, node);
if (-1 != indegree)
cout << "该结点入度为:" << indegree << endl;
else
cout << "结点不存在。" << endl;
}
//出度
void Outdegree(Tree &T)
{
TElemType node;
int outdegree;
printf("请输入结点名称:\n");
cin >> node;
outdegree = GetOutdegree(T, node);
if (-1 != outdegree)
cout << "该结点出度为:" << outdegree << endl;
else
cout << "结点不存在。" << endl;
}
//遍历功能函数 调用PreOrder InOrder PostOrder LevelOrder
void Traverse(Tree T)
{
int choice;
while (1)
{
printf("********1.先序遍历 2.后序遍历*********\n");
printf("********3.层次遍历 4.返回上一单元*********\n");
printf("请输入菜单序号:\n");
scanf("%d", &choice);
if (4 == choice) break;
switch (choice)
{
case 1: {printf("树先序遍历序列:");PreOrder(T,0);printf("\n");}break;
case 2: {printf("树后序遍历序列:");PostOrder(T,0);printf("\n");}break;
case 3: {printf("树层序遍历序列:");LevelOrder(T);printf("\n");}break;
default:printf("输入错误!!!\n");break;
}
}
}
//菜单
void menu()
{
printf("********1.创建 2.某点入度*********\n");
printf("********3.某点出度 4.遍历*************\n");
printf("********5.退出\n");
}
//主函数
int main()
{
Tree T;
int choice = 0;
InitTree(T);
while (1)
{
menu();
printf("请输入菜单序号:\n");
scanf("%d", &choice);
if (5 == choice) break;
switch (choice)
{
case 1:CreateTree(T);break;
case 2:Indegree(T);break;
case 3:Outdegree(T);break;
case 4:Traverse(T);break;
default:printf("输入错误!!!\n");break;
}
}
return 0;
}
所用图
顾名思义,就是每个结点有多个指针域,其中每个指针指向一棵子树的根结点,我们也把这种方法叫做多重链表表式法,有点像线性表中的链式表示法 那么这样的话,我这里就写伪代码了
//指针域的个数就等于树的度,其中树的度又等于树各个结点度的最大值
struct ChildNode
{
int data;
ChildNode*;
}
ChildNode *D;//d为最大结点
d.ChildNode;
不难看出这样的话,如果各个树度之间的差距不大,还可以,但是如果各个树度之间的差距很大,那么很浪费空间,原因是许多的结点域都是空的
这个可以说是学二叉树的基础,有的兄弟可能要说了,为什么不是兄弟表示法?还要带上我的孩子一起? 因为可能存在下面这种情况,只有了兄弟,孩子没有办法往下延申了,那么如何孩子和兄弟一起开呢? 是这样的,任意一棵树,它的结点的第一个孩子如果存在就是唯一的,它的右兄弟如果存在也是唯一的,记得不是堂兄弟昂,是亲兄弟,下面我们看图
观察后,我们可以发现每个结点最多有俩个孩子,也就是一个简单的二叉树,这也可以说是,孩子兄弟表示法最大的好处
struct Node
{
int data;
*firstchild,*ringtsib;
}
Node *Tree;