p244-1.cpp

非常好的C++学习源码,里面包括各种算法的实现,二叉的的前中后序遍历等

#include <stdio.h>
#include <stdlib.h>

struct TreeNode{
	int val;
	int depth;
	TreeNode *left,*right;
};

void computeDepth(TreeNode *root){
	int depth;
	if (root->left!=NULL)
		depth=root->left->depth;
	else
		depth=0;
	if (root->right!=NULL && root->right->depth>depth)
		depth=root->right->depth;
	root->depth=depth+1;
	return;
}

TreeNode *balance(TreeNode *root){
	int leftD,rightD;
	TreeNode *newRoot;
	if (root->left!=NULL)
		leftD=root->left->depth;
	else
		leftD=0;
	if (root->right!=NULL)
		rightD=root->right->depth;
	else
		rightD=0;
	if (abs(leftD-rightD)<2) return (root);

	if (leftD>rightD)
		if (root->left->right!=NULL){
			newRoot=root->left->right;
			root->left->right=newRoot->left;
			newRoot->left=balance(root->left);
			root->left=newRoot->right;
			newRoot->right=balance(root);
		}
		else{
			newRoot=root->left;
			root->left=newRoot->right;
			newRoot->right=root;
		}

	if (leftD<rightD)
		if (root->right->left!=NULL){
			newRoot=root->right->left;
			root->right->left=newRoot->right;
			newRoot->right=balance(root->right);
			root->right=newRoot->left;
			newRoot->left=balance(root);
		}
		else{
			newRoot=root->right;
			root->right=NULL;
			newRoot->left=root;
		}

	computeDepth(newRoot->left);
	computeDepth(newRoot->right);

	return(newRoot);

}

TreeNode *insertBTree(TreeNode *root,int val){
	TreeNode *newNode, *newRoot;

	if (root==NULL){
		newNode=new TreeNode;
		newNode->val=val;
		newNode->depth=1;
		newNode->left=NULL;
		newNode->right=NULL;
		return(newNode);
	}

	if (val<=root->val)
		root->left=insertBTree(root->left,val);
	else
		root->right=insertBTree(root->right,val);

	newRoot=balance(root);
	computeDepth(newRoot);

	return(newRoot);
}

void save_delTree(TreeNode *root,char offset[], FILE *fout){
	char result[20],rr[20];
	char ss[81];
	sprintf(result,"%s%d\n",offset,root->val);
	fputs(result,fout);
	sprintf(ss,"%s%s",offset,"    ");
	sprintf(rr,"%s$\n",ss);

	if (root->left!=NULL)
		save_delTree(root->left,ss,fout);
	else
		fputs(rr,fout);

	if (root->right!=NULL)
		save_delTree(root->right,ss,fout);
	else
		fputs(rr,fout);
	delete root;
	return;
}

void main()
{
	FILE *fin,*fout;
	TreeNode *root;
	int val;
	char str[81],inFile[30],outFile[30];

	printf("input the data file's name:");
	scanf("%s",inFile);
	printf("input the file name for saving results:");
	scanf("%s",outFile);

	root=NULL;
	fin=fopen(inFile,"r");
	while(fscanf(fin,"%d",&val)!=EOF) root=insertBTree(root,val);
	fclose(fin);

	fout=fopen(outFile,"w");
	sprintf(str,"%s","");
	save_delTree(root,str,fout);
	fclose(fout);
	return;
}