2021-11-26 01:04

# 二叉排序树及将树平衡的问题

``````#include<stdio.h>
#include<stdlib.h>
typedef struct Node {
int data;
struct Node* left;
struct Node* right;
}Node;
typedef struct  {
Node* root;
}Tree;
void addnode(Tree* tree, int data) {//添加
Node* node = (Node*)malloc(sizeof(Node));
node->data = data;
node->left = NULL;
node->right = NULL;
if (tree->root == NULL) {
tree->root = node;
}
else {
Node* temp = (Node*)malloc(sizeof(Node));//存储当前根节点内容
temp = tree->root;
while (temp != NULL) {
if (temp->data > data) {
if (temp->left == NULL) {
temp->left = node;
return;
}
else {
temp = temp->left;

}
}
else {
if (temp->data < data) {
if (temp->right == NULL) {
temp->right = node;
return;
}
else {
temp = temp->right;
}
}
}
}
}
}

Node* findmin(Node* node) {//找到最小值
if (node == NULL)
return NULL;
while (node->left != NULL)
node = node->left;
return node;
}
Node *denode(Node* node, int data) {//删除
if (node ==NULL) {
return node;
}
else {
if (node->data > data) {
node->left = denode(node->left, data);
}
else if (node->data < data) {
node->right = denode(node->right, data);
}
else {
if (node->left == NULL && node->right == NULL) {
node = NULL;
}
else if (node->left != NULL && node->right == NULL) {

node = node->left;

}
else if (node->right != NULL && node->left == NULL) {
node = node->right;
}
else {
Node* pre = findmin(node->right);
node = denode(node,pre->data);
node->data = pre->data;
}
}
}
return node;
}
int height(Node* node) {//求树的高度
if (node == NULL) {
return -1;
}
else if (node->left == NULL && node->right == NULL) {
return 0;
}
else {
int left = height(node->left);
int right = height(node->right);
return left>right?(left + 1):(right + 1);
}
}
Node* leftrotation(Node* node) {//左旋
Node* temp = node->right;
node->right = temp->left;
temp->left = node;
return temp;
}
Node* rightrotation(Node* node) {//右旋
Node* temp = node->left;
node->left = temp->right;
temp->right = node;
return temp;
}
Node* balance(Node* current) {//平衡
if (current == NULL) {
return current;
}
if (height(current->left) - height(current->right) > 1) {
if (height(current->left->left) >= height(current->left->right)){
return rightrotation(current);
}
else {
return rightrotation(leftrotation(current->left));
}
}
if (height(current->right) - height(current->left) > 1) {
if (height(current->right->right) >= height(current->right->left)) {
return leftrotation(current);
}
else {
return leftrotation(rightrotation(current->right));
}
}
return current;
}

void firorder(Node* node) {//先序遍历
if (node != NULL) {
printf("%d\n", node->data);
firorder(node->left);
firorder(node->right);
}
}
int main() {

int arry[7] = { 6,3,8,2,5,1,7 };
Tree tree;
tree.root = NULL;
printf("d%\n" + height(tree.root));
for (int i = 0; i < 7; i++) {
}
firorder(tree.root);
printf("--------\n");
denode(tree.root, 7);
firorder(tree.root);
printf("--------\n");
printf("d%\n" + height(tree.root));
printf("d%\n" + height(tree.root));
printf("--------\n");
balance(tree.root);
firorder(tree.root);
printf("--------\n");
printf("d%\n" + height(tree.root));
}
``````

• 好问题 提建议
• 收藏

#### 1条回答默认 最新

• 已采纳
``````printf("d%\n" + height(tree.root));
``````

printf中是 %d 不是 d% ， "%d\n" 后是逗号(,) 不是加号（+） ，改成

``````printf("%d\n" , height(tree.root));
``````

你题目的解答代码如下：

``````#include<stdio.h>
#include<stdlib.h>
typedef struct Node {
int data;
struct Node* left;
struct Node* right;
}Node;
typedef struct  {
Node* root;
}Tree;
void addnode(Tree* tree, int data) {//添加
Node* node = (Node*)malloc(sizeof(Node));
node->data = data;
node->left = NULL;
node->right = NULL;
if (tree->root == NULL) {
tree->root = node;
}
else {
Node* temp = (Node*)malloc(sizeof(Node));//存储当前根节点内容
temp = tree->root;
while (temp != NULL) {
if (temp->data > data) {
if (temp->left == NULL) {
temp->left = node;
return;
}
else {
temp = temp->left;
}
}
else {
if (temp->data < data) {
if (temp->right == NULL) {
temp->right = node;
return;
}
else {
temp = temp->right;
}
}
}
}
}
}
Node* findmin(Node* node) {//找到最小值
if (node == NULL)
return NULL;
while (node->left != NULL)
node = node->left;
return node;
}
Node *denode(Node* node, int data) {//删除
if (node ==NULL) {
return node;
}
else {
if (node->data > data) {
node->left = denode(node->left, data);
}
else if (node->data < data) {
node->right = denode(node->right, data);
}
else {
if (node->left == NULL && node->right == NULL) {
node = NULL;
}
else if (node->left != NULL && node->right == NULL) {
node = node->left;
}
else if (node->right != NULL && node->left == NULL) {
node = node->right;
}
else {
Node* pre = findmin(node->right);
node = denode(node,pre->data);
node->data = pre->data;
}
}
}
return node;
}
int height(Node* node) {//求树的高度
if (node == NULL) {
return -1;
}
else if (node->left == NULL && node->right == NULL) {
return 0;
}
else {
int left = height(node->left);
int right = height(node->right);
return left>right?(left + 1):(right + 1);
}
}
Node* leftrotation(Node* node) {//左旋
Node* temp = node->right;
node->right = temp->left;
temp->left = node;
return temp;
}
Node* rightrotation(Node* node) {//右旋
Node* temp = node->left;
node->left = temp->right;
temp->right = node;
return temp;
}
Node* balance(Node* current) {//平衡
if (current == NULL) {
return current;
}
if (height(current->left) - height(current->right) > 1) {
if (height(current->left->left) >= height(current->left->right)){
return rightrotation(current);
}
else {
return rightrotation(leftrotation(current->left));
}
}
if (height(current->right) - height(current->left) > 1) {
if (height(current->right->right) >= height(current->right->left)) {
return leftrotation(current);
}
else {
return leftrotation(rightrotation(current->right));
}
}
return current;
}
void firorder(Node* node) {//先序遍历
if (node != NULL) {
printf("%d\n", node->data);
firorder(node->left);
firorder(node->right);
}
}
int main() {
int arry[7] = { 6,3,8,2,5,1,7 };
Tree tree;
tree.root = NULL;
//printf("d%\n" + height(tree.root));
printf("%d\n" , height(tree.root));
for (int i = 0; i < 7; i++) {
}
firorder(tree.root);
printf("--------\n");
denode(tree.root, 7);
firorder(tree.root);
printf("--------\n");
//printf("d%\n" + height(tree.root));
printf("%d\n" , height(tree.root));
//printf("d%\n" + height(tree.root));
printf("%d\n" , height(tree.root));
printf("--------\n");
balance(tree.root);
firorder(tree.root);
printf("--------\n");
//printf("d%\n" + height(tree.root));
printf("%d\n" , height(tree.root));
}
``````

如有帮助，望采纳！谢谢!

编辑记录

已采纳该答案
评论
解决 1 无用
打赏 举报