本文共 2442 字，大约阅读时间需要 8 分钟。

这是二叉搜索树的一些基本概念。二叉搜索树具有如下特点：

1. 根节点的值大于左子树的值，根节点的值小于右节点的值。
2. 中序遍历的结果是从下到大。（与其构成的原理有关）
3. 最大值一定在右子树上。最小值一定在左子树上。

要构建二叉树，首先构建起每个结点的构成，这里，使用结构体来表示其结构；在这里要强调，指针和成员变量的关系，如果使用了指针为参数，在调用结构体时要是用箭头来调用其中的成员。

typedef struct node{	int date;	struct node*left;	struct node*right;}Node; typedef struct{	Node *root;} Tree;

现在就开始创建二叉树，使其结构完整。先判断是否存在根节点，如果有就判断左子树或右子树，否则把传入的值作为根节点赋值。

void insert(Tree* tree, int value){	Node* node = (Node *)malloc(sizeof(Node));	node->date = value;	node->left = NULL;	node->right = NULL;	if(tree->root == NULL){		tree->root = node;	}else{		Node* temp = tree->root;		while(temp != NULL){			if(value < temp->date){				if(temp->left == NULL){					temp -> left = node;					return ;				}else{					temp = temp->left;				}			}else{				if(temp->right == NULL){					temp -> right = node;					return ;				}else{					temp = temp->right;				}			}		} 	}}

现在就是对二叉树来说比较重要的遍历先序，中序，后序；这个以前博客有写过（）只要把握住,先序是(根->左->右), 中序(左->根->右)，后序(左->右->根)；就可以使用递归的方法来解决。

void preorder(Node *node){	if(node != NULL){		printf("%d\n",node->date);		preorder(node->left);		preorder(node->right); 	}}void inorder(Node *node){	if(node != NULL){		inorder(node->left);		printf("%d\n",node->date);		inorder(node->right); 	}}void postorder(Node *node){	if(node != NULL){		postorder(node->left);		postorder(node->right); 		printf("%d\n",node->date);	}}

再就是求深度；首先我们要是到在二叉树中递归是经常使用的方法。如果对递归不是太了解就先在网上看看，了解一下，这样更有利于学习；深度肯定就是比较左子树和右子树的深度，取大值就好；

int get_height(Node *node){	if(node == NULL){		return 0;	}else{		int left_h = get_height(node -> left);		int right_h = get_height(node -> right);		int man = left_h;		if(right_h > man){			man = right_h;		}		return man + 1;	}}

当然也有非递归的算法：

int get_h(Node* node){	if(node == NULL) return 0;	int hh = 0;	int wh  = 0;	Node* q = (Node *)malloc(sizeof(q));	queue
   
    qu;	qu.push(node);	while(!qu.empty()){		wh = qu.size();		hh++;		for(int i = 0;i < wh; i++){			q = qu.front();			qu.pop();			if(q->left){				qu.push(q->left);			}			if(q->right){				qu.push(q->right);			}		}	}	return hh;}
   

最后就是求出最大值，一种适用于所有的二叉树。另一种只适用于二叉搜索树：

int get_maxnum(Node *node){	if(node == NULL)return -1;	else{		int m1 = get_maxnum(node->left);		int m2 = get_maxnum(node->right);		int m3 = node->date;		int man = m1;		if(m2 > man) man = m2;		if(m3 > man) man = m3;		return man;	}}int get_maxnn(Node *node){	if(node == NULL) return -1;	else{		int m1 = get_maxnn(node -> right);		int maxnn = node->date;		if(m1 > maxnn)maxnn = m1;		return maxnn;	}}

当然这个也有非递归的写法，自己尝试一下；

转载地址：http://aqpfb.baihongyu.com/