基础结构之树结构详解

树

一）什么是树（tree）

 

 树是n（n≥0）个节点的有限集。当n=0时，称为空树。在任意一个非空树中，有如下特点:

1. 有且仅有一个特定的称为根的节点。

2. 当n>1时，其余节点可分为m（m>0）个互不相交的有限集，每一个集合本身又是一个树，并称为根的子树。

 术语：根节点、子树、叶子节点、父节点、孩子节点、兄弟节点、树的高度

二）二叉树

二叉树（binary tree）是树的一种特殊形式。这种树的每个节点最多有2个孩子节点。注意，这里是最多有2个，也可能只有1个，或者没有孩子节点

 

二叉树的存储

1.链式存储

• 存储数据的data变量

• 指向左孩子的left指针

• 指向右孩子的right指针

2.数组存储

 

使用数组存储时，会按照层级顺序把二叉树的节点放到数组中对应的位置上。如果某一个节点的左孩子或右孩子空缺，则数组的相应位置也空出来，这样可以更方便地在数组中定位二叉树的孩子节点和父节点：

父节点下标 parent，那么左孩子下标为 leftChild = 2×parent + 1；右孩子下标为 rightChild = 2×parent + 2；

思考：什么二叉树适合用数组存储？

二叉树的遍历

线性结构（数组、链表）的遍历很简单，那么非线性结构树是如何遍历的呢？

主要分为：深度优先遍历（先序遍历、中序遍历、后序遍历）和 广度优先遍历（层序遍历）。

深度优先遍历

先序（根）遍历

先序遍历输出顺序是根节点、左子树、右子树。

public void preTraversal(TreeNode(parent,left,right,data) node) {
    if (null == node) {return;}
    // 输出节点值
    print(node.data);
    // 递归