数据结构之树形结构1

1、数据结构之树形结构1树 树是由n(n=0)个节点构成集合。特点是任何两个节点间有且仅有一条路径。ABCDEGHFLJK根节点：没有父亲的节点。 一棵树只有一个根节点。EKJA每个节点可有0个或多个儿子节点除根节点外，每个结点有且只有一个父亲节点J和K是E的儿子节点E是J和K的父亲节点A是E的父节点没有儿子的节点称为叶节点，比如 F G H L J K 都是叶节点父亲相同的节点称为兄弟节点，比如 F G H 是兄弟节点的儿子的个数称为节点的度，比如 A 的度数为4祖先、子孙包含一个节点的所有子孙和该节点本身的集合，称为子树树的存储ABCEGFLJK数组下标123456789ABCEFGLJK节点

2、011122244父亲234儿子56789123456789一般用数组来存储树形结构，用数组下标来表示节点的位置多叉树的缺点：不方便存储，需要n*n的矩阵不方便操作二叉树（Binary tree）二叉树就是每个节点最多只有两个子节点的树。二叉树的特点：1.第i层上最多有 个节点2.高度为h的二叉树最多有 个节点2 2i-1i-12 2h h-1-13.在非空二叉树中，叶节点的个数等于度为2的节点个数加1ABCGFJKLM二叉树每层节点数都达到最大的二叉树树叫满二叉树ABCGFJK满二叉树除最底层外，其余各层节点都达到最大值，且最底层的节点集中在左侧的连续位置上的二叉树叫完全二叉树。ABCGFK

3、完全二叉树二叉树的存储ABCGFJABCFGJ0112232400003560001 2 3 4 5 6一般用多维数组或结构体类型数组来存储数组下标节点的值(data)父亲(father)左孩子(left)右孩子(right) struct node char data; int father,left,right; ; node tree100;tree2.data=B;tree2.father=1;tree2.left=4;tree2.right=5;123456二叉树的遍历Traversal以固定的顺序访问二叉树各个节点，每个节点均恰好被访问一次。左边二叉树遍历的顺序可以是：A B C

4、F G H J K L这种遍历称为层次遍历二叉树按递归遍历有前序、中序、后续三种遍历前序遍历：先访问根节点，然后访问左子树，最后访问右子树。ABCGFJKHL中序遍历：先访问左子树，然后访问根节点，最后访问右子树。后序遍历：先访问左子树，然后访问右子树，最后访问根节点。ABCGFJKHLM前序中序后序A BG KL M CHJFB L K M GA HCJFLM KG BHFJCABXGFJKHVM已知一棵二叉树的中序和后序遍历的顺序，请画出这棵二叉树中序：K,B,V,G,M,J,H,F,X后序：K,V,M,G,B,H,X,F,J已知“中序和前序”或者“中序和后序”可以推出这棵二叉树二叉树遍历

5、的递归实现前序void qian(int p) if(p0) cout0) zhong(treep.left); writeln(treep.data); cout0) hou(treep.left); hou(treep.right); coutn; for(i=1;ixy; /x是y的父亲 if(leftx=0)leftx=y; /若当前x没有左儿子，则y直接成为x的左儿子 else /若x有了左儿子，那么y为左儿子的兄弟，成为左儿子的右儿子 temp=leftx; /y一定是temp的兄弟，讨论右儿子方向 while(righttemp!=0)temp=righttemp; rightt

6、emp=y; 多叉树转二叉树，代码1cinn;for (i=1; ixy; /x是y的父亲 righty=leftx; /x的左儿子是y的兄弟，成为y的右儿子 leftx=y; /y成为x新的左儿子多叉树转二叉树，代码212623381825195297查找7找到了!补充内容：二叉排序树 二叉排序树的特征每个节点的值，都比它的左子节点大，比他的右子节点小（或者反之）。 二叉排序树可用于动态查找二叉排序树的中序遍历：1 3 5 6 7 8 9 12 18 23 25 29若待查节点在第i层，则需查找i次，若待查节点不在树中，则查找次数不超过树高。平均查找复杂度为o(log2n)/输入n个整数，建

7、立二叉排序树void creat_tree() int p,i; cintree1.data; for(i=2;itreei.data; while(true) if(treei.datatreep.data) if(treep.left!=0)p=treep.left; elsetreep.left=i;treei.father=p;break; else if(treep.right!=0)p=treep.right; elsetreep.right=i;treei.father=p;break; /p用于选取树中的节点与要插入的点进行比较/读入第一个数据，当做根节点/依次将2到n号节点插

8、入到树中/每次从根节点开始进行比较/读入一个数据/查找插入的位置,直到找到合适位置为止/如果要插入的数据比p节点的数据小，比较其左孩子/如果p节点有左孩子，p指向左孩子，继续比较/如果p节点没左孩子，则找到了插入的位置 /*如果要插入的数据比p节点的数据大 ，比较其右孩子。如果p节点有右孩子，p 指向右孩子，继续比较。如果p节点没右孩子，则找到了插入的位置，将新插入的节点变为p节点的右孩子*/void insert(int i)/将新的节点(第i个节点)插入到二叉树中 int p=root; while(true) if(treei.datatreep.data) if(treep.left!

9、=0)p=treep.left; else treep.left=i; treei.father=p; break; else if(treep.right!=0)p=treep.right; else treep.right=i; treei.father=p; break; void create_tree() int p,i; scanf(%d,&tree1.data); root=1; for(i=2;i=n;i+) scanf(%d,&treei.data); insert(i); /建立二叉排序树的代码也可以分解成几个函数/在二叉排序树中查找某个值所在的位置int

10、search(int x) int p=root; while(treep.data!=x)&(p!=0) if(xtreep.data) p=treep.left; else p=treep.right; return p;/从根开始比较，比根小，查左子树，反之查右子树/如果p所指节点的值不等于要查找的值x/并且p!=0,表示还没找完整棵树，则继续查找/比p所指的节点的值小，查左子树，反之查右子树/返回找到的位置，没找到结果为0删除排序二叉树中的节点2,91,43,107,28,56,124,19,311,61,4删除删除排序二叉树的节点：1.若被删节点没有左孩子，则用它的右孩子代替

11、它2.若被删除节点有左孩子，则在其左子树中找到值最大的节点P，使被删节点的右子树成为P的右子树。并用被删节点的左孩子代替被删节点。8,5删除10,8P5,7void del(int t) /删除编号为t的节点 int f=treet.father; /f记录t的父亲节点的编号 int Lson=treet.left; /Lson记录t的左孩子节点的编号 int Rson=treet.right; /Rson记录t的右孩子节点的编号 if(Lson=0) /若t没有左孩子，则直接用Rson替代t /删除t:若t为f的左孩子则将Rson变为f的左孩子，否则将Rson变为f的右孩子 if(treef

12、.left=t)treef.left=Rson; else treef.right=Rson; treeRson.father=f; /原来t的父亲变为了t的右孩子的父亲 if(root=t)root=Rson; /root记录根节点编号，被删的可能为根节点 else /讨论t有右孩子的情况 int p=Lson; /找出t左子树中值最大的孩子，将编号存于p中 while(treep.right!=0)p=treep.right; treep.right=Rson; /将t的右子树变为p的子树 treeRson.father=p; /下面用左孩子代替t if(treef.left=t)tree

13、f.left=Lson; else treef.right=Lson; treeLson.father=f; if(root=t)root=Lson; /首先通过前面的find()函数，找到要删除节点的编号t(编号，值)编号就是在数组中的下标删除排序二叉树中的节点2,91,43,107,28,56,124,19,311,61,4删除删除排序二叉树的节点：1.若被删节点没有左孩子，则用它的右孩子代替它2.若被删除节点有左孩子，则在其左子树中找到值最大的节点P，使被删节点的右子树成为P的右子树。并用被删节点的左孩子代替被删节点。8,5删除10,8P5,7void del(int t) /删除编号为

14、t的节点 int f=treet.father; /f记录t的父亲节点的编号 int Lson=treet.left; /Lson记录t的左孩子节点的编号 int Rson=treet.right; /Rson记录t的右孩子节点的编号 if(Lson=0) /若t没有左孩子，则直接用Rson替代t /删除t:若t为f的左孩子则将Rson变为f的左孩子，否则将Rson变为f的右孩子 if(treef.left=t)treef.left=Rson; else treef.right=Rson; treeRson.father=f; /原来t的父亲变为了t的右孩子的父亲 if(root=t)root

15、=Rson; /root记录根节点编号，被删的可能为根节点 else /讨论t有右孩子的情况 int p=Lson; /找出t左子树中值最大的孩子，将编号存于p中 while(treep.right!=0)p=treep.right; treep.right=Rson; /将t的右子树变为p的子树 treeRson.father=p; /下面用左孩子代替t if(treef.left=t)treef.left=Lson; else treef.right=Lson; treeLson.father=f; if(root=t)root=Lson; /首先通过前面的find()函数，找到要删除节点

16、的编号t(编号，值)编号就是在数组中的下标课后练习：何老板的淘宝店 何老板的淘宝店有n(n=10000)种价格不同的商品，且每种商品只有一个。作为店小二的你每天要做的工作有两种： 1.回答顾客提问：顾客问你有没有价格为x的商品，如果有就回答yes，并把该商品出售给顾客。如果没有就回答no。 2.回答何老板的提问：何老板问你有没有价格为x的商品，如果有就回答yes。如果没有就回答no,并且从供货商那里买入一个这种商品。 每个月的月底何老板要检查你的工作记录，请你打印出这个月的问答记录，并把剩余商品按价格由小到大的顺序打印出来。输入格式：第一行，两个空格间隔的整数n和m,分别表示最初的商品个数和提