6.44.cpp

哈夫曼树

//从键盘读入一组数据，根据输入的数据创建一个二叉树，数据的插入按
//照每个节点的左节点小于等于该节点，右节点大于该节点的规则。
#include <stdio.h>
#include <stdlib.h>
#define Maxsize 10
struct TNode
{
		int data;
		struct TNode * left;
		struct TNode * right;
};

typedef struct TNode *Tree;
int n,c=0,x;

int l,r;
void Insert(Tree *t, int value)
{
	struct TNode *tmp;
	Tree T =*t;
	if(T == NULL)
	{
		tmp =(struct TNode *)malloc(sizeof(struct TNode));
		tmp->data = value;
		tmp->left = NULL;
		tmp->right = NULL;
		*t = tmp;
	}
	else
	{
		if( value <= T->data)
		{
			if(T->left != NULL)
				Insert(&(T->left), value);
			else
			{
				tmp =(struct TNode *)malloc(sizeof(struct TNode));
				tmp->data = value;
				tmp->left = NULL;
				tmp->right = NULL;
				(*t)->left = tmp;
			}
		}
		else
		{
			if(T->right != NULL)
				Insert(&(T->right), value);
			else
			{
				tmp =(struct TNode *)malloc(sizeof(struct TNode));
				tmp->data = value;
				tmp->left = NULL;
				tmp->right = NULL;
				(*t)->right = tmp;
			}
		}
	}
}


int Get_Depth(Tree T)//求子树深度的递归算法
{
  if(!T) return 0;
  else
  {
    l=Get_Depth(T->left);
    r=Get_Depth(T->right);
    return (l>r?l:r)+1;
  }
}//Get_Depth 


int Get_Sub_Depth(Tree T,int x)//求二叉树中以值为x的结点为根的子树深度
{
  if(T->data==x)
  {
    printf("%d\n",Get_Depth(T)); //找到了值为x的结点,求其深度
    return 1;
  }
  else
  {
    if(T->left) Get_Sub_Depth(T->left,x);
    if(T->right) Get_Sub_Depth(T->right,x); //在左右子树中继续寻找
  }
}//Get_Sub_Depth 


void main()
{   
	Tree T;
	int i,a;
	T=NULL;
	printf("How many nodes?\n");
	scanf("%d",&n);
	for(i=0; i<n; i++)
	{
		scanf("%d",&a);
		Insert(&T,a);
	}
    printf("\n");
    printf("请输入节点x的值\n");
    scanf("%d",&x);
	printf("子树的深度为:");
	Get_Sub_Depth(T,x);
	printf("\n");
}