数据结构创建叉树.pptVIP

建立二叉树的存储结构（二叉链表） 不同的定义方法相应有不同的存储结构的建立算法 * * 以字符串的形式 “根 左子树 右子树”定 义一棵二叉树 按层次输入边建二叉树 按给定的表达式建相应的表达式二叉树 由二叉树的先序和中序序列建二叉树 以字符串的形式 “根 左子树 右子树” 定义一棵二叉树（递归算法） 例如: 以字符串#表示 A B C D AB#C##D## 空树 只含一个根结点的二叉树 A 以字符串A ##表示 以下列字符串表示 右子树 左子树 int CreateBiTree(BiTree T) { scanf(ch); if (ch==#) T = NULL; else { if (!(T = new BiTNode)) exit(0); T-data = ch; // 生成根结点 CreateBiTree(T-lchild); // 构造左子树 CreateBiTree(T-rchild); // 构造右子树 } return 1; } // CreateBiTree A B C D A B C D 上页算法执行过程举例如下: A T B C D ^ ^ ^ ^ ^ scanf(ch); if (ch==‘#) T = NULL; else { if (!(T = new BiTNode)) exit(0); T-data = ch; CreateBiTree(T-lchild); CreateBiTree(T-rchild); } 表示# a b c d e f g ^ ^ ^ ^ ^ ^ ^ ^ 按字符串输入：abc##d##e#fg### 写出递归调用过程 读入边的非递归算法 按从上到下、从左到右的顺序依次输入二叉树的边(区分左右分支)。即读入 (father,child, lrflag)为一条边的信息，建立二叉树的二叉链表。 需要一个队列保存已建好的结点的指针。 (双亲结点指针) A F B C G E D 算法核心： 每读一条边之后，生成孩子结点，并做为叶子结点；之后将该结点的指针保存在队列中。从队头找该结点的双亲结点指针，按lrflag值建立双亲结点的左右孩子关系。 (‘#’, ‘A’, 0) (‘A’, ‘B’, 0) (‘B’, ‘C’, 1) (‘C’, ‘D’, 0) (‘C’, ‘E’, 1) (‘D’, ‘F’, 0) (‘D’, ‘G’, 1) (‘F’, ‘#’, 0) ^ B ^ ^ C ^ ^ E ^ (‘#’, ‘A’, 0) (‘A’, ‘B’, 0) (‘B’, ‘C’, 1) (‘C’, ‘D’, 0) (‘C’, ‘E’, 1) ^ D ^ (‘D’, ‘F’, 0) (‘D’, ‘G’, 1) (‘F’, ‘#’, 0) ^ G ^ ^F ^ A B C D E G F A F B C G E D 队列中保存已建好的(孩子)结点的指针 读入方式： T=NULL T ^ A ^ void Creat_BiTree(BiTree T){ InitQueue(Q)；T=NULL；scanf(fa, ch, lrflag)； while (ch!=’#’){ p= new BiTNode ； p-data=ch； // 创建孩子结点 p-lchild= p-rchild =NULL； // 做成叶子结点 enqueue(Q，p)；//指针入队列 if (fa == ?# ?) T= p; //所建为根结点 else { } //非根结点的情况 scanf(fa, ch, lrflag)； } // end_while } // Create_BiTree s=GetHead(Q)； //取队列头元素(指针值) while (s-data != fa ) { dequeue(Q)；//出队列 s=GetHead(Q)； } // 在队列中找到双亲结点 if (lrflag==0) s-lchild = p； // 链接左孩子结点 else s-rchild = p； // 链接右孩子结点 按给定的表达式建相应二叉树 由原表达式建树 例如：已知表达式 (a+b)×c – d/e 将表达式存成二叉树，二叉树的前序序列是前缀表达式，中序序列是中缀表达式, 后序序列就是后缀表达式。 分析原表达式和二叉树的关系: × a+b (a+