首页 > 代码库 > 二叉树和广义表的转换
二叉树和广义表的转换
1 //广义表转二叉树: 2 设置一个标记变量k,初始值为-1; 3 设置一个标记结点p; 4 循环遍历广义表的字符串str; 5 如果str[i]是左括号: 6 则设置k为0; 7 把p压入栈中。 8 否则如果str[i]是逗号: 9 则设置k为1。 10 否则如果str[i]是右括号: 11 则栈顶元素出栈。 12 否则如果str[i]是一个字母,用结点temp来存储: 13 如果k为-1: 14 则把temp作为根结点并压入栈中。 15 如果k为0: 16 如果此时栈顶结点是p,则先出栈; 17 然后将temp作为栈顶结点的左孩子; 18 再把temp压入栈中。 19 如果k为1: 20 栈顶元素出栈; 21 将temp作为栈顶结点的右孩子; 22 再把temp压入栈中。 23 24 25 struct Node{ 26 char data; 27 Node *lchild=NULL,*rchild=NULL; 28 }; 29 30 typedef struct Node node; 31 32 node* build(const string &str){ 33 node *root = NULL; 34 unsigned long max_length=str.length(); 35 int k=-1; 36 int top=-1; 37 node *p; 38 node *temp; 39 node* Stack[max_length]; 40 for(int i=0;i<max_length;i++){ 41 if(str[i]==‘(‘){ 42 k=0; 43 top++; 44 Stack[top]=p; 45 } 46 else if(str[i]==‘,‘){ 47 k=1; 48 } 49 else if(str[i]==‘)‘){ 50 top--; 51 } 52 else if(isalpha(str[i])){ 53 temp=new node; 54 temp->data=http://www.mamicode.com/str[i]; 55 if(k==-1){ 56 root=temp; 57 top++; 58 Stack[top]=temp; 59 } 60 else if(k==0){ 61 if(Stack[top]==p){ 62 top--; 63 } 64 Stack[top]->lchild=temp; 65 top++; 66 Stack[top]=temp; 67 } 68 else if(k==1){ 69 top--; 70 Stack[top]->rchild=temp; 71 top++; 72 Stack[top]=temp; 73 } 74 } 75 } 76 return root; 77 } 78 79 80 81 82 //二叉树转广义表 83 输出结点存储的值; 84 如果左孩子不为空: 85 输出"("; 86 递归输出左子树; 87 如果右子树为空: 88 输出",)" 。 89 如果右孩子不为空: 90 如果左孩子为空: 91 输出"("。 92 输出","; 93 递归输出右子树; 94 输出")"。 95 96 97 void print_list(node* cur_node){ 98 cout<<cur_node->data; 99 if(cur_node->lchild!=NULL){ 100 cout<<"("; 101 print_list(cur_node->lchild); 102 if(cur_node->rchild==NULL){ 103 cout<<",)"; 104 } 105 } 106 if(cur_node->rchild!=NULL){ 107 if(cur_node->lchild==NULL){ 108 cout<<"("; 109 } 110 cout<<","; 111 print_list(cur_node->rchild); 112 cout<<")"; 113 } 114 }
二叉树和广义表的转换
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。