Bst

AVL之前写过的二叉排序树（BST）在插入、删除和查找等基本操作的平均时间为O(logN)，但在最坏的情况下，这些基本运算的时间均会增至O(n)（因为退化成了链表）。为了避免这些情况发生，人们研究了许多种动态平衡的方法，使得在树中插入或删除元素时，通过调整树的形态来保持树的“平衡”，使之既保持BST的性质不变又保证树的高度在任何情况下均为O(logN)，从而确保树上的基本运算在最坏情况下的时间也均为O(logN)。下面的AVL就是这样的平衡树。 AVL 树是一种平衡二叉树，得名于其发明者的名字（ Adelson-Velskii 以及 Landis）。平衡二叉树递归定义如下： 左右子树的高度差小于等于 1。其每一个子树均为平衡二叉树。基于两点，我们就可以进行判断其一棵树是否为平衡二叉树了。 实现原理算法通过平衡因子（balaced factor，用bf表示）来具体实现上述平衡二叉树的定义。平衡因子的定义：平衡二叉树中每个节点有一个平衡因子，每个节点的平衡因子是该节点的左子树高度减去右子树的高度。从平衡因子的角度说，若一棵二叉树中所有节点的平衡因子的绝对值都小于等于1，即平衡因子取值为0、1或-1，则该二叉树为平衡二叉树。 用C语言定义该节点为： typedef struct node{ KeyType key; int bf; // 平衡因子 InfoType data; struct node *lchild, *rchild; } BSTNode;

江南无所谓 聊赠一枝春 前言二叉搜索树插入二叉搜索树遍历二叉搜索树高度二叉搜索树最大值什么是二叉搜索树满足条件： 左节点值 < 根节点值 < 右节点值 定义树节点 typedef struct TreeNode { int data; struct TreeNode *left; struct TreeNode *right; } TreeNode;定义树 typedef struct tree { struct TreeNode *root; } Tree;二叉搜索树的插入插入节点 void insertNode (Tree *tree, int value) { TreeNode *node1 = malloc(sizeof(TreeNode)); node1->data = value; node1->left = NULL; node1->right = NULL; if(tree->root == NULL){ tree->root = node1; } else { TreeNode *temp = tree->root; while (temp != NULL) { if(value < temp->data){ if(temp->left == NULL) { temp->left = node1; return ; } else { temp = temp->left; } } else { if(temp->right == NULL) { temp->right = node1; return; } else { temp = temp->right; } } } } }BST的前中后序遍历 // 前序遍历 根->左->右 void preorderTraverse(TreeNode *tree) { if(tree == NULL) {return;} NSLog(@"%d ", tree->data); preorderTraverse(tree->left); preorderTraverse(tree->right); } //中序遍历 左->根->右 void midTraverse(TreeNode *tree) { if(tree == NULL) {return;} midTraverse(tree->left); NSLog(@"%d ", tree->data); midTraverse(tree->right); } //后序遍历 左->右->根 void postorderTraversal(TreeNode *tree) { if(tree == NULL) {return;} postorderTraversal(tree->left); postorderTraversal(tree->right); NSLog(@"%d ", tree->data); }二叉搜索树高度 int getBSTHeight (TreeNode *node) { if (node == NULL) { return 0; } else { int leftH = getBSTHeight(node->left); int rightH = getBSTHeight(node->right); int max = leftH; if (max < rightH) { max = rightH; } return max+1; } }二叉搜索树最大值 int getMaxNum(TreeNode *node) { if (node == NULL) { return -1; } else { int leftMax = getMaxNum(node->left); int rightMax = getMaxNum(node->right); int current = node->data; int max = leftMax; if (rightMax > max) { max = rightMax; } if (current>max) { max = current; } return max; } }测试功能 int arr[] = {6,3,8,2,5,1,7}; // 创建树 Tree *tree = malloc(sizeof(Tree)); tree->root = NULL; for(int i=0; i<7; i++) { // 树中插入节点 insertNode(tree, arr[i]); } // 计算树的高度 int treeH = getBSTHeight(tree->root); NSLog(@"%d\n", treeH); // 计算树的最大值 int maxNum = getMaxNum(tree->root); NSLog(@"%d\n", maxNum);测试结果 ...

题目要求Given a root node reference of a BST and a key, delete the node with the given key in the BST. Return the root node reference (possibly updated) of the BST.Basically, the deletion can be divided into two stages:Search for a node to remove.If the node is found, delete the node.Note: Time complexity should be O(height of tree).Example:root = [5,3,6,2,4,null,7]key = 3 5 / \ 3 6 / \ \2 4 7Given key to delete is 3. So we find the node with value 3 and delete it.One valid answer is [5,4,6,2,null,null,7], shown in the following BST. 5 / \ 4 6 / \2 7Another valid answer is [5,2,6,null,4,null,7]. 5 / \ 2 6 \ \ 4 7假设有一棵二叉搜索树，现在要求从二叉搜索树中删除指定值，使得删除后的结果依然是一棵二叉搜索树。 ...