树

[树的定义](https://baike.baidu.com/item/%E6%A0%91/2699484?fr=aladdin) 树的父亲表示法： ```cpp 当只需要查找每个节点对应的父节点时，就可以只记录父节点。 struct node{ int v;//记录当前节点的值 int fa;//记录当前节点的父节点的编号 }; ``` 二叉树：指每个节点最多只有两个子节点。子节点会被区分为左子节点和右子节点（就算只有一个子节点也会区分）。 二叉树在程序中的存储方式及遍历 ```cpp struct node{ int l,r;//记录左右子节点的下标 int v;//记录当前节点的值（可以没有，也可以很多，视题目要求而定） }; node tr[1000]; void dfs(int x){ if(x==0)return; //在这一行输出当前节点，结果为前序遍历 dfs(tr[x].l); //在这一行输出当前节点，结果为中序遍历 dfs(tr[x].r); //在这一行输出当前节点，结果为后序遍历 } ``` 非二叉树的存储可参考图的存储 \----------------------------- [完全二叉树的定义与基本性质](https://baike.baidu.com/item/%E5%AE%8C%E5%85%A8%E4%BA%8C%E5%8F%89%E6%A0%91/7773232?fr=aladdin) 一般情况下，完全二叉树的编号从上往下从左往右依次增大，根节点编号为1，节点x的左子节点编号为x\*2，右子节点编号为x\*2+1，父节点编号为x/2。 由于不需要记录每个节点的子节点编号，所以不需要结构体来记录完全二叉树，只需要一个数组来记录每个节点的值即可。 \----------------------- 二叉排序树 若一棵二叉树的每个节点的值都大于左子树里每个节点的值，且小于右子树里每个节点的值，那么这棵二叉树就被称作二叉排序树。即：如果中序遍历为递增序列，那么就是二叉排序树。 在二叉排序树里新增节点： ```cpp struct node{ int l,r;//记录左右子节点的下标 int v;//记录当前节点的值（可以没有，也可以很多，视题目要求而定） int cnt;//记录当前节点的值有多少个 }; node tr[1000]; int num=0;//表示节点个数 void ins(int now, int x){//now表示节点编号，x表示要插入的值 if(x==tr[now].v){ tr[now].cnt++; return; } if(x<tr[now].v){ if(tr[now].l)ins(tr[now].l,x); else { num++; tr[num].v=x; tr[num].cnt=1; tr[now].l=num; } } else { if(tr[now].r)ins(tr[now].r,x); else { num++; tr[num].v=x; tr[num].cnt=1; tr[now].r=num; } } } ``` \----------------------------------- [哈夫曼树](https://blog.csdn.net/weixin_43956763/article/details/115213005)