《数据结构与算法——C语言和Java语言描述 ppt及答案和其他资源8二叉树的建立》由会员分享，可在线阅读，更多相关《数据结构与算法——C语言和Java语言描述 ppt及答案和其他资源8二叉树的建立（9页珍藏版）》请在金锄头文库上搜索。
1、创 建 二 叉 树,6.2二叉树 (Binary Tree),二叉树的定义 一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。每个结点最多只有2个孩子。,若i = 1,则该结点为根，无双亲结点 若i 1,则该结点的双亲结点编号为i /2 若2i n,则有编号为2i 的左孩子，否则没有左孩子 若2i+1 n,则有编号为2i+1的右孩子，否则没有右孩子 若 i 为奇数,且i != 1,则其左兄弟编号为i-1 若 i 为偶数,且i != n,则其右兄弟编号为i+1,性质5 如果将一棵有n个结点的完全二叉树自顶向下，同一层自左向右
2、连续给结点编号 1, 2, , n，那么，对于编号为i (1 i n) 的结点,则有以下关系：,二叉树的顺序存储结构,用一组连续的的存储单元存放二叉树中的元素，即按满二叉树的形式存放在一维数组中 结点的编号恰好与数组元素的下标相对应 根据二叉树性质5，结点在一维数组中的相对位置隐含着结点之间的关系 适用于满二叉树和完全二叉树,根据二叉树性质5，在数组中可以方便地由某结点的下标找到它们的双亲结点，或左、右孩子结点,存储示例,(a)完全二叉树的数组表示,(b)一般二叉树的数组表示,由于在顺序存储结构中是以结点在数组中的相对位置表示结点之间的关系，因此，一般二叉树也必须以完全二叉树的形式来存储，可能
3、会造成存储空间的浪费。,单支树就是一个极端情况。例如，深度为k 的单支二叉树，它只有k个结点却需要2k-1个存储单元。,最常用的是二叉链表和三叉链表 二叉链表的每个结点有一个数据域和两个指针域，一个指针指向左孩子，另一个指向右孩子。,二叉树的链式存储结构,结点结构描述为： typedef struct btnode ElemType data; /* 数据域*/ struct btnode *lchild; /* 左孩子指针域*/ struct btnode *rchild; /* 右孩子指针域*/ BTNode;,/以先根遍历创建二叉树,AB#D#C# void Creat(BiTree *bt) Elemtype ch; printf(“请输入字符AB#D#C#:“); scanf(“%c“,else *bt=(BiTree)malloc(sizeof(btNode);/分配根节点 if(!*bt) printf(“分配节点失败n“);exit(0); (*bt)-data=ch; Creat( ,
