欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

数据结构 树的表示,存储结构与遍历

程序员文章站 2022-04-04 08:31:50
...

查找的概念:

根据某个关键字K,从集合R中找出与关键字K相同的记录

静态查找:集合中的记录是固定的

动态查找:集合中的记录是动态变化的


二分查找树:

判定树上每个结点需要的查找次数刚好为该节点所在的层数

找到所需元素的查找次数不会超过判定树的深度

N个节点的判定树深度为log2n+1


树的定义:

树是N个结点构成的有限集合

当N=0时称为空树,

非空树具有以下特点:

(1)树中有一个称为"ROOT"的特殊节点,用R表示

(2)子树:其余节点可以组成M棵子树

子树是不相交的, 除了根结点外, 每个结点有且仅有一个父结点

一棵N个节点的树 有N-1条边


树的基本用语:

(1)节点的度:节点的子树个数

(2)树的度:树的所有节点中最大的度数

(3)叶节点:度为0的节点

(4)父节点:一个节点上面的节点

(5)子节点:父节点下面的两个子节点

(6)路径长度:从一个节点到另一个节点所经历的节点数就是路径长度

(7)节点的层次:规定根结点层数为1 往下就是层次数加1

(8)树的深度:树中所有节点中的最大层次 就是树的深度


树的表示:

儿子-兄弟表示法

数据结构 树的表示,存储结构与遍历

第一个指针指向第一个儿子

第二个指针指向兄弟节点

实现结果如下

数据结构 树的表示,存储结构与遍历


二叉树的定义

数据结构 树的表示,存储结构与遍历

二叉树是一个有穷的结点集合,这个集合可以为空

若不为空:则它是由根结点和称为其左子树和右子树的两个不相交二叉树构成

完全二叉树:

有n个结点的二叉树,对树中节点按从上至下,从左到右顺序进行编号

编号为i节点与满二叉树中编号为i节点在二叉树中位置相同


二叉树的重要性质:

一个二叉树第I层的最大节点数:2^(I-1)个节点

深度为k的二叉树有最大的总结点数为: 2^k - 1 个节点

对任何非空二叉树T, 叶节点数为N0, 有两个子节点的节点数为N2

N0 = N2 + 1



二叉树结构:

class TreeNode {
	friend class BinaryTree;
private:
	ElementType data;
	TreeNode* LChild;    //指向左子节点
	TreeNode* RChild;    //指向右子节点

};


class BinaryTree {
private:
	TreeNode* root;
	
public:
	BinaryTree() {
		root = NULL;   
	}

	
	bool isEmpty();     //判断是否为空
	void TravelSal();   //遍历每个节点
	BinaryTree CreateBinaryTree();   //创建一棵二叉树


二叉树的遍历

先序遍历:

(1)访问根节点

(2)先序遍历左子树

(3)先序遍历右子树


遍历顺序如下所示:

数据结构 树的表示,存储结构与遍历

中序遍历过程:

(1)中序遍历左子树

(2)访问根结点

(3)中序遍历右子树

数据结构 树的表示,存储结构与遍历


后序遍历:

(1)后序遍历其左子树

(2)后序遍历其右子树

(3)遍历根结点

数据结构 树的表示,存储结构与遍历




代码实现:

//先序遍历
void BinaryTree::preOrderTravelsal(TreeNode* node) {
	if (node) {
		cout << node->data << " ";
		preOrderTravelsal(node->LChild);   //往左边遍历
		preOrderTravelsal(node->RChild);   //往右边遍历
	}
}

//中序遍历
void BinaryTree::midOrderTravelsal(TreeNode* node) {
	if (node) {

                midOrderTravelsal(node->LChild)
		cout << node->data << " ";
		midOrderTravelsal(node->RChild);   //往右边遍历
	}
}

//后序遍历
void BinaryTree::backOrderTravelsal(TreeNode* node) {
	if (node) {
		backOrderTravelsal(node->LChild);   //往左边遍历
		backOrderTravelsal(node->RChild);   //往右边遍历
		cout << node->data << " ";
	}
}