62二 1.二又树的概念 每个结点最多有2棵子树,并且子树有左右之 分,不能任意颜倒 二又树有5种形态: ①空树②只有一个根 ③只有左子树④只有右子树 ⑤有两个子树 2.二又树的性质 在二又树的第层上E多有2-1个结点(>=1 ②深度冰的二叉树至多有2-1个结点
6 6.2 二叉树 1. 二叉树的概念 每个结点最多有2棵子树，并且子树有左右之 分，不能任意颠倒。 二叉树有5种形态： ①空树 ②只有一个根 ③只有左子树 ④只有右子树 ⑤有两个子树 2. 二叉树的性质 ①在二叉树的第i层上至多有2 i－1个结点(i>=1) ②深度为k的二叉树至多有2 k -1个结点。 1 2 3 4 5 6 7 8 9
Xpfcont'd) 2.二又树的性质 ③设二又树中,叶结点数为0度为1的结点数为1度 为2的结点数机m2,则有:n=n2+1 因为N=n0+n1+n2=1+n1*1+n22 ④具有n个结点的完全二又树的深度为Log2n/+1 og2n/表示g2取整 满二又树:具有最多结点数的二又树(即一棵深度为 k且有2k-1个结点的二叉树) 完全二叉树:将满二叉树从右向左 删除叶子的结果,因此, ⑤ 结点数n<=2k-1,并且n>2k1-1
7 二叉树(cont’d) 2. 二叉树的性质 ③ 设二叉树中，叶结点数为n0 ,度为1的结点数为n1 ,度 为2的结点数为n2 ,则有： n0 = n2 + 1 因为 N=n0+n1+n2=1+n1 *1+n2 *2 ④ 具有n个结点的完全二叉树的深度为 log2n +1 log2n 表示 log2n取整 满二叉树：具有最多结点数的二叉树（即一棵深度为 k且有2 k -1 个结点的二叉树） 完全二叉树：将满二叉树从右向左 删除叶子的结果，因此 , 结点数 n<=2k -1，并且n>2k-1 -1 1 2 3 4 5 6 7 8 9
XBfIcont d 3.二又树的存情结构 (1)顺序存,利用数组按照完全二又树的方式 对结点编号,根据编号将结点存放在数组中相应 的位置中 # define M50∥二叉树的最大结点数 typedef elemtype SQTREEIN∥顺序存储的二叉树 SQ TREE bt 0123456789 ABCEF ①F6
9 二叉树(cont’d) 3. 二叉树的存储结构 (1) 顺序存储，利用数组按照完全二叉树的方式 对结点编号，根据编号将结点存放在数组中相应 的位置中。 #define N 50 //二叉树的最大结点数 typedef elemtype SQTREE[N]; //顺序存储的二叉树 SQTREE bt; A B C E F 1 2 3 4 5 6 A B C E F 0 1 2 3 4 5 6 7 8 9
XBfIcont d 3.二又树的存储结构 (2)链式存储,利用二又链表或三又链表 PARENT KIANN /child data rchild B 团CZ DATA Iciild data parent rchild LCHILD RCHILD E酉F typedef struct treenode teletype data;M结点数据 指向左右孩子的指针 struct treenode lchild, rchild / parent*/, JTREENODE, *TREENODEPTR, BTREE
10 二叉树(cont’d) 3. 二叉树的存储结构 (2)链式存储，利用二叉链表或三叉链表 typedef struct treenode {elemtype data; //结点数据 //指向左右孩子的指针 struct treenode *lchild,*rchild /*,*parent*/; }TREENODE,*TREENODEPTR,*BTREE A ^B C^ ^ E ^ ^ F ^ DATA PARENT LCHILD RCHILD lchild data rchild lcjild data parent rchild
14.一又树的建立(1)按层序历序为入顺序 whil(font<=rear)/只要队列不空 {t=q[font;font++;/出队一结点指针 scanf(%d", &value) if( value==0)t->lchild==NULL it>Child=(TREENODEPTR)malloc(sizeof(TREENODE)): t->lchild->data=value ∥建立左孩子结点 rear+;q[rear]-t-) Child;∥左孩子入队 scanf(%od", &value) if(value==0)t>rchild=NULL it >rchild=(TREENODEPTR)malloc(sizeof(TREENODE) t->rchild->data=value ∥建立左孩子结点 rear++;q[rear}=t> rchild;∥左孩子入队 i//while
11 ＃define N 50 //定义二叉树最大结点数 void createtree(BTREE *root) {int value,front,rear; TREENODEPTR t,q[N]; //q是队列，front,rear是队头队尾下标。 scanf("%d",&value); //开始创建根结点 if(value==0){*root=NULL; return;}; //输入0，表示空结点 *root=(TREENODEPTR)malloc(sizeof(TREENODE)); (*root)→data=value; rear=front=1; q[front]=*root; //根指针入队 二叉树(cont’d) 4. 二叉树的建立 (1) 按层序遍历顺序为输入顺序 while(front<=rear) //只要队列不空 { t＝q[front]; front++; //出队一结点指针 scanf("%d",&value); if(value==0) t→lchild=NULL; else {t→lchild=(TREENODEPTR)malloc(sizeof(TREENODE)); t→lchild→data=value; //建立左孩子结点 rear++; q[rear]=t→lchild; //左孩子入队 } scanf("%d",&value); if(value==0) t→rchild=NULL; else {t→rchild=(TREENODEPTR)malloc(sizeof(TREENODE)); t→rchild→data=value; //建立左孩子结点 rear++; q[rear]=t→rchild; //左孩子入队 } }//while } 5 3 4 7 9