树和二叉树的概念与使用(Tree&Binary Tree)

        树是一种非线性的数据结构，它在表示机构的组织关系图等方面非常好用，树的示意图如图1所示。

 图1 - 树的示意图

一、表达方式 

        树主要由自身的数据域和其父节点构成，所以表示方法可以利用一个结构体数据表示，其方法如下。

const int maxn=10;//10个节点
struct node{
	int date,prarent;//分别是数据域和父节点
}tree[maxn];//10个节点的数组存储

         树的存储形式如下表所示

二、树转化成二叉树  

        因为数的分枝不确定，所以很多情况下其操作起来很不方便，而二叉树最多只有两个节点，即一个左子树和一个右子树，操作和表示起来都会简单很多。通常情况下，对树的处理都是先将其转化成二叉树。

        树转化成二叉树的方法：将一棵树的孩子节点放在二叉树的坐子树，将一棵树的兄弟节点放在右子树即可。

 图2 - 二叉树示意图

三、二叉树的表示

        由于二叉树最多只有左子树和右子树，所以存储时利用数组存储其左子树和右子树即可。

const int maxn=10;//10个节点
char data[maxn];
char lchild[maxn];//10个节点的左子树信息
char rchild[m];//10个节点的右子树信息
int btree;//根节点

         存储示例如下：

四、二叉树的访问

        利用递归程序对二叉树进行访问非常简单，根据访问顺序可分为：先序遍历、中序遍历和后序遍历。先序遍历访问顺序是根左右，中序遍历访问顺序是左根右，后序遍历顺序是左右根。

代码实现

先序遍历

void predorder(int root)
{
	if(root!=-1)
	{
		cout<" ";
		predorder(lchild[root]);
		predorder(rchild[root]);
	}
}

中序遍历

void midorder(int root)
{
	if(root!=-1)
	{
		midorder(lchild[root]);
		cout<" ";
		midorder(rchild[root]);
	}
}

后序遍历

void postorder(int root)
{
	if(root!=-1)
	{
		postorder(lchild[root]);
		postorder(rchild[root]);
		cout<" ";
	}
}

好啦，以上就是本章的内容啦，感谢阅读！