树

• 任一棵树中，结点总数=度数*该度数对应的结点数+1

  • 子节点个数为n0即各个度对应的个数乘以度减一然后累加后加1

    已知一棵度为m的树中：n1个度为1的结点，n2个度为2的结点，…，nm个度m的结点，问该树中共有多少个叶子结点？
    
    设该树的总结点数为n，则
    n=n0+n1+n2+…+nm
    又：
    n=分枝数+1=0xn0+1xn1+2xn2+…+mxnm
    由上述两式可得：
    n0=n2+2n3+…+(m-1)nm+1
    
    即
    
         d
    n0 =( Σ n(i) * (i - 1)) + 1           
    ​     i=1
     (其中，i ∈ Integer，d为树的度)

• 树中边和结点的关系为：结点数=边数+1 -> 边数 = 结点数-1

哈夫曼树

• 创建哈夫曼树并输出所有度为2的结点权值的和(huffman tree没有度为1的结点，度为0为叶子结点)

  #include<iostream>
  
  using namespace std;
  
  struct huffman{
  	int data;
  	int parent;
  	int lchild;
  	int rchild;
  };
  
  int n, i, a, b, sum;
  //a,b是构造过程中的用于构造哈夫曼树的两个结点的下标，sum是计算所有度为2的结点的权值之和，n是叶子结点个数
  huffman huff[105];
  const int INF = 0x3f3f3f3f;
  
  int select(){
  //选出huff[1]到huff[i-1]中权值最小的且无父母结点的两个结点用以构造哈夫曼树
  	int huffdata1 = INF, huffdata2 = INF;
  	for(int j = 1; j <= i-1; j++){
  		if(huff[j].parent == 0){
  			if(huff[j].data < huffdata1){
  				if(huff[j].data < huffdata2){
  					switch(huffdata2 > huffdata1){
   //注意因为huff[j].data可能小于huffdata2，而huffdata1如果小于huffdata2，那么应该将huffdata2权值更新为huffdata1，因为每次要选出结点权值最小的两个结点
  						case 1:
  							huffdata2 = huffdata1;
  							b = a;
  							huffdata1 = huff[j].data;
  							a = j;
  							break;
  						case 0:
  							huffdata1 = huff[j].data;
  							a = j;
  							break;
  					}
  				}
  			}
  			else if(huff[j].data < huffdata2){
  				huffdata2 = huff[j].data;
  				b = j;
  			}
  		}
  	}
  }
  
  int main(){
  	cin >> n;
  	for(i = 1; i <= n; i++){
  		cin >> huff[i].data;
  		huff[i].lchild = huff[i].rchild = huff[i].parent = 0;
  	}	
  	for(i = n+1; i <= 2*n-1; i++) huff[i] = {0, 0, 0, 0};
  	for(i = n+1; i <= 2*n-1; i++){
  		select(); 
  		sum += huff[a].data + huff[b].data;	
  		huff[i].data = huff[a].data + huff[b].data;
  		huff[a].parent = huff[b].parent = i;
  		huff[i].lchild = a, huff[i].rchild = b;
  	}
  	cout << sum;
  	return 0;
  }
  
  模拟哈夫曼树构造过程:
  4 5 1 2 1 3 1 1
  1 1 2 2 3 4 5
  2 2 2 3 4 5
  2 3 4 4 5
  4 4 5 5
  5 5 8
  8 10
  18

二叉树

二叉排序树查找

#include<iostream>
#include<cstdlib>
#define M 20

using namespace std;


struct node
{
	int data;
	struct node *l,*r;
};

int k = 0;
int kk = 0;
node *bst = NULL;
node bstnode;

int insert(node* &bs, int k){   
	
	if(bs == NULL){
		node* s = new node;
		s -> data = k;
		s -> l = NULL, s -> r = NULL;
		bs = s;
	}
	else if(k < (bs) -> data){
		insert(bs -> l, k);
	}
	else{
		insert(bs -> r, k);
	}	
	
	return 0;
} 

node* search(node* bs, int k){
	if(!bs) return NULL;
	else if(bs -> data == k){
		kk++;
		return bs;
	}
	else if(bs -> data > k) kk++, search(bs -> l, k);
	else if(bs -> data < k) kk++, search(bs -> r, k);
	return bs;
}	

int main(){
	node *bs = NULL;
	cin >> k;
	while(1){
		insert(bs, k);
		cin >> k;
		if(k == -1) break;
	}
	cin >> k;
	search(bs, k);
	cout << kk;
	return 0;
}