二叉树面试题（叶子，深度，复制）

爱被打了一巴掌 2022-06-02 04:28 199阅读 0赞

**1，计算叶子结点的个数**  
**2，计算树的深度**  
**3，如何copy一个二叉树**

![format_png][]  
\#\#\#\#求叶子结点的个数

//给出如下二叉树

![format_png 1][]

（1）思路：输出叶子结点比较简单，用任何一种遍历算法都可以，凡是左，右指针域都为空的结点，就是叶子结点，将其统计并且打印出来即可；

（2）具体实现：

（1.1）通过定义全局变量实现

#include<stdio.h>
    #include<string.h>
    #include<stdlib.h>
    
    typedef struct BinTreeNode
    {
    	int data;
    	struct BinTreeNode *lchild,*rchild;
    }BiTNode,*BiTree;//定义二叉树结构
    
    
    //求叶子结点的个数：
    int g_count=0;//用于找到叶子结点计数
    void CountLeft(BiTNode* root)
    {
    	if(NULL!=root)//如果树不为空
    	{
    		if(root->lchild==NULL&&root->rchild ==NULL)//找叶子结点
    		{
    			g_count++;//找到计数器加1
    		}
    	CountLeft(root->lchild );//递归遍历左子树，直到叶子结点处
    	CountLeft(root->rchild );//递归遍历右子树，直到叶子结点处
      }
    }
    
    int main()
    {
        BiTNode b1,b2,b3,b4,b5;
    	memset(&b1,0,sizeof(BiTNode));
        memset(&b2,0,sizeof(BiTNode));
        memset(&b3,0,sizeof(BiTNode));
        memset(&b4,0,sizeof(BiTNode));
    	memset(&b5,0,sizeof(BiTNode));
    
    	b1.data=1;//给每一个结点赋值
    	b2.data=2;
    	b3.data=3;
    	b4.data=4;
    	b5.data=5;
    
    	b1.lchild =&b2;//构建结点之间的关系
    	b1.rchild =&b3;
    	b2.lchild =&b4;
    	b3.lchild =&b5;
    	
    	CountLeft(&b1);
    	printf("叶子结点的个数为：%d",g_count);
    	printf("\n");
    return 0;
    }

（1.2）运行结果：  
![format_png 2][]

（1.3）问题：如果所有的树都采用定义全局变量的方法去求叶子结点的个数，未免也糟糕了，那么，接下来，我们来使用另一种方式，不设置全局变量，给函数多传一个参数：

（2.1）传参实现：

#include<stdio.h>
    #include<string.h>
    #include<stdlib.h>
    
    typedef struct BinTreeNode
    {
    	int data;
    	struct BinTreeNode *lchild,*rchild;
    }BiTNode,*BiTree;
    
    
    //求叶子结点的个数：
    //采用前序遍历算法
    void CountLeft(BiTNode* root,int *g_count)//多设置一个参数
    {
    	if(NULL!=root)
    	{
    		if(root->lchild==NULL&&root->rchild ==NULL)
    		{
    			(*g_count)++;
    		}
    	CountLeft(root->lchild ,g_count);
    	CountLeft(root->rchild ,g_count);
      }
    }
    
    int main()
    {
    	int g_count=0;
    	BiTNode b1,b2,b3,b4,b5;
    	memset(&b1,0,sizeof(BiTNode));
        memset(&b2,0,sizeof(BiTNode));
        memset(&b3,0,sizeof(BiTNode));
        memset(&b4,0,sizeof(BiTNode));
    	memset(&b5,0,sizeof(BiTNode));
    
    	b1.data=1;
    	b2.data=2;
    	b3.data=3;
    	b4.data=4;
    	b5.data=5;
    
    	b1.lchild =&b2;
    	b1.rchild =&b3;
    	b2.lchild =&b4;
    	b3.lchild =&b5;
    	
    	CountLeft(&b1,&g_count);
    	printf("叶子结点的个数为：%d",g_count);
    	printf("\n");
        return 0;
    }

（2.2）实验结果：  
![format_png 3][]

（3）既然上面说了，求叶子结点的个数，采用任何一种遍历算法都可以，那么，我们能否着这样写代码呢？

//采用中序遍历算法
    void CountLeft(BiTNode* root,int *g_count)
    {
    	if(NULL!=root)
    	{
    		CountLeft(root->lchild ,g_count);
    		if(root->lchild==NULL&&root->rchild ==NULL)
    		{
    			(*g_count)++;
    		}
    		CountLeft(root->rchild ,g_count);
      }
    }

//采用后序遍历算法
    void CountLeft(BiTNode* root,int *g_count)
    {
    	if(NULL!=root)
    	{
    		CountLeft(root->lchild ,g_count);
    		CountLeft(root->rchild ,g_count);
    	
    		if(root->lchild==NULL&&root->rchild ==NULL)
    		{
    			(*g_count)++;
    		}
      }
    }

（3.2）实验结果：  
![format_png 4][]

这就证明了，不论是采用先序，中序，还是后序遍历算法，对叶子结点的计算并无影响。这是因为在遍历二叉树时，每个结点都回被访问三次，详情请见：  
http://blog.csdn.net/dai\_wen/article/details/78955411

![format_png 5][]

\#\#\#\#二叉树的深度

//对如下的树，求树的深度：

![format_png 6][]

1，思路：

要计算二叉树的深度，需要分别计算左右子树的深度，然后再取两者深度较大的那一个即可；

2，实现程序：

#include<stdio.h>
    #include<string.h>
    #include<stdlib.h>
    
    typedef struct BinTreeNode//二叉树的构建
    {
    	int data;
    	struct BinTreeNode *lchild,*rchild;
    }BiTNode,*BiTree;
    
    
    int  Depth(BiTNode* root)
    {//   二叉树的深度， 左子树的深度，右子树的深度
    	int depthval=0,depthleft=0,depthright=0;
    
    	if(root==NULL)//如果树为空
    	{
    		depthval=0;//深度为0
    		return depthval;
    	}
    
    		depthleft=Depth(root->lchild );//左子树深度
    		depthright=Depth(root->rchild );//右子树深度
    	depthval=1+((depthleft>depthright)?depthleft:depthright);//取左右子树较大值
    		return depthval;
    }
    
    int main()
    {
    	int g_count=0;
    	BiTNode b1,b2,b3,b4,b5;
    	memset(&b1,0,sizeof(BiTNode));
        memset(&b2,0,sizeof(BiTNode));
        memset(&b3,0,sizeof(BiTNode));
        memset(&b4,0,sizeof(BiTNode));
    	memset(&b5,0,sizeof(BiTNode));
    
    	b1.data=1;
    	b2.data=2;
    	b3.data=3;
    	b4.data=4;
    	b5.data=5;
    
    	b1.lchild =&b2;
    	b1.rchild =&b3;
    	b2.lchild =&b4;
    	b3.lchild =&b5;
    
    	printf("树的深度为：%d\n",Depth(&b1) );
    	printf("\n");
        return 0;
    }

（3）实验结果：  
![format_png 7][]

![format_png 8][]

\#\#\#\#复制一颗已有的二叉树

![format_png 9][]  
（1）思路：复制一颗二叉树，先复制其根结点，再复制左子树，最后复制右子树，从而复制完成；

（2）程序实现：

#include<stdio.h>
    #include<string.h>
    #include<stdlib.h>
    
    typedef struct BinTreeNode
    {
    	int data;
    	struct BinTreeNode *lchild,*rchild;
    }BiTNode,*BiTree;
    
    //1,前序遍历，用来测试，树是否已经复制成功
    void PreOrder(BiTNode *root)
    {
    	if(root)
    	{
    		printf("%d ",root->data );
    	    PreOrder(root->lchild );
    		PreOrder(root->rchild );
    	}
    }
    
    //复制过程
    BiTNode* copyBinTree(BiTNode *root)
    {
    	
       BiTNode *newnode=NULL,*newlptr=NULL,*newrptr=NULL;
    	
       if(NULL==root)//判断树是否为空
    	{
    		return  NULL;
    	}
       if(root-> lchild!=NULL)//如果左子树不为空
       {
    	   newlptr=copyBinTree(root->lchild );
       }
       else//左子树为空
       {
    	   newlptr=NULL;
       }
    if(root->rchild!=NULL)//如果右子树不为空
    {
    	newrptr=copyBinTree(root->rchild );
    }
    
    else//右子树为空
    {
    	newrptr=NULL;
    }
    
    newnode=(BiTNode*)malloc(sizeof(BiTNode));
    newnode->lchild =newlptr;
    newnode->rchild =newrptr;
    newnode->data=root->data;
    
    return newnode;
    }
    
    
    
    int main()
    {
    	BiTNode* pNewnode;
    	int g_count=0;
    	BiTNode b1,b2,b3,b4,b5;
    	memset(&b1,0,sizeof(BiTNode));
        memset(&b2,0,sizeof(BiTNode));
        memset(&b3,0,sizeof(BiTNode));
        memset(&b4,0,sizeof(BiTNode));
    	memset(&b5,0,sizeof(BiTNode));
    
    	b1.data=1;
    	b2.data=2;
    	b3.data=3;
    	b4.data=4;
    	b5.data=5;
    
    	b1.lchild =&b2;
    	b1.rchild =&b3;
    	b2.lchild =&b4;
    	b3.lchild =&b5;
    	
    	pNewnode=copyBinTree(&b1);
    
    	printf("新二叉树前序遍历：\n");
    	PreOrder(pNewnode);
    	printf("\n");
    	
        return 0;
    }

（3）实现结果：  
![format_png 10][]

\#\#\#\#总结：  
众所周知，软将行业，招聘时数据结构是重点，那么这里的一些只是数据结构中的九牛一毛，持续更新中。。。。。

[format_png]: /images/20220602/dd0c4b78e077439baf66fd646156ffdb.png
[format_png 1]: /images/20220602/054bb6dfb9c340d5b41071080057e1af.png
[format_png 2]: /images/20220602/c4c8aaa211994f96bbb7cf91238e496e.png
[format_png 3]: /images/20220602/0b0cc3c86c9f48ffa23fe59ae737c71f.png
[format_png 4]: /images/20220602/b6db7caacf834f54906567202a07b2ba.png
[format_png 5]: /images/20220602/be5d2c127db84814a5d85431783a53bd.png
[format_png 6]: /images/20220602/b74eba47f5af436ab644af2418f63b71.png
[format_png 7]: /images/20220602/e50883712112485d9a416558b78a6888.png
[format_png 8]: /images/20220602/3f50840b87c74e1d81ce0fc1f990332d.png
[format_png 9]: /images/20220602/0f75cf1acf3f4756b7ddc25d3c04a723.png
[format_png 10]: /images/20220602/d922fc62517a4ca4bf1cb7c4f5501f90.png