二叉树宽度的计算

「爱情、让人受尽委屈。」 2022-08-02 07:20 131阅读 0赞

二叉树的宽度定义为具有最多结点数的层中包含的结点数，试计算一二叉树的宽度。

#include "stdafx.h"
    #include<iostream>  
    #include<vector>
    
    using namespace std;
    
    
    struct BiNOde
    {
    	int ele;
    	BiNOde* lnode;
    	BiNOde* rnode;
    };
    
    vector<int>aa;
    int maxdepth = 0;
    
    
    
    BiNOde*create_tree()
    {
    	BiNOde * root = new BiNOde;
    	BiNOde*node1 = new BiNOde;
    	BiNOde*node2 = new BiNOde;
    	BiNOde*node3 = new BiNOde;
    	BiNOde*node4 = new BiNOde;
    	BiNOde*node5 = new BiNOde;
    	BiNOde*node6 = new BiNOde;
    	BiNOde*node7 = new BiNOde;
    	BiNOde*node8 = new BiNOde;
    	BiNOde*node9 = new BiNOde;
    	BiNOde*node10 = new BiNOde;
    	BiNOde*node11 = new BiNOde;
    	root->ele = 0;
    	node1->ele = 1;
    	node2->ele = 2;
    	node3->ele = 3;
    	node4->ele = 4;
    	node5->ele = 5;
    	node6->ele = 6;
    	node7->ele = 7;
    	node8->ele = 8;
    	node9->ele = 9;
    	node10->ele = 10;
    	node11->ele = 11;
    	root->lnode = node1;
    	root->rnode = node2;
    	node1->lnode = node3;
    	node1->rnode = node4;
    	node2->lnode = node7;
    	node2->rnode = node8;
    	node3->lnode = node5;
    	node3->rnode = node11;
    	node4->lnode = node10;
    	node4->rnode = NULL;
    	node5->lnode = node6;
    	node5->rnode = NULL;
    	node6->lnode = NULL;
    	node6->rnode = NULL;
    	node7->lnode = node9;
    	node7->rnode = NULL;
    	node8->lnode = NULL;
    	node8->rnode = NULL;
    	node9->lnode = NULL;
    	node9->rnode = NULL;
    	node10->lnode = NULL;
    	node10->rnode = NULL;
    	node11->lnode = NULL;
    	node11->rnode = NULL;
    	//BiNOde*node12 = new BiNOde;  
    	//node12->ele = 12;  
    	//node12->lnode = NULL;  
    	//node12->rnode = NULL;  
    	//node6->lnode = node11;  
    
    	return root;
    }
    
    
    void PreOrderTraverseTree(BiNOde*node,BiNOde*root)
    {
    	if (node == NULL)
    		return ;
    	if(node==root)
    	{
    		root->ele=0;
    		aa.push_back(1);
    	}
    	else
    	{
    		aa[node->ele]++;
    	}
    	if (node->lnode != NULL)
    	{
    		node->lnode->ele=node->ele+1;
    		if (node->lnode->ele > aa.size()-1)
    			aa.push_back(0);
    		PreOrderTraverseTree(node->lnode, root);
    
    	}
    	if (node->rnode != NULL)
    	{
    		node->rnode->ele=node->ele+1;
    		if (node->rnode->ele > aa.size()-1)
    			aa.push_back(0);
    		PreOrderTraverseTree(node->rnode, root);
    	}
    }
    
    
    int _tmain(int argc, _TCHAR* argv[])
    {
    	BiNOde*root=create_tree();
    	PreOrderTraverseTree(root, root);
    	maxdepth=aa.size()-1;
    
    	for (int i = 0; i < maxdepth+1; i++)
    		cout<<aa[i]<<endl;
    
    	system("pause");
    	return 0;
    }

注意，原二叉树要留一份拷贝