关于二叉排序树的插入，高度，遍历

 首先定义一课树和结点

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

typedef struct node{
	int data;
	struct node* left;
	struct node* right;
}Node;//树结点

typedef struct{
	Node *root;
} Tree;

然后插入结点

这里我想插入结点之后为一棵二叉排序树

（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；

（2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值；

（3）左、右子树也分别为二叉排序树；

（4）没有键值相等的节点。

我这里以插入结点的数列int arr[7]={6,8,2,1,4,3,9} 为例

void insert(Tree *tree,int value)
{
	Node* node=(Node*)malloc(sizeof(Node));
	node->data=value;
	node->left=NULL;
	node->right=NULL;
	//当数为空时，将结点放到根结点上
	if (tree->root==NULL)
	{
		tree->root=node;
	}
	else//当根结点不为空时，就要比大小了,temp为当前比较的结点
	{
		Node* temp=tree->root;//先让temp指向根结点
		while (temp!=NULL)
		{
			if (value<temp->data)//value小的话走左边
			{
				if(temp->left==NULL)//左边为空，直接插入
					{temp->left=node;return;}
//或者break也可以，这里结点已经插进去了，所以要跳出循环
				
				else 
					temp=temp->left;
//左边不为空就把temp指到左子树继续做比较
			}
			else//value大的就往右走
			{
				if(temp->right==NULL)//右边是空的就直接插入
					{temp->right=node;return;}
				else
					temp=temp->right;
//右边不为空就把temp指到右子树继续做比较
			}
		}
	}
}

 为验证是否插入正确，输出前序遍历序列看一下，中序遍历后序遍历都是一样的写法，改一下顺序即可。

void preorder(Node *node)
{
	if(node!=NULL)
	{
		printf("%d ",node->data);
		preorder(node->left);
		preorder(node->right);
	}
}

 如何求一个树的高度呢？

将这棵树的左右子树的高度求出，然后比大小，大的值加1，即为树的高度。递归。

 

//计算数的高度
int height(Node* node)//将左子树和右子树的高度比大小，大的那边子树的高度加1，就是数的高度
{
	int max;
	if(node==NULL)//一定要设置好这样的递归出口
		return 0;
	else
	{
		int left_h=height(node->left);
		int right_h=height(node->right);
		int max=left_h;
		if(right_h>max)
			max=right_h;
		return max+1;
	}
}

二叉排序树里结点最大的值就是最右边的结点，那么对于一颗普通二叉树来说，找最大值，需要进行每个结点比较。

左右结点与当前根结点作比较，递归。

//对于一个普通二叉树找最大值，就是左边的值和右边的值和根结点作比较，然后递归，递归出口就是只有1个结点
int getmax(Node* node)//假设结点的值都是正数
{
	if (node==NULL)
	{
		return -1;
	}
	else{
		int n1=getmax(node->left);
		int n2=getmax(node->right);
		int n3=node->data;
		int max=n1;
		if(n2>max)
			max=n2;
		if(n3>max)
			max=n3;
		return max;
	}
}

 

 然后输出结果为

int main()
{
	int arr[7]={6,8,2,1,4,3,9} ;
	Tree tree;
	tree.root=NULL;
	int i;
	//将arr这个数组放进树里
	for(i=0;i<7;i++)
	{
		insert(&tree,arr[i]);
	}
	printf("前序遍历结果：\n");
	preorder(tree.root);

	printf("\n");
	int h;
	h=height(tree.root);
	printf("the height of tree=%d\n",h);
	int max;
	max=getmax(tree.root);
	printf("the max of tree=%d\n",max);
}