文章目录 二叉树深度、高度、度 代码实现思路：代码实现举例：
把树的每一个节点认为是集合，每一条边叫做关系
所以是全集分为子集，全划分上一个节点。
树和栈是存在联系的，后续树的遍历过程中会使用到栈（系统栈），表现形式是递归（编程技巧）（？）
单看树的某一条线，和链表实际上是一样的。区别在于，每个节点上链接的下一步next指针域应该是任意多个的。（next指针变成数组）
链表：
typedef struct Node{int data;struct Node *next;}Node, *LindedList;树：
typedef struct Node{int data;struct Node *next[3];}Node, *Tree; 二叉树对二叉树了解后就可以对其他的树进行结构定义。通过“左孩子，右兄弟”表示法，可以将任何树形结构转化为二叉树结构。实际上就是把原本的同级别的放在右下。
深度、高度、度高度：从当前节点开始向下遍历，最远能走到的距离
深度：从当前节点向上遍历的距离。
度：节点下面所挂的节点数（也就是说集合的子集合个数）
节点数=边数 + 1
性质：
1.每个节点度最多为2
2.度为0的节点（叶子节点）比度为2的节点多一个
遍历：
以下树为例
前序遍历：1 2 4 5 3 6（根左右）
中序遍历：4 2 5 1 3 6 （左根右）
后序遍历：4 5 2 6 3 1 （左右根）
完全二叉树：从根到倒数第二层是完美二叉树（要么没孩子，要么有两个），最后一层可以不为满，但全都在左边。为满则为完美二叉树。只缺最后一个孩子。
特点：
1.节点编号按规律：编号为i的节点左孩子为2i，右孩子为2i+1
2.可以用连续空间存储（数组）
满二叉树：指没有度为1的节点，满但不完美
完美二叉树：要么没孩子，要么有两个
具体分别参见：完美二叉树, 完全二叉树和完满二叉树
广义表：
数据结构与算法简记：根据广义表构建二叉树
L=(A(B( ,D),C( ,E))) —>想到栈，左括号入栈，右括号出栈
代码实现思路： 1.先将树用广义表表示出来，那么可以由左右括号联想到要用栈实现（完全包含关系的问题）
2.假设有个栈，那么栈里面存储的东西应该是相关节点的地址
3.左括号入栈，右括号出栈，说明应该为char类型
4.对于A(B( ,D),C(E，))，记录节点A的地址p
5.遇到左括号，对A进行入栈。
6.遇到B，用q记录节点B的地址
7.添加B的关系，即当前栈顶的元素；同时还要判断是左孩子还是右孩子，以逗号判断。
8.遇到右括号，弹栈
代码实现举例： #include<stdio.h>#include<stdlib.h>#include<time.h>//跟链表差不多，链表分为节点和链表的结构定义，所以二叉树也分为两个部分typedef struct Node{ int data; //不需要使用数组struct *Node[2]了，因为二叉树可以直接使用左右孩子指针定义; struct Node *lchild, *rchild;}Node;typedef struct Tree{ Node *root; int n;}Tree;//实现结构操作，分为两个部分，节点的初始化和树的初始化Node *init_node(int val){ Node *p = (Node *)malloc(sizeof(Node));//这里是初始化一个节点，malloc不用*val p->data = val; p->lchild = p->rchild = NULL; return p;}Tree *init_tree(){ Tree *tree = (Tree *)malloc(sizeof(Tree)); tree->root = NULL; tree->n = 0; return tree;}//销毁操作void clear_node(Node *node){ if(node == NULL) return; //因为lchild不是通过malloc开辟的，所以不能free(node->lchild)，应该使用递归进行销毁; clear_node(node->rchild); clear_node(node->lchild); free(node); return;}void clear_tree(Tree *tree){ if(tree == NULL) return ; clear_node(tree->root); free(tree); return;}//树的其他操作，如插入//二叉排序树（二叉搜索树），这种树的任何三人组而言，根节点的值会大于左子树的值，小于右子树的值//需求：按照二叉排序树给二叉树插入节点Node *insert_node(Node *root, int val, int *flag){ if(root == NULL) {//认为此时插入成功 *flag = 1; return init_node(val); } if(root->data == val) return root; if(val < root->data) root->lchild = insert_node(root->lchild, val, flag);//说明应该往左边插入 else root->rchild = insert_node(root->rchild, val, flag); return root;}void insert(Tree *tree, int val){ int flag = 0; tree->root = insert_node(tree->root, val, &flag); tree->n += flag; return;}//实现遍历操作void pre_order_node(Node *node){ if(node == NULL) return; printf("%d ", node->data); pre_order_node(node->lchild); pre_order_node(node->rchild); return;}void pre_order(Tree *tree){ if(tree == NULL) return; printf("pre_order : "); pre_order_node(tree->root); printf("n"); return;}void in_order_node(Node *node){ if(node == NULL) return; in_order_node(node->lchild); printf("%d ", node->data); in_order_node(node->rchild); return;}void in_order(Tree *tree){ if(tree == NULL) return; printf("in_order : "); in_order_node(tree->root); printf("n"); return;}void post_order_node(Node *node){ if(node == NULL) return; post_order_node(node->lchild); post_order_node(node->rchild); printf("%d ", node->data); return;}void post_order(Tree *tree){ if(tree == NULL) return; printf("post_order : "); post_order_node(tree->root); printf("n"); return;}//二叉树转广义表void output_node(Node *node){ if(node == NULL) return; printf("%d ", node->data); if(node->lchild == NULL && node->rchild == NULL) return; printf("("); output_node(node->lchild); printf(","); output_node(node->rchild); printf(")"); return;}void output(Tree *tree){ if(tree == NULL) return; printf("tree(%d): ", tree->n); output_node(tree->root); printf("n"); return;}int main(){ srand(time(0)); Tree *tree = init_tree(); #define max_op 10 for(int i = 0; i < max_op; i ++){ int val = rand() % 100; insert(tree,val); output(tree); } pre_order(tree); in_order(tree); post_order(tree); #undef max_op clear_tree(tree); return 0;}//实现操作：随机生成并插入max_op个节点，大小均为100以内，并实现前序中序后序遍历 int val = rand() % 100; insert(tree,val); output(tree);}pre_order(tree);in_order(tree);post_order(tree);#undef max_opclear_tree(tree);return 0;}
//实现操作：随机生成并插入max_op个节点，大小均为100以内，并实现前序中序后序遍历