一.树的结构定义
typedef struct Node {int data;Node* next;
}Node, *LinkList;typedef struct Node {int data;Node* next[3];
}Node, *Tree;
//三叉树的定义
树的深度\高度\度
(1)树的深度/高度为5;
(2)节点4的1深度为1,高度为3;
(3)节点2的度为1,节点1的度为3;
(4)节点数量等于边数加1;
树形结构的深入理解:
树的节点代表"集合";
树的边代表"关系";
二.广度遍历和深度遍历
1.广度优先遍历(层序遍历)
借助一个队列:
先将根节点压入队列中,然后在他出队的时候再将他的所有子节点进行入队;
这样就可以达到层序遍历的效果;
2.深度优先遍历
借助一个栈:
先将根节点入栈,此后若该节点存在子节点,就先将子节点进行入栈,直到没有节点可以入栈;
此时再把相关的节点进行弹栈;
若将入栈和出栈顺序按照时间顺序进行排序,则可以得到:
判断一个节点是否为另一个节点子节点的方法:
看对应的时间戳是否具有包含关系!
比如: 节点3[6,14] 节点8[10,11] 所以节点8是节点3的子节点;
三.二叉树
结构定义:
(1)每个节点的度数最多为2;
(2)度为0的节点比度为2的节点多1个;
证明: 点数=边数+1;
n0 + n1 + n2 = n1 + 2n2 + 1 ==> n0 = n2 + 1;
二叉树的特殊种类:
完全二叉树 满二叉树 完美二叉树
完全二叉树:每一层从左到右进行存储直到这一层满了;
满二叉树:没有度为1的节点;
完美二叉树:每一层都是满的;
!!完全二叉树的性质:
1.编号为i的子节点:
右孩子编号:2 * i;
左孩子编号:2 * i + 1;
2.由于性质1,可以用连续的空间来进行存储完全二叉树(数组);
---------------------------------------------------------------------------------------------------------------------------------
扩展:将其他的树形结构转换为二叉树:左孩子右兄弟表示法
如右图,将三叉树转换为一个二叉树: 
意义:可以节省储存空间
---------------------------------------------------------------------------------------------------------------------------------
代码实现:
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<time.h>typedef struct Node {int key;Node* lchild, *rchild;
}Node;Node* getNewNode(int key) {Node* p = (Node*)malloc(sizeof(Node));p->key = key;p->lchild = NULL;p->rchild = NULL;return p;
}Node* insert(Node* root, int key) {if (root =
