数据结构6-树b解读.ppt

6.3 遍历二叉树和线索二叉树 6.3.1 遍历二叉树 6.3.2 建立(生成)二叉树 6.3.3 线索二叉树 6.3.4 表达式二叉树 表达式二叉树T = (第一操作数) (运算符) (第二操作数) 其中：第一操作数、第二操作数也是表达式二叉树， 分别为表达式二叉树T的左子树和右子树 例 表达式： A + B * C - D /（E - F） 6.3.5 中序遍历序列和前(或后)序序列确定唯一棵二叉树 6.3.5 中序遍历序列和前(或后)序序列确定唯一棵二叉树 6.3.5 中序遍历序列和前(或后)序序列确定唯一棵二叉树 递归算法 1.前序遍历以root为根指针的二叉树 preorder(struct nodeb *root) { if (root) //为非空二叉树 { printf(%c,root-data)； //访问根结点 preorder(root-lchild)； //递归遍历左子树 preorder(root-rchild)； //递归遍历右子树 } } 执行preorder(struct nodeb *t)； 执行preorder(struct nodeb *t)； 执行preorder(struct nodeb *t)； 执行preorder(struct nodeb *t)； 执行preorder(struct nodeb *t)； 执行preorder(struct nodeb *t)； 执行preorder(struct nodeb *t)； 2.中序遍历以root为根指针的二叉树 3.后序遍历以root为根指针的二叉树 4.中序遍历非递归算法 preorder(struct nodeb *t) //t为根指针 { struct bnode *st[maxleng+1]；//定义地址栈st[0..maxleng] int top=0； //置空栈 do { while(t) //为非空二叉树 { if (top==maxleng) exit(overflow)；//栈已满,退出 st[++top]=t； //根地址进栈 t=t-lchild； //t移向左子树 } if (top) //为非空栈 { t=st[top--]； //弹出根地址 printf(%c,t-data)； //访问根结点 t=t-rchild； //遍历右子树 } } while(top||t)； } //父结点未访问，或右子树未遍历 6.3.7 遍历二叉树的应用 例. 求二叉树中结点的个数 creat_tree(struct bnode **root) //生成二叉树 { ........... } preorder(struct nodeb *root,int *n)//求二叉树中结点的个数 { if (root) { (*n)++； //计数 preorder(root-lchild,n)； //递归遍历左子树 preorder(root-rchild,n)； //递归遍历右子树 } } main() { int n=0； //n为计数器,假定二叉树已生成 preorder(root,n)； //root为指针,执行preorder(root,n) printf(%d,n)； //输出n } 6.4 树和森林 6.4.1 树的存储结构 1.双亲表示法/数组表示法/顺序表示法 2.孩子表示法/链接表表示法 (1)固定大小的结点格式，(设树T的度为k,结点数为n) 2.孩子表示法/链接表表示法 (2)非固定大小的结点格式 3.孩子兄弟表示法/二叉树表示法/二叉链表 3.孩子兄弟表示法/二叉树表示法/二叉链表 4.孩子链表表示法/单链表表示法 5.带双亲的孩子链表表示法 6.4.2 树与二叉树的转换 1.树 二叉树 1.树 二叉树 2.森林 二叉树 2.森林 二叉树 3. 二叉树 树 3. 二叉树 森林 6.4.3 树和森林