数据结构与算法:两分钟初识树

数据结构与算法:两分钟初识树

一:树的定义

树是一种数据结构,由n(n>1)个有限结点组成一个有层次关系的集合。形状像一颗倒立的树而得名。分为:无序树,有序树,二叉树,满二叉树,完全二叉树,平衡二叉树(AVL),二叉查找树(二叉搜索树、BST),霍夫曼树,红黑树,B-tree(B-树或者B树),B+树,B*树等。

节点结构体(C/C++)表示为:

1
2
3
4
5
6
typedef struct treeNode
{
    void *val;                  //数据项,任意类型
    struct treeNode *left;      //左子节点指针 
    struct treeNode *right;     //右子节点指针
}node;

节点类(Java)表示为:

1
2
3
4
5
public class TreeNode {
    private Object data;            //数据项
    private TreeNode leftChild;     //左子节点的引用
    private TreeNode rightChild;    //右子节点的引用
}

二:树的特点

1.根节点没有父节点。

2.每个非根节点只有一个父节点。

3.每个节点有零个或多个子节点。

三:相关术语

1.节点的度:节点含有子树的个数

2.叶子节点:节点的度为0。

3.子节点:一个节点含有的子树的根节点称为该节点的子节点。(这句有点绕口,举例:上图a,b,c是R的子节点)

4.父节点:含有子节点的节点,成为子节点的父节点。

5.兄弟节点:父节点相同的节点。

6.堂兄弟节点:父节点为兄弟节点的节点。

7.树的度:最大的节点的度称为树的度

8.树的高度或深度:树种节点的最大层次。

9.森林:n(n>=0)颗互不相交树的集合。

四:树的遍历

1.前序遍历

遍历顺序:访问根节点—>遍历左子树—>遍历右子树

2.中序遍历

遍历顺序:遍历左子树—>访问根节点—>遍历右子树

3.后序遍历

遍历顺序:遍历左子树—>遍历右子树—>访问根节点

#

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×