数据结构 树的表示,存储结构与遍历
查找的概念:
根据某个关键字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 << " ";
}
}
下一篇: c++ 已知到三点的距离,求当前点坐标