首页 > 代码库 > 二叉树和广义表的转换

二叉树和广义表的转换

  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 }

 

二叉树和广义表的转换