2019年08月19日(星期一)  农历:己亥年七月十九
  • 首页
  • JAVA
  • 数据结构之二叉树的Java实现

作者:三年。分类: JAVA

 树由边连接的节点构成。节点一般代表实体数据,如代表某一类数据。windows文件系统就可以看成是一棵树,比如C盘下有一些文件夹,这些文件夹下面又分别有一些文件夹,这样的关系其实就是一棵树。

根:树顶端的节点称为树的根,一棵树只有一个根。

父节点:每一个节点(除了根)都有一条边向上连接到另一个节点,上面的这个节点就称为下面节点的父节点。

子节点:与父节点相反。

子树:每个节点都可以作为子树的根,它和它所有的子节点,还有子节点的子节点都在子树中。

二叉树:如果树中每个节点最多有两个子节点,这样的树就称为二叉树。

二叉树的两个节点分别称为左子节点和右子节点。

Java中表示二叉树,可以用数组表示树,常用的方法是将节点存在无关联的容器中,再通过每个节点指向自己的子节点的引用来连接。

下面的方法用的就是后一种:

package test;

public class BinaryTree {

static Node root;

public Node find(int key) {

Node current = root;// 从根节点开始,用current保存正在查看的节点

while (current.idata != key) {

if (key < current.idata)

current = current.leftChild;

else

current = current.rightChild;

if (current == null)

return null;

}

return current;

}

public void insert(int key) {

// 首先要找到插入的地方

Node inode = new Node();

inode.idata = key;// 赋值

if (root == null)

root = inode;// 空树,则作为根节点

else {

Node current = root;// 从根节点开始比对

Node parent;

while (true) {

// 用parent来存储current,目的是在current变为空的时候,

// 才知道current== null时对应的上一个节点(parent)没有子节点

parent = current;

if (key < current.idata) {

current = current.leftChild;

if (current == null) {

parent.leftChild = inode;

return;

}

} else {

current = current.rightChild;

if (current == null) {

parent.rightChild = inode;

return;

}

}

}

}

}

/**

* 找到要删除的节点 有三种情况:1)该节点是页节点 ,2)该节点有一个子节点 ,3)该节点有两个子节点

* (删除好复杂,于是可以这样:在每一个节点上添加一个字段isDelete,若需要删除,则置为true)

*/

public boolean delete(int key) {

Node current = root;

Node parent = root;

boolean isLeftChild = true;

while (current.idata != key) {

parent = current;

if (key < current.idata) {

isLeftChild = true;

current = current.leftChild;

} else {

isLeftChild = false;

current = current.rightChild;

}

if (current == null)

return false;

}// 找到了节点

// 判断有无子节点

if (current.leftChild == null && current.rightChild == null) {

if (current == root)

root = null;

else if (isLeftChild)

parent.leftChild = null;

else

parent.rightChild = null;

} else if (current.rightChild == null) {

if (current == root)

root = current.leftChild;

else if (isLeftChild)

parent.leftChild = current.leftChild;

else

parent.rightChild = current.leftChild;

} else if (current.leftChild == null) {

if (current == root)

root = current.rightChild;

else if (isLeftChild)

parent.leftChild = current.rightChild;

else

parent.rightChild = current.rightChild;

}

/**

* 删除一个有两个子节点的节点,就不能用它的一个子节点来代替它,而要用它的中序后继代替该节点 如何找?

* 首先,找到初始节点的右子节点rcn,然后转到rcn的左子节点(有的话)rcnl,然后转到rcnl的左子节点,直到结束。

* 这里实际上要找的是比初始节点值大的集合中最小的那一个 如果初始节点的右子节点没有左子节点,那么其本身就是后继

*/

else {

Node success = getMidPostNode(current);

if (current == root)

root = success;

else if (isLeftChild)

parent.leftChild = success;

else

parent.rightChild = success;

success.leftChild = current.leftChild;

}

return true;

}

// 获取当前节点的中序后继

public Node getMidPostNode(Node delNode) {

Node successParent = delNode;

Node success = delNode;

Node current = delNode.rightChild;

while (current != null) {// 直到找到当前节点右子节点的最左子孙节点

successParent = success;

success = current;

current = current.leftChild;

}

if (success != delNode.rightChild) {

successParent.leftChild = success.rightChild;

success.rightChild = delNode.rightChild;

}

return success;

}

// 前序遍历

public void preTraverse(Node root) {

if (root != null) {

System.out.println(root.idata + " ");

preTraverse(root.leftChild);

preTraverse(root.rightChild);

}

}

// 中序遍历

public void midTraverse(Node root) {

if (root != null) {

midTraverse(root.leftChild);

System.out.println(root.idata + " ");

midTraverse(root.rightChild);

}

}

// 后续遍历

public void postTraverse(Node root) {

if (root != null) {

postTraverse(root.leftChild);

postTraverse(root.rightChild);

System.out.println(root.idata + " ");

}

}

// 递归地交换二叉树的左右子节点

public void swap(Node root) {

if(root == null)

return;

Node tmp = root.leftChild;

root.leftChild = root.rightChild;

root.rightChild = tmp;

swap(root.leftChild);

swap(root.rightChild);

}

public static void main(String[] args) {

BinaryTree bt = new BinaryTree();

bt.insert(1);

bt.insert(2);

bt.insert(3);

bt.insert(0);

bt.insert(5);

// Node f = bt.find(2);

// System.out.println("find = " + f.idata);

// bt.delete(3);

// bt.preTraverse(root);

// System.out.println("----------");

// bt.midTraverse(root);

// System.out.println("----------");

// bt.postTraverse(root);

// System.out.println("---------->");

bt.printBinaryTree(root, 0);

bt.swap(root);

bt.printBinaryTree(root, 0);

}

//递归打印树形二叉树

public static void printBinaryTree(Node root, int level){

if(root==null)

return;

printBinaryTree(root.rightChild, level+1);

if(level!=0){

for(int i=0;i<LEVEL-1;I++) pre }< rightChild; Node leftChild; idata; int { } level+1); printBinaryTree(root.leftChild, System.out.println(root.idata); else System.out.println(?|-------?+root.idata); System.out.print(?|\t?);><BR>

<BR>

<P></P>

温馨提示如有转载或引用以上内容之必要,敬请将本文链接作为出处标注,谢谢合作!

已有 0/1299 人参与

发表评论:



手Q扫描加入Java初学者群