二叉树的相关操作

二叉树

1、二叉树的建立

二叉树的结点添加，即为二叉树的建立
外部类为树，根节点，结点的个数
内部类（结点类，添加结点的方法（递归方法））
左节点，右结点，父节点

package binarytree;
public class BinaryTree {
    private Node root;
    private int count;
    public class Node{
        private int data;
        private Node left;
        private Node right;
        private Node parent;
        public Node() {
        }
        public Node(int data) {
            this.data = data;
        }
        /**
         * 添加结点，成功返回true,失败返回false
         */
        public boolean addNode(Node newNode){
           if (newNode.data<this.data){
               if(this.left==null){
                   this.left = newNode;
                   newNode.parent = this;
               }else {
                   return this.left.addNode(newNode);
               }
           }else if(newNode.data>this.data){
               if(this.right==null){
                   this.right = newNode;
                   newNode.parent = this;
               }else {
                   return this.right.addNode(newNode);
               }
           }else {
               return false;
           }
           return true;
        }
    }
    /**
     * 在结点外部添加方法
     */
    public boolean add(int data){
        Node node = new Node(data);
        //用来保存是否添加成功
        boolean flag = false;
        //判断二叉树是否为空
        if(this.root==null){
            this.root = node;
            flag = true;
        }else {
            flag = this.root.addNode(node);
        }
        if(flag){
            this.count++;
        }
        return flag;
    }
}

package binarytree;

import org.omg.Messaging.SyncScopeHelper;

public class Test1 {
    public static void main(String[] args) {
        BinaryTree binaryTree = new BinaryTree();
        System.out.println(binaryTree.add(10));
        System.out.println(binaryTree.add(11));
        System.out.println(binaryTree.add(11));
    }
}

2.判断结点是否包含某数据

package binarytree;
public class BinaryTree {
    private Node root;
    private int count;//添加结点的个数
    public class Node{
        private int data;
        private Node left;
        private Node right;
        private Node parent;
        public Node() {
        }
        public Node(int data) {
            this.data = data;
        }
        /**
         * 添加结点，成功返回true,失败返回false
         */
        public boolean addNode(Node newNode){
        //省略
           return true;
        }
        /**
         * 查找二叉树中是否包含某数据
         */
        public boolean contiansNode(int data){
            //从根节点开始
            if(this.data==data){
                return true;
            }else if(data>this.data){
                if(this.right!=null){
                    return this.right.contiansNode(data);
                }
            }else if(data<this.data){
                if (this.left!=null){
                    return this.left.contiansNode(data);
                }
            }
            return false;
        }

    }
    /**
     * 在外部添加增加结点的方法
     */
    public boolean add(int data){
       省略
    }

    /***
     * 查看节点中是否包含指定数据
     * @param data
     * @return
     */
    public boolean contains(int data){
        if(this.root == null){
            return false;
        }else {
            return this.root.contiansNode(data);
        }
    }
}
package binarytree;

import org.omg.Messaging.SyncScopeHelper;

public class Test1 {
    public static void main(String[] args) {
        BinaryTree binaryTree = new BinaryTree();
        binaryTree.add(34);
        binaryTree.add(35);
        binaryTree.add(39);
        binaryTree.add(78);
        System.out.println(binaryTree.contains(35));
        System.out.println(binaryTree.contains(351));
    }
}

小结：无论是添加结点，还是判断是否包含。都是从根节点开始判断。然后通过this.root.方法名（）调用方法

二叉树的遍历

package binarytree;

import org.omg.Messaging.SyncScopeHelper;

import javax.xml.bind.SchemaOutputResolver;

public class BinaryTree {
    private Node root;
    private int count;//添加结点的个数
    public class Node{
        private int data;
        private Node left;
        private Node right;
        private Node parent;
        public Node() {
        }
        public Node(int data) {
            this.data = data;
        }
        /**
         * 添加结点，成功返回true,失败返回false
         */
        public boolean addNode(Node newNode){
           if (newNode.data<this.data){
               if(this.left==null){
                   this.left = newNode;
                   newNode.parent = this;
               }else {
                   return this.left.addNode(newNode);
               }
           }else if(newNode.data>this.data){
               if(this.right==null){
                   this.right = newNode;
                   newNode.parent = this;
               }else {
                   return this.right.addNode(newNode);
               }
           }else {
               return false;
           }
           return true;
        }
        /**
         * 查找二叉树中是否包含某数据
         */
        public boolean contiansNode(int data){
            //从根节点开始
            if(this.data==data){
                return true;
            }else if(data>this.data){
                if(this.right!=null){
                    return this.right.contiansNode(data);
                }
            }else if(data<this.data){
                if (this.left!=null){
                    return this.left.contiansNode(data);
                }
            }
            return false;
        }
        /**
         * 遍历二叉树
         * 1、先序遍历，先根遍历
         */
        public void transFirst(){
            //先从根节点开始判断
            System.out.print(this.data+" ");
            //从左至右
            if(this.left!=null){
                this.left.transFirst();
            }if (this.right!=null){
                this.right.transFirst();
            }
        }
        /**
         * 中序遍历
         */
        public void transMiddle(){
            if (this.left!=null){
                this.left.transMiddle();
            }
            System.out.print(this.data+" ");
            if (this.right!= null){
                this.right.transMiddle();
            }
        }
        /**
         * 后序遍历
         */
        public void transLast(){
            if (this.left!=null){
                this.left.transLast();
            }
            if (this.right!=null){
                this.right.transLast();
            }
            System.out.print(this.data+" ");
        }
        /**
         * 层序遍历(或许补充)
         */
        public void transCx(){

        }



    }
    /**
     * 在外部添加增加结点的方法
     */
    public boolean add(int data){
        Node node = new Node(data);
        //用来保存是否添加成功
        boolean flag = false;
        //判断二叉树是否为空
        if(this.root==null){
            this.root = node;
            flag = true;
        }else {
            flag = this.root.addNode(node);
        }
        if(flag){
            this.count++;
        }
        return flag;
    }

    /***
     * 查看节点中是否包含指定数据
     * @param data
     * @return
     */
    public boolean contains(int data){
        if(this.root == null){
            return false;
        }else {
            return this.root.contiansNode(data);
        }
    }

    /**
     * 先序遍历
     */
    public void transingFirst(){
        if(this.root == null){
            System.out.println("二叉树为空");
        }else {
            this.root.transFirst();
        }
    }
    /**
     * 中序遍历
     */
    public void transingMiddle(){
        if (this.root!=null){
            this.root.transMiddle();
        }
    }
    /**
     * 后序遍历
     */
    public void transingLast(){
        if(this.root != null){
            this.root.transLast();
        }
    }

}

package binarytree;
public class Test1 {
    public static void main(String[] args) {
        BinaryTree binaryTree = new BinaryTree();
        binaryTree.add(23);
        binaryTree.add(32);
        binaryTree.add(10);
        binaryTree.add(9);
        binaryTree.add(78);
        binaryTree.add(15);
        binaryTree.add(90);
        binaryTree.add(85);
        binaryTree.add(100);
        System.out.print("先序遍历结果为：");
        binaryTree.transingFirst();
        System.out.println();
        System.out.print("中序遍历结果为：");
        binaryTree.transingMiddle();
        System.out.println();
        System.out.print("后遍历结果为：");
        binaryTree.transingLast();
    }
}

最后

以上就是健壮小刺猬最近收集整理的关于二叉树的相关操作的全部内容，更多相关二叉树内容请搜索靠谱客的其他文章。