数据结构——树

树

树的概念：

图1 图2

图1中是我们现实生活中的树，根在下，叶子和分支在上，而在计算机中的树是图二中的样子，也就是现实生活中的树倒过来的样子，根在上，叶子和分子在下；而具体是什么样子呢如图3：

图3

树的的性质：

1.一颗树有且只有一个根节点；

2.根节点没有前驱结点，也就是没有父节点，而其他结点有且只有一个父节点；

3.结点代表集合，边代表关系，那么根节点代表这颗树的全集，其他结点都代表这颗树的子集，并且被根节点所包含；

4.一个结点有几条边，也就是几个子孩子，那他的度就为几，比如图3中的1结点度为3，3结点度为0；

5.一颗树的节点数量等于所有结点的度+1，+1是因为根节点没有父节点，+1就是加的根结点；

6.树的深度，从上往下看，比如7结点的深度为3，3结点的深度为2；

7.树的高度，从下往上看，比如7结点的高度为1，3结点的高度为2；

二叉树：

这文章主要讲二叉树，因为在数据结构中用的树，最多的也是二叉树，可以通过二叉树的代码，来转换成普通树的代码也是一样的；

结构定义

物理结构

二叉树是树的一种树形结构，它的特点就是，一个结点最多只有两个子孩子结点(下文中可能会分为左右孩子)，并且左右还在结点不能交换顺序，不能颠倒；

其实链表也可以看作一颗树，只是这颗树的每一个结点只有一个子孩子，那么链表的结构定义是：
typedef struct Node {//结点定义void val;//值域,可以是int，char等等类型struct Node *next;//指针域，用来存下一个结点的地址的
} Node;
那么二叉树他有两个子孩子，就再多定义一个指针域，指向另一个子孩子：
typedef struct Node {//结点定义void val;//值域,可以是int，char等等类型struct Node *lchild, *rchild;//指针域，用来存下一个结点的地址的,分别为左孩子和右孩子
} Node;
逻辑结构

他的逻辑结构就是它最多只有两个子孩子，那么二叉树中每个结点的度小于等于2；

二叉树的性质

1.每个结点的度最多为2；

2.度为0的结点个数比度为2的结点多一个 $N_0 = N_2 + 1$

3.非空的二叉树，第i层的结点数最多为： $2^{i-1}$

4.高度为h的二叉树，节点数最多为： $2^h - 1$

5.满二叉树：也就是除了度0的结点，都是度为2的结点，它的结点数量就是 $2^h - 1$ (这是一种特殊的二叉树)；需要注意的是，满二叉树肯定是完全二叉树，而完全二叉树不一定是满二叉树。

6.完全二叉树：在完全二叉树中叶子结点只能出现在最下层和次下层，且最下层的叶子结点集中在树的左部；也就是说，完全二叉树如果有一个结点没有左子树，但有右子树那么这一定不是完全二叉树；

7.排序二叉树：根节点的值大于左子树，小于右子树的值;

8.平衡二叉树：对于排序二叉树的优化，左右子树中的任意结点高度差不大于1;

结构操作：

对于树的操作，会用到很多递归的编程技巧；递归就是函数调用函数本身，将一个较大的问题分为较小的问题进行处理，然后通过较小问题的返回进行回溯到最开始调用第一次时得到最终结果；

递归举例

举一个经典的递归问题，爬楼梯一次可以上1层或2层，爬20层有几种方式；

先分析爬1层只有一种办法，2层有两种方法，而这两种就是递归分为的最小问题；

而 $f(n) = f(n - 1) + f(n - 2)$ ，n为爬的层数，为什么这个公式成立,先把20层拿进去， $f(20) = f(19) + f(18)$ ,而减一就是从19爬到20，减二就是18爬到20，倒过来想，能爬到20层的只有这两个方法，那爬20层的方法总数就等于它们俩的方法总数的和，所这样一直分化下去，直到只爬一层，两层这样问题就分到了最小，也就是递归出口，这样进行返回，回溯最终得到结果；

代码实现如下：
#include <stdio.h>int f(int n) {if (n <= 2) return n;//递归出口return f(n - 1) + f(n - 2);//开始递归直到递归到出口
}int main() {printf("%d\n", f(20)); return 0;
}
现在有了一点递归的概念后，开始实现二叉树的插入：
#include <stdio.h>
#include <stdlib.h>
#include <time.h>typedef struct Node {//结构定义结点int val;struct Node *lchild, *rchild;
} Node;typedef struct Tree {//定义树int n;        Node *root;
} Tree;Node *getNewNode(int val) {//获取新节点Node *n = (Node *)malloc(sizeof(Node));n->val = val;n->lchild = n->rchild = NULL;return n;
}Tree *getNewTree() {//获取新树Tree *tree = (Tree *)malloc(sizeof(Tree));tree->n = 0;tree->root = NULL;return tree;
}Node * __insert(Node *root, int val, int *ret) {//添加结点操作if (!root) {*ret = 1;return getNewNode(val);}if (val < root->val) root->lchild = __insert(root->lchild, val, ret);else  root->rchild = __insert(root->rchild, val, ret);return root;
}void insert(Tree *tree, int val) {//添加结点int flag = 0;tree->root = __insert(tree->root, val, &flag);tree->n += flag;return ;
jvoid pre_output(Node *root) {// 先序遍历if (!root) return ;printf("%d(", root->val);pre_output(root->lchild);printf(", ");pre_output(root->rchild);printf(")");return ;
}void output(Tree *tree) {//输出树的结果pre_output(tree->root);return ;
}void clearNode(Node *root) {//递归归还空间if (!root) return ;clearNode(root->lchild);clearNode(root->rchild);free(root);return ;
}void clear(Tree *tree) {if (!tree);clearNode(tree->root);free(tree);return ;
}int main() {//测试srand(time(0));Tree *tree = getNewTree();for (int i = 0; i < 10; i++) {int val = rand() % 100;  insert(tree, val);}output(tree);putchar(10);clear(tree);return 0;}
这里只实现了，插入的操作，删除的操作，在后面的文章中讲排序二叉树中会讲到；

遍历二叉树

在上面的代码中pre_output函数的输出就是先序遍历，先序遍历是如何遍历的，根节点左子树，右子树;中序遍历先遍历左子树在遍历根结点最后遍历右子树；后序遍历就是左子树，右子树，根节点；

图4

对图中的树进行先序遍历的结果为：1245367；

  对图中的树进行中序遍历的结果为：4251637；

        对图中的树进行后序遍历的结果为：4526731；

先序遍历的代码：
void pre_orderNode(Node *root) {if (!root) return ;printf("%d ", root->data);//先输出根节点pre_orderNode(root->lchild);//遍历左子树pre_orderNode(root->rchild);//遍历右子树return ;
}void pre_order(Tree *tree) {printf("pre_order : ");pre_orderNode(tree->root);printf("\n");return ;
}
中序遍历代码：
void in_orderNode(Node *root) {if (!root) return ;in_orderNode(root->lchild);//先遍历左子树printf("%d ", root->data);//在打印根节点的值in_orderNode(root->rchild);//在遍历右子树return ;
}void in_order(Tree *tree) {printf("in_order : ");in_orderNode(tree->root);printf("\n");return ;
}
后序遍历代码：
void post_orderNode(Node *root) {if (!root) return ;post_orderNode(root->lchild);//先遍历左子树post_orderNode(root->rchild);//在遍历右子树printf("%d ", root->data);//最终打印根节点值return ;
}void post_order(Tree *tree) {printf("post_order : ");post_orderNode(tree->root);printf("\n");return ;
}