精华内容
下载资源
问答
  • 求二叉树的宽度

    2020-03-16 10:24:13
    求二叉树的宽度 【问题描述】 以二叉链表为存储结构,编写算法求二叉树的宽度(具有结点数最多的那一层上的节点个数)。 【输入形式】两行,第一行是扩展二叉树的前序遍历序列。 【输出形式】二叉树的宽度。 【样例...

    求二叉树的宽度

    【问题描述】

    以二叉链表为存储结构,编写算法求二叉树的宽度(具有结点数最多的那一层上的节点个数)。

    【输入形式】两行,第一行是扩展二叉树的前序遍历序列。

    【输出形式】二叉树的宽度。

    【样例输入】AB#D##C##

    【样例输出】 2

    #include<iostream>
    #include<queue>
    #include<deque>
    using namespace std;
    template<typename DataType>
    
    struct BiNode
    {
    	DataType data;
    	BiNode<DataType> *lchild,*rchild,*next;
    };
    
    template <typename DataType>
    class BiTree
    {
    	public:
    		BiTree()
    		{
    			root=Creat();
    		}
    		int width();
    		queue<BiNode<DataType>*> d;
    		
    	private:
    		BiNode<DataType> *Creat();
    		BiNode<DataType> *root;
    };
    
    
    
    template<typename DataType>
    BiNode<DataType> *BiTree<DataType>::Creat()
    {
    	BiNode<DataType> *bt;
    	char ch;
    	cin>>ch;
    	if(ch=='#')  bt=NULL;
    	else
    	{
    		bt=new BiNode<DataType>;
    		bt->data=ch;
    		bt->lchild=Creat();
    		bt->rchild=Creat();
    	}
    	return bt;
    }
    
    
    template<typename DataType>
    int BiTree<DataType>::width()
    {
    	
        if(root == NULL)
            return 0;
    
        int maxWidth = 0;
        deque<BiNode<DataType>*> d;
        d.push_back(root);
    
        while(true)
        {
            int len = d.size();
            if(len == 0)
                break;
            while(len > 0)
            {
                BiNode<DataType> *temp = d.front();
                d.pop_front();
                len--;
                if(temp->lchild)
                    d.push_back(temp->lchild);
                if(temp->rchild)
                    d.push_back(temp->rchild);
            }
            maxWidth = maxWidth > d.size() ? maxWidth : d.size();
    
        }
        return maxWidth;
    }
    
    
    int main()
    {
    	BiTree<char> t;
    	cout<<t.width()<<endl;
    }
    
    
    展开全文
  • 二叉树系列五:求二叉树的宽度

    千次阅读 2017-10-19 21:47:02
    求二叉树的宽度可以依据与二叉树的层次遍历,我们知道,二叉树的层次遍历借助于deque实现,每次打印当前结点后将其左子树右子树入队,此时队列中既包含当前层的结点,也包含下一层的结点,若我们将当前层的结点全部...

      二叉树的宽度是指二叉树各层结点个数的最大值。求二叉树的宽度可以依据与二叉树的层次遍历,我们知道,二叉树的层次遍历借助于deque实现,每次打印当前结点后将其左子树右子树入队,此时队列中既包含当前层的结点,也包含下一层的结点,若我们将当前层的结点全部出队,剩余的就是下一层的结点个数。所以,我们可以使用maxWidth来表示最大宽度,若下一层的结点个数大于maxWidth,则更新maxWidth,最终队列为空,得到的maxWidth即为二叉树的宽度。

    以下是C++实现的源代码:

    //求二叉树的宽度
    int WidthOfBiTree(BiTree root)
    {
        if(root == NULL)
            return 0;
    
        int maxWidth = 0;
        deque<BiTree> d;
        d.push_back(root);
    
        while(true)
        {
            int len = d.size();
            if(len == 0)
                break;
            while(len > 0)
            {
                BiTree temp = d.front();
                d.pop_front();
                len--;
                if(temp->Lchild)
                    d.push_back(temp->Lchild);
                if(temp->Rchild)
                    d.push_back(temp->Rchild);
            }
            maxWidth = maxWidth > d.size() ? maxWidth : d.size();
    
        }
        return maxWidth;
    }
    展开全文
  • 华为练习 求二叉树的宽度和深度

    千次阅读 2014-05-11 13:37:34
    求二叉树的宽度和深度 给定一个二叉树,获取该二叉树的宽度和深度。

    求二叉树的宽度和深度
    给定一个二叉树,获取该二叉树的宽度和深度。

    例如输入
    a
    / \
    b c
    / \ / \
    d e f g

    返回3.
    详细描述:

    接口说明
    原型:
    int GetBiNodeInfo(BiNode &head, unsigned int *pulWidth, unsigned int *pulHeight)
    输入参数:
    head 需要获取深度的二叉树头结点
    输出参数(指针指向的内存区域保证有效):
    pulWidth 宽度
    pulHeight 高度
    返回值:
    0 成功
    1 失败或其他异常


    int DEEP;//深度,初始节点深度为0.则计算完了,将deep加一
    int level[10010];//假定最高10010层。太大了就无法保存了。
    
    //深度优先遍历
    void DFS(int d,BiNode *n){//d为所要遍历的节点的层数
    	if(n != 0){
    		if(d > DEEP)
    			DEEP = d;
    		level[d] ++;
    		DFS(d+1,n->left);
    		DFS(d+1,n->right);
    	}
    }
    /*
    Description  
             给定一个二叉树,获取该二叉树的宽度深度。
    Prototype
             int GetBiNodeInfo(BiNode &head, unsigned int *pulWidth, unsigned int *pulHeight)
    Input Param 
             head   需要获取深度的二叉树头结点
    Output Param 
             pulWidth   宽度
             pulHeight  高度
    Return Value
             0          成功
             1          失败或其他异常
    */
    int GetBiNodeInfo(BiNode &head, unsigned int *pulWidth, unsigned int *pulHeight)
    {
    	/*在这里实现功能*/
    	
    	for(int i = 0; i < 10010;i++)
    		level[i] = 0;
    	DEEP = 0;
    	DFS(0,&head);
    	DEEP++;
    	*pulHeight = DEEP;
    	DEEP = 0;
    	for(int i =0; i < 10010;i++)
    		DEEP = level[i] > DEEP ? level[i] : DEEP;
    	*pulWidth = DEEP; 
    	return 0;
    }
    


    展开全文
  • 【题目名称】求二叉树的宽度 【问题描述】 以二叉链表为存储结构,编写算法求二叉树的宽度(具有结点数最多的那一层上的节点个数)。 【输入形式】两行,第一行是扩展二叉树的前序遍历序列。 【输出形式】二叉树的...

    【练习时间】2021/3/16
    【题目名称】求二叉树的宽度
    【问题描述】

    以二叉链表为存储结构,编写算法求二叉树的宽度(具有结点数最多的那一层上的节点个数)。
    1.png
    【输入形式】两行,第一行是扩展二叉树的前序遍历序列。

    【输出形式】二叉树的宽度。

    【样例输入】AB#D##C##

    【样例输出】2

    【思路分析】
    我采用的思路是在构造树之后,设置该节点的孩子节点的个数,并将其一起封装起来存储到结构体中,然后采用层序遍历的方法,将该节点左孩子的孩子节点个数和该节点右孩子的孩子节点个数相加,与当前最大值比较,最终输出的最大值即为树的宽度。

    【代码分析】
    首先设计结构体并生成树

    int cont=0;//用于记录当前最大值 
    struct BiNode
    {
    	char data;
    	int numchild;//用于记录孩子节点的个数 
    	BiNode *lchild;
    	BiNode *rchild;
    };
    BiNode *Creat()
    {
    	BiNode *bt;
    	char ch;
    	cin>>ch;
    	if(ch=='#')return NULL;
    	else{
    		bt=new BiNode;
    		bt->data=ch;
    		bt->lchild=Creat();
    		bt->rchild=Creat();
    	}
    	return bt;
    }
    void SetNumchild(BiNode *bt)//设置某一个节点它的孩子节点的个数 
    {
    	if(bt==NULL)return;
    	else{
    		if(bt->rchild!=NULL&&bt->lchild!=NULL)bt->numchild=2;
    		else if(bt->lchild==NULL&&bt->rchild==NULL)bt->numchild=0;
    		else bt->numchild=1;
    		SetNumchild(bt->lchild);
    		SetNumchild(bt->rchild);
    	}
    	return;
    }
    

    接下来我们需要将每个节点的孩子节点的相加,并与当前最大值比较

    void PreOrder(BiNode *q)
    {
    	if(q==NULL)return;
    	else {
    		int sum;
    		if(q->lchild!=NULL&&q->rchild!=NULL)
    		{
    			sum=q->lchild->numchild+q->rchild->numchild;
    		}
    		else if(q->lchild==NULL&&q->rchild!=NULL)sum=q->rchild->numchild;
    		else if(q->rchild==NULL&&q->lchild!=NULL)sum=q->lchild->numchild;
    		else sum=0;
    		if(sum>cont)cont=sum;
    		PreOrder(q->lchild);
    		PreOrder(q->rchild);
    	}
    } 
    

    下面是主函数部分,由于根节点也存储了孩子节点的个数,而在PreOder函数当中并没有对根节点进行操作比较,所以我们需要在主函数中设置一个节点——使得此节点的有且仅有一个孩子节点即根节点

    int main()
    {
    	BiNode *bt=Creat();//根节点 
    	SetNumchild(bt);
    	
    	BiNode *front=new BiNode;//虚拟节点 
    	front->lchild=bt;
    	
    	PreOrder(front);
    	cout<<cont;
    	return 0;
    } 
    

    当然我们也需要设置一些全局变量来存储某些值。

    【源代码】

    #include <iostream>
    using namespace std;
    int cont=0;//用于记录当前最大值 
    struct BiNode
    {
    	char data;
    	int numchild;//用于记录孩子节点的个数 
    	BiNode *lchild;
    	BiNode *rchild;
    };
    BiNode *Creat()
    {
    	BiNode *bt;
    	char ch;
    	cin>>ch;
    	if(ch=='#')return NULL;
    	else{
    		bt=new BiNode;
    		bt->data=ch;
    		bt->lchild=Creat();
    		bt->rchild=Creat();
    	}
    	return bt;
    }
    void SetNumchild(BiNode *bt)//设置某一个节点它的孩子节点的个数 
    {
    	if(bt==NULL)return;
    	else{
    		if(bt->rchild!=NULL&&bt->lchild!=NULL)bt->numchild=2;
    		else if(bt->lchild==NULL&&bt->rchild==NULL)bt->numchild=0;
    		else bt->numchild=1;
    		SetNumchild(bt->lchild);
    		SetNumchild(bt->rchild);
    	}
    	return;
    }
    void PreOrder(BiNode *q)
    {
    	if(q==NULL)return;
    	else {
    		int sum;
    		if(q->lchild!=NULL&&q->rchild!=NULL)
    		{
    			sum=q->lchild->numchild+q->rchild->numchild;
    		}
    		else if(q->lchild==NULL&&q->rchild!=NULL)sum=q->rchild->numchild;
    		else if(q->rchild==NULL&&q->lchild!=NULL)sum=q->lchild->numchild;
    		else sum=0;
    		if(sum>cont)cont=sum;
    		PreOrder(q->lchild);
    		PreOrder(q->rchild);
    	}
    } 
    int main()
    {
    	BiNode *bt=Creat();//根节点 
    	SetNumchild(bt);
    	
    	BiNode *front=new BiNode;//虚拟节点 
    	front->lchild=bt;
    	
    	PreOrder(front);
    	cout<<cont;
    	return 0;
    } 
    
    展开全文
  • 求二叉树宽度.exe - 1 error(s), 0 warning(s) #include #include #define maxsize 20 St A[maxsize]; int L=1;//记录层数 int i=0; void width(BTNode *p); BTNode *CreateBiTree(); void main() { int j,k=...
  • PTA 求二叉树的宽度

    2019-10-23 10:22:43
    typedef struct TreeNode *BinTree; struct TreeNode { int Key; BinTree Left; BinTree Right; }; int Width( BinTree T ) ...//队列储存树结点 int Last, temp_width, max_widt...
  • 一、二叉树宽度  利用队列保存每一层结点,借助层次遍历思想(先将根节点入队,队列非空时每出队一个结点将其左右子节点入队),队列中结点个数就是下一次循环次数,当循环结束后队列中结点就全部是下一...
  • 算法学习 - 求二叉树的宽度

    千次阅读 2015-03-11 18:17:24
    二叉树的宽度二叉树的宽度定义为 整个二叉树各层节点数,其中最大的值为这个二叉树的宽度。 所以二叉树的第一层就是1(根节点)。代码实现(C++)代码实现比较简单,树的遍历一般用递归比较方便。// // main.cpp // ...

空空如也

空空如也

1 2 3 4 5 ... 18
收藏数 342
精华内容 136
关键字:

求二叉树的宽度