2023年6月22日发(作者：)

实验报告

系部 计算机系

课程名称

实验名称

班级 学号 姓名

实验日期 2019-11-14

成绩

数据结构

二叉树的操作

实验目的：

1 理解二叉树的类型定义与性质；

2、掌握二叉树的二叉链表存储结构的表示和实现方法；

3掌握二叉树遍历操作的算法实现。

实验条件：

eclipse

实验内容与步骤：

内容：

1. 建立二叉树的二叉链表 存储结构；

2. 实现二叉树的先根，中根和后根三种遍历操作。

3. 实现二叉搜索树及相关操作。

步骤：

1. 建立节点类

public class BinaryTreeNode{

private T data;

private BinaryTreeNode lchild,rchild;

public BinaryTreeNode(T data, BinaryTreeNode lchild,

BinaryTreeNode rchild) {

super();

= data;

= lchild;

= rchild;

}

public BinaryTreeNode(T data) {

=data;

=null;

=null;

}

public BinaryTreeNode() {

this(null);

}

2. 先序，中序，后序遍历

private void preorder(BinaryTreeNode p) {

if(p!=null) {

(a()+"t");

preorder(ild());

preorder(ild());

}

}

private void inorder(BinaryTreeNode p) {

if(p!=null) {

inorder(ild());

(a()+"t");

inorder(ild());

}

}

public void inorder() {

n("中序遍历：");

inorder(root);

}

private void postorder(BinaryTreeNode p) {

if(p!=null) {

postorder(ild());

postorder(ild());

(a()+"t");

}

}

public void postorder() {

n("后序遍历：");

postorder(root);

}

3. 二叉搜索树

public void insearch(int x) {

if(root==null) {

root=new Node(x);

return;

}

Node p=root;

while (p!=null) {

if(x>a()) {

if(ht()==null) {

ht(new Node(x));

return;

}

p=ht();

}

else {

if (t()==null) {

t (new Node(x));

return;

}

}

p=t();

}

}

运行结果：

二叉搜索树：

实验总结：

通过这次实验，我掌握了二叉树的结构原理以及它的先序，中序，后序遍历，运用递归的方法实现和不用递归的方法实现。二叉搜索树的原理和算法实现，根据二叉搜索树的特点，运用二分法进行二叉搜索树的一系列操作。 附：源程序：

二叉树：

package tree;

import ;

import List;

public class BinaryTree{

private BinaryTreeNode root;

public BinaryTree(BinaryTreeNode root) {

}

public BinaryTree() {

}

public BinaryTreeNode getRoot() {

}

public void setRoot(BinaryTreeNode root) {

}

@Override

public String toString() {

}

private void preorder(BinaryTreeNode p) {

}

public void preorder() {

}

n("先序遍历：");

preorder(root);

if(p!=null) {

(a()+"t");

return "BinaryTree [root=" + root + "]";

= root;

return root;

=null;

super();

= root;

preorder(ild());

preorder(ild());

}

private void inorder(BinaryTreeNode p) {

}

public void inorder() {

}

private void postorder(BinaryTreeNode p) {

}

public void postorder() {

}

private int size(BinaryTreeNode p) {

}

public int size() {

}

private int height(BinaryTreeNode p) {

n("节点数为：");

return size(root);

if(p==null) {

}

int lchildsize=size(ild());

int rchildsize=size(ild());

return lchildsize+rchildsize+1;

return 0;

n("后序遍历：");

postorder(root);

if(p!=null) {

}

postorder(ild());

postorder(ild());

(a()+"t");

n("中序遍历：");

inorder(root);

if(p!=null) {

inorder(ild());

(a()+"t");

inorder(ild());

}

}

if (p==null) {

}

int hl=height(ild());

int hr=height(ild());

return (hl>hr)?hl+1:hr+1;

return 0；

public int height() {

}

public void showleaves(BinaryTreeNode p) {

}

public void pretravel() {

BinaryTreeNode p=root;

Deque mystack=new LinkedList();

if(p!=null) {

(p);

while(!y()) {

}

p=();

(a()+" ");

if(ild()!=null) {

}

if (ild()!=null) {

}

(ild());

(ild());

if (p!=null) {

}

if (ild()==null&&ild()==null) {

}

showleaves(ild());

showleaves(ild());

(a()+"t");

n("高度为：");

return height(root);

}

}

}

二叉搜索树

package tree;

public class BinartSearchtree {

private Node root;

public BinartSearchtree(Node root) {

super();

= root;

}

public BinartSearchtree() {

root=null;

}

public void insearch(int x) {

if(root==null) {

root=new Node(x);

return;

}

Node p=root;

while (p!=null) {

if(x>a()) {

if(ht()==null) {

ht(new Node(x));

return;

}

p=ht();

}

else {

if (t()==null) {

t (new Node(x));

return;

}

p=t();

}

}

}

public Node find(int x) {

Node p=root;

while(p!=null) {

if(x>a()) {

p=ht();

}

else if(x

p=t();

}

else { return p;

}

}

return null;

}

public void preorder() {

n("先序遍历：");

preorder(root);

}

private void preorder(Node p) {

if(p!=null) {

(a()+" ");

preorder(t());

preorder(ht());

}

}

public Node minNode(Node p) {

// Node p=root;

while(t()!=null) {

p=t();

}

return p;

}

public Node maxNode(Node p) {

// Node p=root;

while(ht()!=null) {

p=ht();

}

return p;

}

public Node delete(int x, Node p) {

Node temp;

if(p==null) {

n("error");

return null;

}

else if (x

t(delete(x, t()));

}

else if (x>a()) {

ht(delete(x, ht()));

}

else {if (t()!=null&&ht()!=null) {

temp=maxNode(t());

a(a());

t(delete(a(), t()));

}

else {

if (t()==null) {

p=ht();

}

}

}

else if (ht()==null) {

p=ht();

}

return p;

}