二叉排序树的打印输出
时间: 2023-08-21 22:13:38 浏览: 109
二叉排序树(Binary Search Tree)的打印输出一般有三种方式:中序遍历、前序遍历和后序遍历。
中序遍历(Inorder Traversal)输出的结果是将树中所有节点按从小到大的顺序输出。
前序遍历(Preorder Traversal)输出的结果是先输出根节点,再输出左子树,最后输出右子树。
后序遍历(Postorder Traversal)输出的结果是先输出左子树,再输出右子树,最后输出根节点。
以下是二叉排序树的中序遍历的打印输出代码示例(假设节点中存储的是整数):
```c++
void inorderTraversal(Node* root) {
if (root == nullptr) {
return;
}
inorderTraversal(root->left); // 先遍历左子树
std::cout << root->val << " "; // 输出当前节点值
inorderTraversal(root->right); // 再遍历右子树
}
```
如果需要使用前序遍历或后序遍历打印输出,只需要将上述代码中的 `inorderTraversal` 改为 `preorderTraversal` 或 `postorderTraversal` 即可。
相关问题
Java树状打印输出二叉排序树
以下是Java中树状打印输出二叉排序树的代码:
```java
public class BinarySortTreePrinter {
public static void printNode(Node root) {
int maxLevel = BinarySortTreePrinter.maxLevel(root);
printNodeInternal(Collections.singletonList(root), 1, maxLevel);
}
private static void printNodeInternal(List<Node> nodes, int level, int maxLevel) {
if (nodes.isEmpty() || BinarySortTreePrinter.isAllElementsNull(nodes))
return;
int floor = maxLevel - level;
int endgeLines = (int) Math.pow(2, (Math.max(floor - 1, 0)));
int firstSpaces = (int) Math.pow(2, (floor)) - 1;
int betweenSpaces = (int) Math.pow(2, (floor + 1)) - 1;
BinarySortTreePrinter.printWhitespaces(firstSpaces);
List<Node> newNodes = new ArrayList<Node>();
for (Node node : nodes) {
if (node != null) {
System.out.print(node.getData());
newNodes.add(node.getLeft());
newNodes.add(node.getRight());
} else {
newNodes.add(null);
newNodes.add(null);
System.out.print(" ");
}
BinarySortTreePrinter.printWhitespaces(betweenSpaces);
}
System.out.println("");
for (int i = 1; i <= endgeLines; i++) {
for (int j = 0; j < nodes.size(); j++) {
BinarySortTreePrinter.printWhitespaces(firstSpaces - i);
if (nodes.get(j) == null) {
BinarySortTreePrinter.printWhitespaces(endgeLines + endgeLines + i + 1);
continue;
}
if (nodes.get(j).getLeft() != null)
System.out.print("/");
else
BinarySortTreePrinter.printWhitespaces(1);
BinarySortTreePrinter.printWhitespaces(i + i - 1);
if (nodes.get(j).getRight() != null)
System.out.print("\\");
else
BinarySortTreePrinter.printWhitespaces(1);
BinarySortTreePrinter.printWhitespaces(endgeLines + endgeLines - i);
}
System.out.println("");
}
printNodeInternal(newNodes, level + 1, maxLevel);
}
private static void printWhitespaces(int count) {
for (int i = 0; i < count; i++)
System.out.print(" ");
}
private static int maxLevel(Node node) {
if (node == null)
return 0;
return Math.max(BinarySortTreePrinter.maxLevel(node.getLeft()), BinarySortTreePrinter.maxLevel(node.getRight())) + 1;
}
private static boolean isAllElementsNull(List list) {
for (Object object : list) {
if (object != null)
return false;
}
return true;
}
}
```
使用该代码,您可以将二叉排序树以树状结构的形式打印输出。只需在您的代码中调用`BinarySortTreePrinter.printNode(root)`即可。
根据二叉排序树的抽象数据类型的定义,使用二叉链表实现一个二叉排序树。二叉排序树的基本功能:1、二叉排序树的建立;2、二叉排序树的查找;3、二叉排序树的插入;4、二叉排序树的删除;5、二叉排序树的销毁;6、其他:自定义操作。编写测试main()函数测试二叉排序树的正确性。
好的,以下是使用二叉链表实现二叉排序树的代码实现,并附带测试main()函数。
```c++
#include <iostream>
using namespace std;
// 定义二叉排序树的结构体
typedef struct BSTNode{
int data;
struct BSTNode* left;
struct BSTNode* right;
}BSTNode, *BSTree;
// 初始化二叉排序树
void InitBSTree(BSTree &T) {
T = NULL;
}
// 创建二叉排序树
void CreateBSTree(BSTree &T, int a[], int n) {
for (int i = 0; i < n; i++) {
BSTNode* p = new BSTNode;
p->data = a[i];
p->left = NULL;
p->right = NULL;
// 插入节点
if (T == NULL) {
T = p;
} else {
BSTNode* q = T;
while (true) {
if (p->data < q->data) {
if (q->left == NULL) {
q->left = p;
break;
} else {
q = q->left;
}
} else {
if (q->right == NULL) {
q->right = p;
break;
} else {
q = q->right;
}
}
}
}
}
}
// 查找二叉排序树中是否有指定元素
BSTNode* SearchBSTree(BSTree T, int key) {
if (T == NULL || T->data == key) {
return T;
} else if (key < T->data) {
return SearchBSTree(T->left, key);
} else {
return SearchBSTree(T->right, key);
}
}
// 插入元素到二叉排序树
bool InsertBSTree(BSTree &T, int key) {
if (T == NULL) {
BSTNode* p = new BSTNode;
p->data = key;
p->left = NULL;
p->right = NULL;
T = p;
return true;
} else if (T->data == key) {
return false; // 已存在相同元素
} else if (key < T->data) {
return InsertBSTree(T->left, key);
} else {
return InsertBSTree(T->right, key);
}
}
// 删除二叉排序树中指定元素
bool DeleteBSTree(BSTree &T, int key) {
if (T == NULL) {
return false;
} else if (key < T->data) {
return DeleteBSTree(T->left, key);
} else if (key > T->data) {
return DeleteBSTree(T->right, key);
} else {
if (T->left == NULL && T->right == NULL) {
delete T;
T = NULL;
} else if (T->left == NULL) {
BSTNode* p = T;
T = T->right;
delete p;
} else if (T->right == NULL) {
BSTNode* p = T;
T = T->left;
delete p;
} else {
BSTNode* p = T->right;
while (p->left != NULL) {
p = p->left;
}
T->data = p->data;
DeleteBSTree(T->right, p->data);
}
return true;
}
}
// 销毁二叉排序树
void DestroyBSTree(BSTree &T) {
if (T != NULL) {
DestroyBSTree(T->left);
DestroyBSTree(T->right);
delete T;
T = NULL;
}
}
// 自定义操作:中序遍历并输出二叉排序树的所有节点值
void PrintBSTree(BSTree T) {
if (T != NULL) {
PrintBSTree(T->left);
cout << T->data << " ";
PrintBSTree(T->right);
}
}
int main() {
BSTree T;
InitBSTree(T);
int a[] = {6, 3, 8, 2, 5, 7, 9};
CreateBSTree(T, a, 7);
// 测试查找
BSTNode* node = SearchBSTree(T, 5);
if (node != NULL) {
cout << "find " << node->data << endl;
} else {
cout << "not find" << endl;
}
// 测试插入
bool res = InsertBSTree(T, 4);
if (res) {
cout << "insert success" << endl;
} else {
cout << "insert fail" << endl;
}
// 测试删除
res = DeleteBSTree(T, 5);
if (res) {
cout << "delete success" << endl;
} else {
cout << "delete fail" << endl;
}
// 打印二叉排序树
PrintBSTree(T);
// 销毁二叉排序树
DestroyBSTree(T);
return 0;
}
```
输出结果:
```
find 5
insert success
delete success
2 3 4 6 7 8 9
```