树(入门)

1.树的定义

树是一种非线性结构，用它来描述有分支和层次特性的数据集合。在树型结构中，二叉树是最常用的结构。具有分支个数确定、又可以为空，并有良好的递归特性，特别适宜于程序设计。

2.基本概念

树的概念

一棵树是由n（n>0）个元素组成的有限集合，其中：

（1）每个元素称为结点（node）

（2）有一个特定的结点，称为根结点或树根（root）

（3）除根节点外，其余节点能分成m（m>=0）个互不相交的有限集合 T(0)-T(m-1)。其中的每一个子集都是一个树，这些集合被称为这棵树的子树。

树的度

a.树的结点包含一个数据及若干指向子树的分支
b.结点拥有的子树数目称为结点的度–度为0的结点称为叶节点，度不为0的结点称为分支结点
c.树的度定义为所有结点中度的最大值

树的深度

3.树的存储

方法1：父亲表示法
记录每个节点的父亲节点，根节点没有父亲

方法2：树型双向链表

4.二叉树

二叉树是每个节点最多只有两个子树的数结构，两个子树称为左子树和右子树。

二叉树的存储

方法一：数组存储

用一维数组存储二叉树中的节点，数组的下标要能体现节点之间的逻辑关系。
如果某个节点的索引为 i，（假设根节点的索引为 0）则在它左子节点的索引会是 2i+1，以及右子节点会是 2i+2。

方法二：链表存储

在二叉树中，一个父节点最多只允许 2 个子节点，所以我们只需要一个存储数据和左右子节点的指针，这样的结构就是链式存储，也叫二叉链表。

二叉树的遍历 

例子1

例子2

 代码

#include <iostream>using namespace std;const int MAX_SIZE = 100;int tree[MAX_SIZE];
int leftChild[MAX_SIZE];
int rightChild[MAX_SIZE];
int n; // Number of nodesvoid buildTree() 
{cin >> n;for (int i = 0; i < n; i++) {cin >> tree[i];}for (int i = 0; i < n; i++) {leftChild[i] = 2 * i + 1;rightChild[i] = 2 * i + 2;}
}void xprint(int root) {if (root >= n || tree[root] == -1) return;cout << tree[root] << " "; xprint(leftChild[root]);xprint(rightChild[root]);
}void zprint(int root) {if (root >= n || tree[root] == -1) {return;}zprint(leftChild[root]);cout << tree[root] << " "; zprint(rightChild[root]);
}void hprint(int root) 
{if (root >= n || tree[root] == -1) return;hprint(leftChild[root]);hprint(rightChild[root]);cout << tree[root] << " "; 
}int main() 
{buildTree();xprint(0); cout << endl;zprint(0); cout << endl;hprint(0);return 0;
}