C语言创建二叉树及对二叉树的操作

雨点打透心脏的1/2处 2022-12-17 07:01 175阅读 0赞

代码都是书上的。  
需要注意的是怎么输入。  
![在这里插入图片描述][20201022110755441.png_pic_center]  
第一行 为自己输入的数据，在创建的二叉树中数据域为char型，故空格和enter键也会被存入二叉树数据中。‘\#’号总比二叉树数据结点多一个，不然一直在输入，无法进入输出。输出是中序遍历打印的。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDAyNTQ0_size_16_color_FFFFFF_t_70_pic_center]  
根据上面的输入数据可以画出自己创建的二叉树（上图）。这是草稿纸上的操作，代码结果只输出中序遍历结果。

完整代码如下：

#include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    typedef struct BiTNode
    { 
    	char data;//结点的数据域 
    	struct BiTNode *lchild,*rchild;//左右孩子指针 
    }BiTNode,*BiTree;
    
    void CreateTree(BiTree &T)//创建二叉树，这里是先序遍历的顺序建立的二叉链表 递归形式 
    { 
    	char ch,trmp;
    	scanf("%c",&ch);//输入链表数据 
    	if(ch == '#')//如果出现输入的是#,终止递归。终止递归条件 
    		T = NULL;
    	else
    	{ 
    		T = (BiTNode*)malloc(sizeof(BiTNode));//申请一个根结点 
    		T->data = ch;//对根结点进行赋值 
    		CreateTree(T->lchild);//递归创建左子树 
    		CreateTree(T->rchild);//递归创建右子树 
    	}
    }
    
    bool TreeEmpty(BiTree T)//判断二叉树是否为空 
    { 
    	if(T == NULL)//bool类型，如果二叉树为空，返回true,否则返回false 
    		return true;
    	return false;
    }
    
    void InOrderTraverse(BiTree T)//打印二叉树 ，中序遍历二叉树的递归算法 
    { 
    	if(T)//递归终止条件是T为NULL 
    	{ 
    		InOrderTraverse(T->lchild);//中序遍历左子树 
    		printf("%c ",T->data);//输出打印根结点 
    		InOrderTraverse(T->rchild);//中序遍历右子树 
    	}
    }
    
    void CopyTree(BiTree T,BiTree &NewT)//复制一颗和T完全相同的二叉树 
    { 
    	if(T == NULL)//递归终止条件 
    	{ 
    		NewT = NULL;
    		return ;
    	}
    	else
    	{ 
    		NewT = (BiTNode*)malloc(sizeof(BiTNode));//申请一个根结点 
    		NewT->data = T->data;//复制根结点 
    		CopyTree(T->lchild,NewT->lchild);//递归复制左子树 
    		CopyTree(T->rchild,NewT->rchild);//递归复制右子树 
    	}
    }
    
    int Depth(BiTree T)//计算二叉树T的深度 
    { 
    	int m = 0,
    		n = 0;//定义两个变量 
    	if(TreeEmpty(T))//递归终止条件 
    		return 0;
    	else
    	{ 
    		m = Depth(T->lchild);//递归计算左子树的深度记为m 
    		n = Depth(T->rchild);//递归计算右子树的深度记为n 
    		if(m>n)//二叉树的深度为m与n的较大者加1 
    			return m+1;
    		return n+1;
    	}
    }
    
    int NodeCount(BiTree T)//统计二叉树T中的结点的个数 
    { 
    	if(T == NULL)//递归终止条件 
    		return 0;
    	else//结点个数为左子树的结点个数+右子树的结点个数 
    		return NodeCount(T->lchild)+NodeCount(T->rchild)+1;
    }
    
    int main()
    { 
    	BiTree T;//创建一个空二叉树 
    	CreateTree(T);// 创建二叉树 
    	InOrderTraverse(T);//打印二叉树 中序遍历
    	printf("\n");
    	BiTree NewT;//创建一个新二叉树 
    	CopyTree(T,NewT);//复制二叉树 
    	InOrderTraverse(NewT);
    	printf("\n");
    	printf("%d\n",Depth(T));//二叉树T的深度 
    	printf("%d\n",NodeCount(T));//二叉树的结点个数 
    	return 0;
    }

（完）

[20201022110755441.png_pic_center]: /images/20221123/c492673298e9431bba34053432fa8bcf.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDAyNTQ0_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/820fe4ac8d3b4ab29bbce8e286365aa4.png