树简介
树结构是具有一定关系的n个结点的集合。树结构是一个递归定义，树结构有且仅有一个称为根的结点，每个结点又是具有一定关系的集合且称为根结点的子树。
树有且仅有一个根结点，对于子树的结点是互不相交的。
结点：是树种一个独立的元素，指向字数的分支。
结点的度：结点拥有字树的个数。
树的度：树中结点度的最大值。
叶子：度为0的结点（没有字树的结点）也叫终端结点。
双亲和孩子：结点的字树称为孩子，字树的根结点称为双亲。
层次：结点的层次从根节点开始且定义为第一层，层次累加。
树的深度：树中结点最大的层次，称为树的深度或高度。
有序树和无序树：将树的结点按从左向右的有次序的树，称为有序树，否则反之。
森林：是 m (m>0)棵互不相交的树的集合。
二叉树
二叉树特殊的树，定义为每个结点至多有两个子树，字树有左右之分。
满二叉树
每个结点都有左右字树。
完全二叉树
二叉树从上而下，从左到右排序编号1-n与结点位置一一对应时称为完全二叉树。
从树的定义可以看出，树是就有一定关系的集合。元素是分散的，存储空间也一定连续。这点和链表类似。
二叉树树的存储结构
由于二叉树的特殊性，且具有一定规律性，因此二叉树相比于一般树更容易实现。
- 顺序存储结构
完全二叉树，自上而下，从左到右和结点一一对应，因此可以使用地址连续的空间存储。
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
typedef struct{
int elem[100];
int length;
}ZxTree;
//初始化二叉树
ZxTree Init(){
ZxTree tree;
tree.elem[0] = 0;
tree.length = 0;
return tree;
}
//创建二叉树
void Create(ZxTree *tree,int e){
if(tree->length == 0){
tree->elem[0] = e;
tree->length ++;
}else{
tree->elem[tree->length] = e;
tree->length ++;
}
}
//返回二叉树深度
int treeDepth(ZxTree tree){
//因为是二叉树满足层次满足2^(k-1),所有结点满足2^k-1
// 实际二叉树结点 n 2^(k-1)<n<2^k-1
double tmp = log2(tree.length);
int reault = floor(tmp+1.0);
return reault;
}
//返回二叉树的根结点
int treeRoot(ZxTree tree){
return tree.elem[0];
}
//查找
int treeQuery(ZxTree tree, int e){
for(int i=0;i<tree.length;i++){
if(tree.elem[i] == e){
return i;
}
}
return -1;
}
//修改
int treeModify(ZxTree *tree, int e,int x){
for(int i=0;i<tree->length;i++){
if(tree->elem[i] == e){
tree->elem[i] = x;
return 1;
}
}
return -1;
}
//打印二叉树
void display(ZxTree tree){
printf("打印二叉树：");
for(int i=0;i<tree.length;i++){
//TODO
printf("%d",tree.elem[i]);
}
printf("\n");
}
int main(){
ZxTree tree = Init();
//printf("%d\n",tree.elem[0]);
//printf("%d",tree.elem[1]+tree.elem[0]);
Create(&tree,2);
Create(&tree,3);
Create(&tree,4);
Create(&tree,5);
display(tree);
int a = treeDepth(tree);
printf("%d",a);
}
完全二叉树由于其特殊的性质，满足2^(k-1)和(2^k)-1和有序性，从而能够计算出结点位置和其他属性。
对于非完全二叉树，没有顺序的限定，因此位置和计算公式没有绝对的关系，那么有些位置可能没有结点，在没有结点处用0代替。
- 链式存储结构
在二叉树上每个结点需要指向左右子树，因此需要有两个指针域，如果需要记录父节点还需要双亲域。
不论是那种方式都需要一个头结点记录根结点地址 。
对于顺序存储的二叉树通过循环遍历即可，但是对于二叉链表，需要按照链表的逻辑依次遍历了。
对于单链表来说通过node->next != NULL即可，但是二叉树有其独特的结构。 每个结点有三个域，数据域和左右子树域。三个域均可作为第一个访问的元素，那么就有6中访问形式。在完全二叉树中限定了左右子树不可颠倒，因此遍历也需要从左到右。因此访问顺序就变成了3种：根结点—–左字树—–右字树；左字树——-根结点——右字树；左字树——右字树——根结点。分别称为先序遍历，中序遍历，后序遍历（以根结点访问循序决定）。
#include<stdio.h>
#include<stdlib.h>
typedef int Elem;
typedef struct Node{
Elem data;
struct Node *Lnode, *Rnode;
}TreeNode,ZxTree;
中序遍历
头结点先访问根结点，在访问左字树，最后访问右子树。
#include<stdio.h>
#include<stdlib.h>
typedef int Elem;
typedef struct Node{
Elem data;
struct Node *Lnode, *Rnode;
}TreeNode,ZxTree;
//初始化
void Init(ZxTree *tree){
tree = (TreeNode*)malloc(sizeof(TreeNode)); //初始化头结点
tree->Lnode = NULL;
tree->Rnode = NULL;
}
//创建二叉树
void Create(ZxTree *tree,Elem e){
//根结点(二叉树本身地址为头结点，其左字树指向根结点)
TreeNode *head = tree;
//新结点作为根结点
TreeNode *node = (TreeNode*)malloc(sizeof(TreeNode));
node->data = e;
node->Lnode = NULL;
node->Rnode = NULL;
if(head->Lnode == NULL){ //左字树为空左子树指向新结点，否则右子树指向新结点
head->Lnode = node;
}else{
head->Rnode = node;
}
}
//中序遍历
void display(ZxTree *tree){
if(tree != NULL){
printf("%d~",tree->data);
display(tree->Lnode);
//printf("%d-",tree->);
display(tree->Rnode);
}else{
return;
}
}
int main(){
ZxTree tree;
Init(&tree);
Create(&tree,2);
Create(&tree,4);
Create(&tree,6);
display(&tree);
return 1;
}
可以看到上述代码只能创建一个如下所示的二叉树，不能再多一点。
上述创建二叉树的代码显然是错误的，但是中序遍历的递归方法确实正确的。创建二叉树也需要通过遍历创建。
非递归实现
遍历的非递归实现需要借助栈的帮助，因为在遍历的同时结点向叶子结点移动，无法在回去，需要借助栈来保存以往的结点，重新取出右字树。
创建二叉树并遍历
由于链表的指针域依次指向下一个地址就可以创建一个连续的链表，在二叉链表由于左右字树的存在无法批量创建。
int main(){
//创建所需二叉树
TreeNode* nodeList[10];
for(int i=0;i<6;i++){
TreeNode *node = (TreeNode*)malloc(sizeof(TreeNode));
node->data = i+1;
node->Lnode = NULL;
node->Rnode = NULL;
nodeList[i] = node;
}
nodeList[0]->Lnode=nodeList[1];
nodeList[0]->Rnode=nodeList[2];
nodeList[1]->Lnode=nodeList[3];
nodeList[1]->Rnode=nodeList[4];
nodeList[2]->Lnode=nodeList[5];
ZxTree tree;
tree.Lnode = nodeList[0];
display(&tree);
return 1;
}
中序遍历
//递归中序遍历
//中序遍历
void display(ZxTree *tree){
if(tree != NULL){
display(tree->Lnode);
printf("%d~",tree->data);
display(tree->Rnode);
}
}
中序遍历先操作左子树在节点，最后右子树，因此输出顺序为425163。
先序遍历
先序遍历先访问节点然后左子树，最后右子树。顺序因该是124536。
void display(ZxTree *tree){
if(tree != NULL){
printf("%d~",tree->data);
display(tree->Lnode);
display(tree->Rnode);
}
}
后序遍历
后序遍历先访问左子树再访问右子树，最后节点。顺序应该是452631。
void display(ZxTree *tree){
if(tree != NULL){
display(tree->Lnode);
display(tree->Rnode);
printf("%d~",tree->data);
}
}
数据结构——二叉树先序、中序、后序及层次四种遍历（C语言版）文章以动画的形式解析了三种遍历方法的过程，生动形象，感谢作者大大。
树的存储结构
上面研究了二叉树的存储结构，接下来是普通树了，有特殊的树能扩展到普通树吗？在链式存储结构中，定义了左子树和右子树，但是在普通树上并不确定有多少子树，所以不能通过链式结构。
- 双亲表示法
每个结点除了数据域data外，还附设一个parent域用以指示其双亲结点的位置。如下：
若干节点构成树时，parent指向双亲节点的坐标。
对于0坐标R是根节点坐标为-1。A.B,C分别是其子树，那么他们的parent指向坐标0即R根结点，同理D，E双亲为A，指向A的坐标为1（坐标本身的顺序决定了子树的左右顺序）。
实现方式以连续的空间存储树的结点，每个结点包含数据域和双亲结点的位置。
//节点定义
typedef struct Node{
int data;
int parent;
}Node;
//树定义
typedef struct{
Node Tree[100];
int head,number;
}PTree;
//创建树
#include<stdio.h>
#include<stdlib.h>
/*
树的双亲表示法
*/
//双亲表示法的结点
typedef struct PNode{
char data;
int parent;
} PNode;
//结点生成树
typedef struct{
PNode node[10]; //树有10个结点
int tree_length; //树的长度
}PTree;
//树是具有一定关系的结点
//初始化
PTree* treeInit(char e){
PNode *node = (PNode*)malloc(sizeof(PNode));
node->data = e;
node->parent = -1;
PTree *tree = (PTree*)malloc(sizeof(PTree));
(*tree).node[0] = *node;
tree->tree_length = 0;
return tree;
}
//创建树
void catrePTree(PTree *tree){
//A结点
PNode *node_a = (PNode*)malloc(sizeof(PNode));
node_a->data = 'A';
node_a->parent = 0;
tree->tree_length++;
(tree->node)[tree->tree_length] = *node_a;
//printf("%c",(tree->node)[1].data);
//printf("%c,%d",tree->node->data,tree->node->parent);
//printf("%c,%d",node_a->data,node_a->parent);
//B结点
PNode *node_b = (PNode*)malloc(sizeof(PNode));
node_b->data = 'B';
node_b->parent = 0;
tree->tree_length++;
((*tree).node)[tree->tree_length] = *node_b;
//C结点
PNode *node_c = (PNode*)malloc(sizeof(PNode));
node_c->data = 'C';
node_c->parent = 0;
tree->tree_length++;
((*tree).node)[tree->tree_length] = *node_c;
//d结点
PNode *node_d = (PNode*)malloc(sizeof(PNode));
node_d->data = 'D';
node_d->parent = 1;
tree->tree_length ++;
(*tree).node[tree->tree_length] = *node_d;
//E结点
PNode *node_e = (PNode*)malloc(sizeof(PNode));
node_e->data = 'E';
node_e->parent = 1;
tree->tree_length ++;
(*tree).node[tree->tree_length] = *node_e;
//f结点
PNode *node_f = (PNode*)malloc(sizeof(PNode));
node_f->data = 'F';
node_f->parent = 3;
tree->tree_length ++;
(*tree).node[tree->tree_length] = *node_f;
//g结点
PNode *node_g = (PNode*)malloc(sizeof(PNode));
node_g->data = 'G';
node_g->parent = 6;
tree->tree_length ++;
(*tree).node[tree->tree_length] = *node_g;
//h结点
PNode *node_H = (PNode*)malloc(sizeof(PNode));
node_H->data = 'H';
node_H->parent = 6;
tree->tree_length ++;\
(*tree).node[tree->tree_length] = *node_H;
//k结点
PNode *node_K = (PNode*)malloc(sizeof(PNode));
node_K->data = 'K';
node_K->parent = 6;
tree->tree_length ++;
(*tree).node[tree->tree_length] = *node_K;
}
int main(){
PTree *tree = treeInit('R');
catrePTree(tree);
for(int i=0;i<=tree->tree_length;i++){
printf("[%c,%d]",(tree->node)[i].data,(tree->node)[i].parent);
}
}
如上图所示创建了双亲结点表示的树。
- 孩子表示法
方法一
树中每个结点可能有多棵子树，则可用多重链表。即一个结点存在多个指向该结点的链表。那么需要知道每个结点存在的字树的格式（结点的度），而每个结点的度不一样，所以一般以树的度为每个结点度（结点的度一定小于等于树的度）。
但是实际使用的结点一定小于分配内存，造成了空间浪费。而且还能计算出浪费指针域：在一棵有n个结点度为K 的
树中必有n(k-1) + 1个空链域。
方法二
在结点中新增一个数据域，用来存储指向该节点的度，并且每个结点分配度个数的指针域。
这样每个结点需要多少指针域就分配多少不会造成空间浪费。
方法三
用顺序表存储结点，用链表表示结点的孩子结点。
方法四
双亲孩子表示法，将两种方式结合。
- 孩子兄弟表示法
该方法又称二叉树表示法，或二叉链表表示法，即以二叉链表做树的存储结构。
孩子兄弟表示法的实现方式是每个结点有左右字树，左子树指向该结点的孩子结点，右字树指向兄弟结点。
一般树表示：
孩子兄弟表示（二叉树表示）：
链表中结点的两个链域分别指向该结点的第一个孩子结点和下一个兄弟结点。
R左字树指向孩子结点A，右字树指向兄弟结点（无）。这样表示奇妙的是能够完全使用表示结点且能展结点的一定层次关系。
二叉树表示法的每个结点的左子树（包含左子树）的所有右子树的结点都是该节点的孩子结点，是左子树的兄弟结点。
这种存储结构的优点是它和二叉树的二叉链表表示完全一样， 便千将一般的树结构转换为二叉树进行处理， 利用二叉树的算法来实现对树的操作。（最常用的存储方法）
#include<stdio.h>
#include<stdlib.h>
//树的二叉表示法
//结点
typedef struct SNode{
struct SNode *child;
char data;
struct SNode *brother;
}SNode,STree;
//
STree* init(char e){
SNode *node = (SNode*)malloc(sizeof(SNode));
node->data = 'R';
node->brother = NULL;
node->child = NULL;
return node;
}
//
void create(STree *tree){
//A
SNode *node_a = (SNode*)malloc(sizeof(SNode));
node_a->data = 'A';
node_a->brother = NULL;
node_a->child = NULL;
tree->child = node_a;
//b
SNode *node_b = (SNode*)malloc(sizeof(SNode));
node_b->data = 'B';
node_b->brother = NULL;
node_b->child = NULL;
node_a->brother = node_b;
//c
SNode *node_c = (SNode*)malloc(sizeof(SNode));
node_c->data = 'C';
node_c->brother = NULL;
node_c->child = NULL;
node_b->brother = node_c;
//d
SNode *node_d = (SNode*)malloc(sizeof(SNode));
node_d->data = 'D';
node_d->brother = NULL;
node_d->child = NULL;
node_a->child = node_d;
//e
SNode *node_e = (SNode*)malloc(sizeof(SNode));
node_e->data = 'E';
node_e->brother = NULL;
node_e->child = NULL;
node_d->brother = node_e;
//f
SNode *node_f = (SNode*)malloc(sizeof(SNode));
node_f->data = 'F';
node_f->brother = NULL;
node_f->child = NULL;
node_c->child = node_f;
//G
SNode *node_G = (SNode*)malloc(sizeof(SNode));
node_G->data = 'G';
node_G->brother = NULL;
node_G->child = NULL;
node_f->child = node_G;
//h
SNode *node_h = (SNode*)malloc(sizeof(SNode));
node_h->data = 'H';
node_h->brother = NULL;
node_h->child = NULL;
node_G->brother = node_h;
//k
SNode *node_k = (SNode*)malloc(sizeof(SNode));
node_k->data = 'K';
node_k->brother = NULL;
node_k->child = NULL;
node_h->brother = node_k;
}
//二叉树递归遍历(先序遍历)
void bianli(STree *tree){
if(tree == NULL){
return;
}
printf("%c",tree->data);
bianli(tree->child);
bianli(tree->brother);
}
int main(){
STree *tree = init('R');
create(tree);
bianli(tree);
}
对构造的二叉树表示的使用先序遍历结果也完全一致。
这种存储结构的优点是它和二叉树的二叉链表表示完全一样， 便千将一般的树结构转换为二叉树进行处理， 利用二叉树的算法来实现对树的操作。
森林存储方式
由树的二叉链表表示的定义可知，任何一棵和树都有对应的二叉树表示，且其二叉树表示的根结点的右子树必空。森林又是树的集合，若把森林的第二棵树看做第一棵树的二叉表示法的根右字树。那么这个森林就合并成了一个二叉树。
以此类推，森林的多个树转化的二叉表示法，均为前一个树的二叉表示的根结点的右子树，这样森林的所有树均归并到二叉表示法中。
森林使用二叉树表示法存储，对二叉树的遍历一般有先序，中序，后序，层次遍历。
双亲存储，孩子表示法的存储方式的树不具有统一的规律，无法使用递归，二叉树表示法可以。
== 树没有中序遍历==
由于森林使用二叉树表示法，满足二叉树的特性因此可以使用二叉树的变量方法。但是缺也有一些限制，如树的二叉树表示法没有中序遍历。
原因是，树的二叉树表示法树的孩子结点可以任意交换顺序，这是树并没有变化，但是兄弟结点有多个，不符合中序遍历。
二叉树有先序后序中序，因为二叉树就三个部分：根，左子树，右子树。但是树不一定只有三个部分，所以只能大致分为两个部分：根，子树。所以遍历有先根，后根
森林没有后续遍历
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/156117.html
