首页 > 程序开发 > 综合编程 > 其他综合 >

树的定义及存储以及二叉树的遍历方式实例讲解

2018-04-11

树的定义及存储以及二叉树的遍历方式实例讲解。

树的定义及存储以及二叉树的遍历方式实例讲解

/*
树的定义:
 由一个或多个(n >= 0)结点组成的有限集合T,有且仅有一个结点称为根(root),当 n>1时,其余的结点分为m(m > 0)个相互不相交的有限集合T1, T2, ..., Tm。每个集合本身又是棵树,被称作这个根的子树。
 树的结构特点:
 1.非线性结构,有一个直接前驱,但可能有多个直接后继(1:n)
 2.树的定义具有递归行,树中还有树。
 3.树可以为空,即结点个数为0.
 若干术语:
 根->即根结点
 叶子->即终端节点(没有后继)
 森林->指m棵不相交的树的集合
 有序树->结点各子树从左至右有序,不能互换(左为第一)
 无序树->结点各子树可互换位置。
 双亲->即上层的那个结点(直接前驱)parent
 孩子->即下层结点的子树(直接后继)child
 兄弟->同一双亲下的同层结点(孩子之间互称兄弟)sibling
 堂兄弟->即双亲位于同一层的结点(但并非同一双亲)cousin
 祖先->即从根到该结点所经分支的所有结点
 结点->即树的数据元素
 结点的度->结点挂接的子树数(有几个直接后继就是几度)。
 结点的层次->从根到该结点的层数(根结点算第一层)
 终端结点->即度为0 的结点, 即叶子
 分支结点->除树根以为的结点(也称为内部结点)
 树的度->所有结点度中的最大值(MAX(各结点的度))
 树的深度(或者高度)->指所有结点中最大的层数(Max(各结点的层次))
 三种表示树的方法:
 双亲表示法
 struct Node
 {
 int data;
 int parent;
 };
 左孩子右兄弟表示法:
 孩子表示法:
 struct ChildNode
 {
 int data;
 ChildNode*;
 };
*/
/*
二叉树的遍历:
遍历定义:
指按某条搜索路线遍访每个节点且不重复(又称周游)。
遍历用途:
它是树结构插入、删除、修改、查找和排序运算的前提,是二叉树一切运算的基础和核心。
遍历的方法:
牢记一种约定,对每个结点的查看都是"先左后右"。
限定先左后右,树的遍历有三种实现方案:
DLR		 LDR	  LRD
都要遍历到底在说
前(根)序遍历 中(根)序遍历 后(根)序遍历
DLR->先序遍历,即先根在左在右
LDR->中序遍历,即先左在根在右
LRD->后序遍历,即先左在右在根
*/
# include 
# include 
# include 


//二叉树结点
typedef struct BINARYNODE
{
	char ch;
	struct BINARYNODE* lchild;
	struct BINARYNODE* rchild;
}BinaryNode;
//递归前序遍历
void Recursion_1(BinaryNode* root)
{
	if(root == NULL)
	{
		return ;
	}
	//先访问根结点
	printf("%c", root->ch);
	//在遍历左子树
	Recursion_1(root->lchild);
	//在遍历右子树
	Recursion_1(root->rchild);
}
//递归中序遍历
void Recursion_2(BinaryNode* root)
{
	if(root == NULL)
	{
		return ;
	}
	//在遍历左子树
	Recursion_2(root->lchild);
	//先访问根结点
	printf("%c", root->ch);
	//在遍历右子树
	Recursion_2(root->rchild);
}
//递归后序遍历
void Recursion_3(BinaryNode* root)
{
	if(root == NULL)
	{
		return ;
	}
	//在遍历左子树
	Recursion_3(root->lchild);
	//在遍历右子树
	Recursion_3(root->rchild);
	//先访问根结点
	printf("%c", root->ch);


	
}


void CrestBinaryTree()
{
	//创建结点
	BinaryNode node1 = {'A', NULL, NULL};
	BinaryNode node2 = {'B', NULL, NULL};
	BinaryNode node3 = {'C', NULL, NULL};
	BinaryNode node4 = {'D', NULL, NULL};
	BinaryNode node5 = {'E', NULL, NULL};
	BinaryNode node6 = {'F', NULL, NULL};
	BinaryNode node7 = {'G', NULL, NULL};
	BinaryNode node8 = {'H', NULL, NULL};
	
	//建立结点关系
	node1.lchild = &node2;
	node1.rchild = &node6;
	node2.rchild = &node3;
	node3.lchild = &node4;
	node3.rchild = &node5;
	node6.rchild = &node7;
	node7.lchild = &node8;


	//递归遍历
	//前序遍历
	printf("前序遍历\n");
	Recursion_1(&node1);
	printf("\n");
	//中序遍历
	printf("中序遍历\n");
	Recursion_2(&node1);
	printf("\n");
	//后序遍历
	printf("后序遍历\n");
	Recursion_3(&node1);
	printf("\n");
}


int main(int argc, char *argv[])
{
	CrestBinaryTree();
	return 0;
}

\

相关文章
最新文章
热点推荐