pe contd) 4.二又树的建立(2)根据广义表字符串建立二又树 广义表字符串输入的形式是 A(B(,D),C(E,) 这是个递归输入方式,因此这样建立二叉树也 是个递归的过程。这里给出非递归的算法。 算法思想: (1)从左向右扫描字符串,遇到字母就建立结点; (2)遇到(表示前面字母有孩子,要将前面字母 的结点入栈,以便将左右孩子与双亲链接起来。 (3)(后面的字母是左孩子,逗号后面的字母是 右孩子,遇到)表示以栈顶结点为根的子树建立 完毕,出栈
12 广义表字符串输入的形式是： A(B(,D),C(E,)) 这是个递归输入方式，因此这样建立二叉树也 是个递归的过程。这里给出非递归的算法。 算法思想： (1) 从左向右扫描字符串，遇到字母就建立结点； (2) 遇到(表示前面字母有孩子，要将前面字母 的结点入栈，以便将左右孩子与双亲链接起来。 (3) (后面的字母是左孩子，逗号后面的字母是 右孩子，遇到)表示以栈顶结点为根的子树建立 完毕，出栈。 二叉树(cont’d) 4.二叉树的建立 (2) 根据广义表字符串建立二叉树 A B C D E
contd) 4.二又树的建立(2)根据广义表字符串建立二又树 default:∥常规字母,直接创建结点 t=(TREENODEPTR)malloc(sizeof(TREENODE)) t→)data=* t-丶 Child=t- rchild=NUL;∥/默认情况下,左右孩子为空 n ∥第一次创建的结点是整个树的根 i *root=t; n++:) else itg)s[top]→> child=t;∥栈顶结点的左孩子是t else s[]- rchild=t;∥栈顶结点的右孩子是t J//switch i//for
13 #define N 50 void creattree(BTREE *root, char *str) //假设结点数据是字母 {TREENODEPTR t, s[N]; char *p; int top=0,n=0,tag; //s是栈，top是栈顶下标 p=str; for(;*p;p++) {switch(*p) {case '(' : top++; s[top]=t; tag=1;break; //将前面结点入栈，准备链接左孩子 case ')' :top--;break; //栈顶结点的子树创建完毕，出栈 case ',' :tag=0;break; //准备链接右孩子 二叉树(cont’d) 4.二叉树的建立 (2)根据广义表字符串建立二叉树 default: //常规字母，直接创建结点 t=(TREENODEPTR)malloc(sizeof(TREENODE)); t→data=*p; t→lchild=t→rchild=NULL; //默认情况下,左右孩子为空 if(n==0) //第一次创建的结点是整个树的根 { *root=t; n++; } else { if(tag) s[top]→lchild=t; //栈顶结点的左孩子是t else s[top]→rchild=t; //栈顶结点的右孩子是t } }//switch }//for } A B C D E
6.3场二见 1.二又树的遍历方式 (1)先序遍历(DLR,先输出根,再遍历左子树,最后 遍历右子树 (2)中序遍历(LDR),先遍历左子树,再输出根,最后 遍历右子树 3后序遍历(LRD),先遍历左子树,再遍历右子树, 最后输出根 DLR:ABDCE LDR: BDAE C LRD: BECA
14 6.3 遍历二叉树 1. 二叉树的遍历方式 (1) 先序遍历(DLR)，先输出根，再遍历左子树，最后 遍历右子树 (2) 中序遍历(LDR)，先遍历左子树，再输出根，最后 遍历右子树 (3) 后序遍历(LRD)，先遍历左子树，再遍历右子树， 最后输出根 A B C D E DLR： LDR： LRD： AB D C E BD A E C D B E C A
2.二又树的遍历算法(1)中序遍历 void inorder(btree root) if(root!=NULL) 递归算法 f inorder(root ->lchild); printf("%d", root->data); inorder(root-rchild);
15 遍历二叉树(cont’d) 2. 二叉树的遍历算法 (1)中序遍历 void inorder(BTREE root) { if(root!=NULL) { inorder(root→lchild); printf("%d",root→data); inorder(root→rchild); } } 递归算法
2.二又树的遍历算法(2)先序遍历 void preorder(btree root if(root!=NULL) 递归算法 printf(""%d", root->data); preorder(root-Ichild) preorder(root ->rchild)
16 遍历二叉树(cont’d) 2. 二叉树的遍历算法 (2)先序遍历 void preorder(BTREE root) { if(root!=NULL) { printf("%d",root→data); preorder(root→lchild); preorder(root→rchild); } } 递归算法