数据结构学习：什么是树？

概念

A tree is a nonlinear data structure, compared to arrays, linked lists, stacks and queues which are linear data structures. A tree can be empty with no nodes or a tree is a structure consisting of one node called the root and zero or one or more subtrees.

树是一个非线性的数据结构，相比较而言，数组，链表，栈和队列等等就是线性的数据结构。树可以为空，不包含任何节点，或者树可以称为由一个根节点和零个或者多个子树构成的。

判断是否是一颗树的条件：

• 有且只有一个根节点；
• 有若干个互不相交的子树；
• 根节点（root）没有父节点；
• 一个节点有且只有一个父节点（根节点除外）；
• 节点可以有多个子节点；
  

和树相关的一些术语，查阅了网上的一些资料，做了一下整理；

树的分类

按照个人的理解进行分类；

• 一般树：任意一个节点的子节点的个数都不受限制；
• 二叉树：任意一个节点的子节点的个数最多只有两个；
  • 一般二叉树
  • 满二叉树：在不增加树的层数的前提下，无法再多添加一个节点的二叉树
  • 完全二叉树：如果只是删除了满二叉树的最底层最右边的连续若干个节点，则这样形成的二叉树叫完全二叉树；
• 森林：n个互不相交的树的集合；

树的数据结构

typedef struct TreeNode *PtreNode; //前向声明

struct TreeNode {
    ElementType element;
    PtreNode	FirstChild;
    PtreNode	NextSibling;
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
 

总结

大部分的知识点主要参考了wiki上的解释，这里对于二叉树的分类都是点到即止，其实需要自己结合实践写代码实现一下，深入了解知识点和应用场景，以加深理解，如有错误的地方，希望指正。

参考

Tree_(data_structure)
树的遍历

文章来源: great.blog.csdn.net，作者：小麦大叔，版权归原作者所有，如需转载，请联系作者。

原文链接：great.blog.csdn.net/article/details/95769205