【数据结构与算法】动态查找表（二叉排序树,二叉平衡树）详解

二叉排序树的数据结构。

struct TreeNode {ElemType data;TreeNode *left, *right;
};
using BiTree = TreeNode *;

结构体包含三个成员：

• data 是一个 ElemType 类型的变量，用于存储二叉搜索树节点的数据。
• left 是一个指向 TreeNode 类型的指针，用于指向二叉搜索树节点的左子节点。
• right 是一个指向 TreeNode 类型的指针，用于指向二叉搜索树节点的右子节点。

Status insertBST(BiTree &T, ElemType e) {if (!T) {T = (TreeNode *)malloc(sizeof(TreeNode));if (!T) {return ERROR;}T->data = e;T->left = T->right = nullptr;return OK;} else if (e < T->data) {return insertBST(T->left, e);} else if (e > T->data) {return insertBST(T->right, e);}return OK;
}void inorderInsert(BiTree &T, BiTree &dst) {if (T) {inorderInsert(T->left, dst);insertBST(dst, T->data);inorderInsert(T->right, dst);}
}

怎样从二叉排序树得到有序表。

中序遍历二叉排序树可得到一个关键字的有序序列。

void inorderPrint(BiTree &T) {if (T) {inorderPrint(T->left);cout << T->data << " ";inorderPrint(T->right);}
}

已知长度为 n 的表按表中元素顺序构造二叉平衡树，图示构造过程。