南开大学 的数据结构Week10 树的遍历.pdf

二叉树遍历算法的应用 “遍历”是二叉树最重要的基本操作，是各种其它操 作的基础，二叉树的许多其它操作都可以通过遍历来实 现。如建立二叉树的存储结构、求二叉树的结点数、求 二叉树的深度等。 1 二叉树的二叉链表创建 ⑴ 按满二叉树方式建立 在此补充按满二叉树的方式对结点进行 编号建立链式二叉树。对每个结点，输入i、ch。 i ：结点编号，按从小到大的顺序输入 ch ：结点内容，假设是字符 在建立过程中借助一个一维数组S[n] ，编号为i 的 结点保存在S[i]中。 #define MAX_NODE 50 typedef struct BTNode { char data ; struct BTNode *Lchild , *Rchild ; }BTNode ; BTNode *Create_BTree(void) /* 建立链式二叉树，返回指向根结点的指针变量 */ { BTNode *T , *p , *s[MAX_NODE] ; char ch ; int i , j ; while (1) { scanf(“%d”, i) ; if (i 0) break ; /* 以编号0作为输入结束 */ else { ch=getchar() ; p=(BTNode *)malloc(sizeof(BTNode)) ; p–data=ch ; p–Lchild=p–Rchild=NULL ; s[i]=p ; if (i 1) T=p ; else { j=i/2 ; /* j是i 的双亲结点编号 */ if (i%2 0) s[j]-Lchild=p ; else s[j]-Rchild=p ; } } } return(T) ; } ⑵ 按先序遍历方式建立 对一棵二叉树进行“扩充” ，就可以得到二叉树所扩充的二叉 树。有两棵二叉树T 及其扩充的二叉树T 。 1 2 A A B C B C ? D E F D E F ? ? ? G ? ? G