二叉排序树的应用（求树的高度、树中最大元素的值、查找某个值）

短命女 2023-06-24 10:29 6阅读 0赞

我们可以利用递归来求一个二叉排序树的高度

int tree_hight(Node *node)
    {
        
    	if (node != NULL) {
        
    		int left_h = tree_hight(node->left);  //递归求左树的高度
    		int right_h = tree_hight(node->right); //递归求右树的高度
    		int max = left_h;
    		if (left_h < right_h) {
        
    			max = right_h;
    		}
    		return max + 1;
    	}
    }

还可以使用递归来求树中最大的元素

int tree_maxnum(Node *node)
    {
        
    	if (node != NULL) {
        
    		int m1 = tree_maxnum(node->left);  //递归求左树的最大值
    		int m2 = tree_maxnum(node->right); //递归求右树的最大值
    		int m3 = node->data;   //根节点的值
    		int max = m1;
    		if (max < m2) {
        
    			max = m2;
    		}
    		if (max < m3) {
        
    			max = m3;
    		}
    		return max;
    	}
    }

查找这个树中是否有我们想要的值。

static int i = 0;
    
    void sreach_tree(Node *node, int key)
    {
        
    	++i;
    	if (node) {
        
    		if (key == node->data) {
        
    			printf("have this data , is %d\n", node->data);
    			printf("the sreach number is %d\n", i);
    			return;
    		}
    		else if (key < node->data) {
        
    			sreach_tree(node->left, key);  //值小于根的值，往左树查找
    		}
    		else {
        
    			sreach_tree(node->right, key); //值大于根的值，往右树查找
    		}
    	}
    }

总的代码

#include <stdio.h>
    #include <stdlib.h>
    
    typedef struct node {
        
    	int data;
    	struct node *left;
    	struct node *right;
    }Node;
    
    typedef struct tree {
        
    	Node *root;
    }Tree;
    
    void create_tree(Tree *tree, int val)
    {
        
    	Node *node = (Node*)malloc(sizeof(Node));
    	node->data = val;
    	node->left = NULL;
    	node->right = NULL;
    	
    	if (tree->root == NULL) {
        
    		tree->root = node;
    	}
    	else {
        
    		Node *temp = tree->root;
    		while (temp != NULL) {
        
    			if (val < temp->data) {
        
    				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("data is %d\n",node->data);
    		preorder(node->left);
    		preorder(node->right);
    	}
    }
    
    void inorder(Node *node)
    {
        
    	if (node != NULL) {
        
    		inorder(node->left);
    		printf("data is %d\n",node->data);
    		inorder(node->right);
    	}
    }
    
    void postorder(Node *node)
    {
        
    	if (node != NULL) {
        
    		postorder(node->left);
    		postorder(node->right);
    		printf("data is %d\n",node->data);
    	}
    }
    
    static int i = 0;
    
    void sreach_tree(Node *node, int key)
    {
        
    	++i;
    	if (node) {
        
    		if (key == node->data) {
        
    			printf("have this data , is %d\n", node->data);
    			printf("the sreach number is %d\n", i);
    			return;
    		}
    		else if (key < node->data) {
        
    			sreach_tree(node->left, key);
    		}
    		else {
        
    			sreach_tree(node->right, key);
    		}
    	}
    }
    
    int tree_hight(Node *node)
    {
        
    	if (node != NULL) {
        
    		int left_h = tree_hight(node->left);
    		int right_h = tree_hight(node->right);
    		int max = left_h;
    		if (left_h < right_h) {
        
    			max = right_h;
    		}
    		return max + 1;
    	}
    }
    
    int tree_maxnum(Node *node)
    {
        
    	if (node != NULL) {
        
    		int m1 = tree_maxnum(node->left);
    		int m2 = tree_maxnum(node->right);
    		int m3 = node->data;
    		int max = m1;
    		if (max < m2) {
        
    			max = m2;
    		}
    		if (max < m3) {
        
    			max = m3;
    		}
    		return max;
    	}
    }
    
    int main(int argc, char **argv)
    {
        
    	int a[9] = {
        1,35,15,11,17,99,56,66,8};
    	Tree tree;
    	tree.root = NULL;
    	int i;
    	int len = sizeof(a) / sizeof(int);
    	for (i=0; i<len; i++) {
        
    		create_tree(&tree, a[i]);
    	}
    	
    	inorder(tree.root);
    	sreach_tree(tree.root, 8);
    	
    	int h = tree_hight(tree.root);
    	printf("this tree's hight is %d\n",h);
    	
    	int maxnum = tree_maxnum(tree.root);
    	printf("this tree's max num is %d\n", maxnum);
    
    	return 0;
    }