5.[数据结构和算法分析笔记]树 Tree

简介:

1.树 Tree

定义

树是层次化的而非线性的。

树是由显示结点间关系的边(edge)相联而成的结点(node)集合。

如果树的每个结点都可以有任意数目子结点,则称为一般树。

如果树中每个结点的子结点数目不超过n,则称为n叉树。

如果树中每个结点只有两个子结点,则称为二叉树。

从根开始,沿着连接结点的边从一个结点到另一结点,构成一条路径(path),顺着路径可以到达树中任何一个结点。根和其他任何一个结点之间的路径是唯一的。

二叉树

如果二叉树中的每个叶子结点都恰好有两个子结点,则称为满二叉树。

如果二叉树中除最后一层外其余层都是满的,并且最后一层的叶子是从左向右填满,则称为完全二叉树。

如果n是一个满二叉树中的结点数,h是树的高度,则 

含有n个结点的完全二叉树或满二叉树的高度是log2(n+1)向上取整

树的Java接口

1
2
3
4
5
6
7
8
public  interface  TreeInterface<T> {
     public  T getRootData();
     public  int  getHieght();
     public  int  getNumberOfNodes();
     public  boolean  isEmpty();
     public  void  clear();
                                            
}

树的遍历方法接口

1
2
3
4
5
6
7
public  interface  TreeIteratorInterface<T> {
     public  Iterator<T> getPerorderIterator();
     public  Iterator<T> getPostorderIterator();
     public  Iterator<T> getInorderIterator();
     public  Iterator<T> getLevelOrderIterator();
                                         
}

二叉树的接口

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public  interface  BinaryTreeInterface<T>  extends  TreeInterface<T>,
         TreeIteratorInterface<T> {
     /**
      * 将已有的二叉树置为一棵新的单结点的二叉树
      * @param rootData
      */
     public  void  setTree(T rootData);
     /**
      * 将已有的二叉树置为一颗新的二叉树
      * @param rootData 新树的根的数据对象
      * @param leftTree 新树的左子树
      * @param rightTree 新树的右子树
      */
     public  void  setTree(T rootData, BinaryTreeInterface<T> leftTree,
             BinaryTreeInterface<T> rightTree);
}

二叉树的实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public  class  BuildBinaryTree {
     // 构建只含一个结点的树
     BinaryTreeInterface<String> dTree =  new  BinaryTree<String>();
     dTree.setTree( "D" );
     BinaryTreeInterface<String> fTree =  new  BinaryTree<String>();
     fTree.setTree( "F" );
     BinaryTreeInterface<String> gTree =  new  BinaryTree<String>();
     gTree.setTree( "G" );
     BinaryTreeInterface<String> hTree =  new  BinaryTree<String>();
     hTree.setTree( "H" );
     // 构建更大的子树
     BinaryTreeInterface<String> eTree =  new  BinaryTree<String>();
     eTree.setTree( "E" , fTree, gTree);
     BinaryTreeInterface<String> bTree =  new  BinaryTree<String>();
     bTree.setTree( "B" , dTree, eTree);
     BinaryTreeInterface<String> cTree =  new  BinaryTree<String>();
     cTree.setTree( "C" , emptyTree, hTree);
     BinaryTreeInterface<String> aTree =  new  BinaryTree<String>();
     aTree.setTree( "A" , bTree, cTree);
}

堆(heap)是其结点含有Comparable的对象并且每个结点含有的对象不小于(或不大于)其后代中的对象的完全二叉树。在最大堆中,结点中的对象大于等于其后代对象。在最小堆中,结点的对象小于等于其后代对象。

最大堆的接口

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public  interface  MaxHeapInterface<T  extends  Comparable<?  super  T>> {
     // 将一个新元素插入堆
     public  void  add(T newEntry);
     // 删除并返回堆中最大元素,如果堆为空则返回null
     public  T removeMax();
     // 返回堆中最大的元素,如果堆为空则返回null
     public  T getMax();
     // 检查堆是否为空
     public  boolean  isEmpty();
     // 获得堆的大小
     public  int  getSize();
     // 删除堆中所有元素
     public  void  clear();
}

优先队列

1
2
3
4
5
6
7
8
9
10
public  class  PriorityQueue<T  extends  Comparable<?  super  T>>  implements  PriorityQueueInterface<T>, Serializable {
     private  MaxHeapInterface<T> pq;
     public  PriorityQueue() {
         pq =  new  MaxHeap<T>();
     }
     @Override
     public  void  add(T newEntry) {
         pq.add(newEntry);
     }
}

2.二叉树的结点

二叉树结点的接口

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
public  interface  BinaryNodeInterface<T> {
     /**
      * 检索结点的数据部分
      * @return 结点的数据部分中的对象 */
     public  T getData();
     /**
      * 设置结点的数据部分
      * @param newDdata 是一个对象 */
     public  void  setData(T newData);
     /**
      * 检索结点的左(或右)子结点
      * @return 结点的左(或右)子结点 */
     public  BinaryNodeInterface<T> getLeftChild();
     public  BinaryNodeInterface<T> getRightChild();
     /**
      * 将结点的的左子结点设为指定结点
      * @param leftChild 将成为左子结点 */
     public  void  setLeftChild(BinaryNodeInterface<T> leftChild);
     /**
      * 将结点的右子结点设为指定结点
      * @param rightChild 将成为右子结点 */
     public  void  setRightChild(BinaryNodeInterface<T> rightChild);
     /**
      * 检查结点是否有左(或右)子结点
      * @return 如果有左(或右)子结点则返回true */
     public  boolean  hasLeftChild();
     public  boolean  hasRightChild();
     /**
      * 检查结点是不是叶子
      * @return 如果是叶子则返回true */
     public  boolean  isLeaf();
     /**
      * 计算以该结点为根的子树的结点数据
      * @return 返回以该结点为根的子树的结点数目 */
     public  int  getNumberOfNodes();
     /**
      * 计算以该结点为根的子树的高度
      * @return 返回以该结点为根的子树的高度 */
     public  int  getHeight();
     /**
      * 复制以该结点为根的子树
      * @return 返回以该结点为根的子树的根 */
     public  BinaryNodeInterface<T> copy();
}

BinaryNode的实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
public  class  BinaryNode<T>  implements  BinaryNodeInterface<T>, Serializable {
     private  T data;
     private  BinaryNode<T> left;
     private  BinaryNode<T> right;
     public  BinaryNode() {
         this ( null );
     }
     public  BinaryNode(T dataPortion) {
         this (dataPortion,  null null );
     }
     public  BinaryNode(T dataPortion, BinaryNode<T> leftChild,
             BinaryNode<T> rightChild) {
         data = dataPortion;
         left = leftChild;
         right = rightChild;
     }
     public  T getData() {
         return  data;
     }
     public  void  setData(T newData) {
         data = newData;
     }
     public  BinaryNodeInterface<T> getLeftChild() {
         return  left;
     }
     public  BinaryNodeInterface<T> getRightChild() {
         return  right;
     }
     public  void  setLeftChild(BinaryNodeInterface<T> leftChild) {
         left = (BinaryNode<T>) leftChild;
     }
     public  void  setRightChild(BinaryNodeInterface<T> rightChild) {
         right = (BinaryNode<T>) rightChild;
     }
     public  boolean  hasLeftChild() {
         return  left !=  null ;
     }
     public  boolean  hasRightChild() {
         return  right !=  null ;
     }
     public  boolean  isLeaf() {
         return  (left ==  null ) && (right ==  null );
     }
}










本文转自 LinkedKeeper 51CTO博客,原文链接:http://blog.51cto.com/sauron/1227342,如需转载请自行联系原作者
目录
相关文章
|
13天前
|
存储 机器学习/深度学习 算法
C 408—《数据结构》算法题基础篇—链表(下)
408考研——《数据结构》算法题基础篇之链表(下)。
76 29
|
14天前
|
存储 算法 C语言
C 408—《数据结构》算法题基础篇—链表(上)
408考研——《数据结构》算法题基础篇之链表(上)。
71 25
|
14天前
|
存储 人工智能 算法
C 408—《数据结构》算法题基础篇—数组(通俗易懂)
408考研——《数据结构》算法题基础篇之数组。(408算法题的入门)
58 23
|
1月前
|
存储 C++
【C++数据结构——树】哈夫曼树(头歌实践教学平台习题) 【合集】
【数据结构——树】哈夫曼树(头歌实践教学平台习题)【合集】目录 任务描述 相关知识 测试说明 我的通关代码: 测试结果:任务描述 本关任务:编写一个程序构建哈夫曼树和生成哈夫曼编码。 相关知识 为了完成本关任务,你需要掌握: 1.如何构建哈夫曼树, 2.如何生成哈夫曼编码。 测试说明 平台会对你编写的代码进行测试: 测试输入: 1192677541518462450242195190181174157138124123 (用户分别输入所列单词的频度) 预
59 14
【C++数据结构——树】哈夫曼树(头歌实践教学平台习题) 【合集】
|
1月前
|
Java C++
【C++数据结构——树】二叉树的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现二叉树的基本运算。​ 相关知识 创建二叉树 销毁二叉树 查找结点 求二叉树的高度 输出二叉树 //二叉树节点结构体定义 structTreeNode{ intval; TreeNode*left; TreeNode*right; TreeNode(intx):val(x),left(NULL),right(NULL){} }; 创建二叉树 //创建二叉树函数(简单示例,手动构建) TreeNode*create
48 12
|
1月前
|
C++
【C++数据结构——树】二叉树的性质(头歌实践教学平台习题)【合集】
本文档介绍了如何根据二叉树的括号表示串创建二叉树,并计算其结点个数、叶子结点个数、某结点的层次和二叉树的宽度。主要内容包括: 1. **定义二叉树节点结构体**:定义了包含节点值、左子节点指针和右子节点指针的结构体。 2. **实现构建二叉树的函数**:通过解析括号表示串,递归地构建二叉树的各个节点及其子树。 3. **使用示例**:展示了如何调用 `buildTree` 函数构建二叉树并进行简单验证。 4. **计算二叉树属性**: - 计算二叉树节点个数。 - 计算二叉树叶子节点个数。 - 计算某节点的层次。 - 计算二叉树的宽度。 最后,提供了测试说明及通关代
46 10
|
1月前
|
存储 算法 测试技术
【C++数据结构——树】二叉树的遍历算法(头歌教学实验平台习题) 【合集】
本任务旨在实现二叉树的遍历,包括先序、中序、后序和层次遍历。首先介绍了二叉树的基本概念与结构定义,并通过C++代码示例展示了如何定义二叉树节点及构建二叉树。接着详细讲解了四种遍历方法的递归实现逻辑,以及层次遍历中队列的应用。最后提供了测试用例和预期输出,确保代码正确性。通过这些内容,帮助读者理解并掌握二叉树遍历的核心思想与实现技巧。
49 2
|
1月前
|
算法 数据安全/隐私保护 计算机视觉
基于Retinex算法的图像去雾matlab仿真
本项目展示了基于Retinex算法的图像去雾技术。完整程序运行效果无水印,使用Matlab2022a开发。核心代码包含详细中文注释和操作步骤视频。Retinex理论由Edwin Land提出,旨在分离图像的光照和反射分量,增强图像对比度、颜色和细节,尤其在雾天条件下表现优异,有效解决图像去雾问题。
|
1月前
|
算法 数据可视化 安全
基于DWA优化算法的机器人路径规划matlab仿真
本项目基于DWA优化算法实现机器人路径规划的MATLAB仿真,适用于动态环境下的自主导航。使用MATLAB2022A版本运行,展示路径规划和预测结果。核心代码通过散点图和轨迹图可视化路径点及预测路径。DWA算法通过定义速度空间、采样候选动作并评估其优劣(目标方向性、障碍物距离、速度一致性),实时调整机器人运动参数,确保安全避障并接近目标。
145 68
|
1月前
|
算法 数据安全/隐私保护
室内障碍物射线追踪算法matlab模拟仿真
### 简介 本项目展示了室内障碍物射线追踪算法在无线通信中的应用。通过Matlab 2022a实现,包含完整程序运行效果(无水印),支持增加发射点和室内墙壁设置。核心代码配有详细中文注释及操作视频。该算法基于几何光学原理,模拟信号在复杂室内环境中的传播路径与强度,涵盖场景建模、射线发射、传播及接收点场强计算等步骤,为无线网络规划提供重要依据。