创建二叉树之C语言实现

朴灿烈づ我的快乐病毒、 2022-01-11 04:09 258阅读 0赞

### 按照指定输入方式创建二叉树 ###

*   *  输入方式
     *  创建代码
     *  逐步分析
     *  原理分析
     *  难点分析

## 输入方式 ##

输入方式： A ( B ( D ( , G ) ) , C ( E , F ) )

A为本节点，括号里的两部分由逗号隔开，分别是左右节点。如果没有则直接打逗号。

那么上图对应的二叉树就是：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzOTQ4NTgz_size_16_color_FFFFFF_t_70]

## 创建代码 ##

typedef enum Dealing
    {
        
       DealingLeft,DealingRight
    } Dealing;
    
    
    void CreatBTNode(BTNode* &b, char *str) 
    {
        											
       	
       //一个保存亲节点的栈 
       BTNode* St[MaxSize];
       int top = -1;
       
       //其他的东些
       BTNode* p; 
       int j = 0; //用来循环处理字符串的 
       Dealing k;
       char ch;
       
       //建立的时候二叉链初始为空
       b = NULL;
       //读入第一个字符，按理说就应该是根节点的值
       ch = str[j];
       while (ch!=0)
       {
        
       	switch(ch)
       	{
        
       		case '(' :
       			//可能有左孩子节点 进栈 
       			top++;
       			St[top] = p;      //将亲节点保存在栈里然后对子节点开始操作 
       			k = DealingLeft;
       			break;
       			
       		case ')' :
       			//处理完了一层 后退出栈 
       			top--;
       			break;
       			
       		case ',' :
       			//后面为右孩子节点 
       			k = DealingRight;
       			break;
       		
       		default :
       			//遇到节点值 
       			p = (BTNode*)malloc(sizeof(BTNode));
       			p->data = ch;
       			p->lchild = p->rchild = NULL;
       			
       			if(b==NULL) //p为二叉树的根节点 
       			{
        
       				b = p;
       			}
       			else   //已建立二叉树根节点 
       			{
        
       				switch(k)
       				{
        
       					case DealingLeft :
       						St[top]->lchild=p;
       						break;
       					case DealingRight :
       						St[top]->rchild=p;
       						break;
       							
       				}
       			}
       	}
       	
       	//继续扫描str 
       	j++;
       	ch = str[j];
       	 
       } 	
    }

我们直接来看以输入 A ( B ( D ( , G ) ) , C ( E , F ) ) 为例，程序是怎么运行的吧。  
毕竟那么一大堆代码说理论也是说不清的…

## 逐步分析 ##

A ( B ( D ( , G ) ) , C ( E , F ) ) 这个字符串在读入每个字符的时候会做如下操作：  
这个过程建议读者拿着笔跟着画一下。  
为了记录亲节点，我们需要一个栈。

开始：  
`A` ：建立根节点，赋值  
`(` ：表示进入子树，先左子树，所以下个字母放左边，根节点是A（入栈）  
`B`：开辟空间，赋值，放到A节点左边  
`(` ：表示进入子树，先左子树，所以下个字母放左边，根节点是B（入栈）  
`D` ：开辟空间，赋值，放到B节点左边  
`(`：表示进入子树，先左子树，所以下个字母放左边，根节点是D（入栈）  
`,` ：表示下一个是右子树，所以下个字母放右边  
`G` ：开辟空间，赋值，放到D节点右边  
`)`：表示D节点的子树已经录入完毕，修改当前的根节点为B（出栈）  
`)`：表示B节点的子树已经录入完毕，修改当前的根节点为A（出栈）  
`,`：表示下一个是右子树，所以下个字母放右边  
`C` ：开辟空间，赋值，放到A节点右边  
`(` ：表示进入子树，先左子树，所以下个字母放左边，根节点是C（入栈）  
`E` ：开辟空间，赋值，放到C节点左边  
`,`：表示下一个是右子树，所以下个字母放右边  
`F`：开辟空间，赋值，放到C节点右边  
`)`：表示C节点的子树已经录入完毕，修改当前的根节点为A（出栈）  
`)`：表示A节点的子树已经录入完毕，整棵树全部录入完毕。（出栈，栈空）

## 原理分析 ##

我们可以发现，上面的那么多步可以被归为以下这几类：  
`字母且是根节点`：直接开辟空间，并把传入函数的指针指向这里。  
`字母`：开辟空间，赋值，然后建立连接关系。  
`（`：表示下一个字母的连接关系是左  
`，`：表示下一个字母的连接关系是右  
`）`：表示对应的根节点左右子树已经处理完了。

现在你去回看代码里的switch再理解一下。

所以说我们最终的switch处理机制是这样的：  
`字母`：开辟空间，赋值，若是根节点，啥不干。若不是，建立连接关系。  
`（`：表示下一个字母的连接关系是左，亲节点入栈。  
`，`：表示下一个字母的连接关系是右  
`）`：表示对应的根节点左右子树已经处理完了。亲节点出栈。

## 难点分析 ##

但是还是有几大难点：  
1.字母判断字母处理用哪个方式？  
答：

if(b==NULL)
    	{
        
    		b = p;
    	}
    	else   //已建立二叉树根节点 
    	。。。。。

若是刚开始，则传入的指针是空的，把第一个开辟的空间给它作为根节点就对了，这样以后的都会去执行else里的建立连接关系的操作了。  
2.建立连接关系的时候怎么判断是连左子树还是右子树？

答：我们刚才在遇到`（`或者`,`的时候，就会知道下一个会是处理左子树还是右子树。这里借助一个变量Dealing k = dealingleft 或者 dealingright来传递信息，如果遇到`(`就修改k为dealingleft，遇到`,`就修改为dealingright，然后再在录入字母的时候判断一下现在k是什么状态，从而选择相应的处理方法。

这里其实也不一定要声明一个Dealing类的变量，只是方便理解，如果懒的话可以直接int flag，flag是0 就处理左边 flag是1 就处理右边。

3.建立连接关系的时候怎么知道亲节点是哪个呢？

答：用栈来存呐！  
每次当你遇到`（`的时候，就把上一个节点入栈（此时p就指向的上一个节点），然后用stack\[top\]来表示亲节点就可以了。遇到`）`就出栈就对了。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzOTQ4NTgz_size_16_color_FFFFFF_t_70]: /images/20220111/b4697424cdb54cbaa3993ab2a8463b0a.png