二叉链表(双叉链表)实现二叉树-白红宇

强烈建议你试试无所不能的chatGPT，快点击我

二叉链表(双叉链表)实现二叉树

阅读量：5365 次

发布时间：2019-06-15

本文共 13864 字，大约阅读时间需要 46 分钟。

1.二叉树的节点声明

1 package com.neusoft.Tree; 2 /** 3  * @author zhao-chj 4  * 保存Node节点的数据域指针域 5  */ 6 public class BiTreeNode { 7     public Object data;//数据域 8     public BiTreeNode lchild,rchild; 9     public BiTreeNode() {10         // TODO 构造函数11         this(null);12     }13     public BiTreeNode(Object data){14         this(data,null,null);15     }16     public BiTreeNode(Object data,BiTreeNode lchild,BiTreeNode rchild){17         this.data=data;18         this.lchild=lchild;19         this.rchild=rchild;20     }21 }

点击+复制代码

1 package com.neusoft.Tree; 2 /** 3  * @author zhao-chj 4  * 保存Node节点的数据域指针域 5  */ 6 public class BiTreeNode { 7     public Object data;//数据域 8     public BiTreeNode lchild,rchild; 9     public BiTreeNode() {10         // TODO 构造函数11         this(null);12     }13     public BiTreeNode(Object data){14         this(data,null,null);15     }16     public BiTreeNode(Object data,BiTreeNode lchild,BiTreeNode rchild){17         this.data=data;18         this.lchild=lchild;19         this.rchild=rchild;20     }21 }

点击+复制代码

2.二叉树的各种操作(遍历及节点的统计)

1 package com.neusoft.Tree;  2 import com.neusoft.Queue.LinkQueue;  3 import com.neusoft.stack.LinkStack;  4 /**  5  * @author zhao-chj  6  * 二叉链表存储二叉树  7  * 1.导入链表和链栈的工具类  8  */  9 public class BiTree { 10     private BiTreeNode root; 11     public BiTreeNode getRoot() { 12         return root; 13     } 14     public void setRoot(BiTreeNode root) { 15         this.root = root; 16     } 17     public BiTree(){ 18         this.root=null; 19     } 20     public BiTree(BiTreeNode root){ 21         this.root=root; 22     } 23     //由先跟遍历和中根遍历创建一棵二叉树算法 24     /** 25      * @param preOrder 代表整棵树的先跟遍历 26      * @param inOrder  整棵树的中根遍历 27      * @param preIndex  先跟遍历从preOrder字符串中的开始位置 28      * @param inIndex  是中根遍历从字符串inOrder中 的开始位置 29      * @param count 树节点的个数 30      */ 31     public BiTree(String preOrder,String inOrder,int preIndex, 32             int inIndex,int count){ 33         if (count >0) {
   //先跟和中跟非空 34             //取出先跟遍历字符串中的第一个元素作为根节点 35             char r= preOrder.charAt(preIndex); 36             int i=0; 37             for(;i

点击+可复制代码

1 package com.neusoft.Tree;  2 import com.neusoft.Queue.LinkQueue;  3 import com.neusoft.stack.LinkStack;  4 /**  5  * @author zhao-chj  6  * 二叉链表存储二叉树  7  * 1.导入链表和链栈的工具类  8  */  9 public class BiTree { 10     private BiTreeNode root; 11     public BiTreeNode getRoot() { 12         return root; 13     } 14     public void setRoot(BiTreeNode root) { 15         this.root = root; 16     } 17     public BiTree(){ 18         this.root=null; 19     } 20     public BiTree(BiTreeNode root){ 21         this.root=root; 22     } 23     //由先跟遍历和中根遍历创建一棵二叉树算法 24     /** 25      * @param preOrder 代表整棵树的先跟遍历 26      * @param inOrder  整棵树的中根遍历 27      * @param preIndex  先跟遍历从preOrder字符串中的开始位置 28      * @param inIndex  是中根遍历从字符串inOrder中 的开始位置 29      * @param count 树节点的个数 30      */ 31     public BiTree(String preOrder,String inOrder,int preIndex, 32             int inIndex,int count){ 33         if (count >0) {
    //先跟和中跟非空 34             //取出先跟遍历字符串中的第一个元素作为根节点 35             char r= preOrder.charAt(preIndex); 36             int i=0; 37             for(;i

点击+复制代码

3.模拟创建树的代码

1 package com.neusoft.Tree; 2 /* 3  * 初始化一棵树 4  */ 5 public class BiTreeCreate { 6    public BiTree createBitree(){ 7        BiTreeNode A=new BiTreeNode('A'); 8        BiTreeNode B=new BiTreeNode('B'); 9        BiTreeNode C=new BiTreeNode('C');10        BiTreeNode D=new BiTreeNode('D');11        BiTreeNode E=new BiTreeNode('E');12        BiTreeNode F=new BiTreeNode('F',null,A);13        BiTreeNode G=new BiTreeNode('G',B,null);14        BiTreeNode H=new BiTreeNode('H',G,null);15        BiTreeNode I=new BiTreeNode('I',null,E);16        BiTreeNode J=new BiTreeNode('J',D,I);17        BiTreeNode K=new BiTreeNode('K',F,H);18        BiTreeNode L=new BiTreeNode('L',C,J);19        BiTreeNode root=new BiTreeNode('M',K,L);20        return new BiTree(root);21    }22    public BiTree createBitree2(){23        BiTreeNode d=new BiTreeNode('D');24        BiTreeNode g=new BiTreeNode('G');25        BiTreeNode h=new BiTreeNode('H');26        BiTreeNode e=new BiTreeNode('E',g,null);27        BiTreeNode b=new BiTreeNode('B',d,e);28        BiTreeNode f=new BiTreeNode('F',null,h);29        BiTreeNode c=new BiTreeNode('C',f,null);30        BiTreeNode a=new BiTreeNode('A',b,c);31        return  new BiTree(a);32    }33 }

点击+可复制代码

1 package com.neusoft.Tree; 2 /* 3  * 初始化一棵树 4  */ 5 public class BiTreeCreate { 6    public BiTree createBitree(){ 7        BiTreeNode A=new BiTreeNode('A'); 8        BiTreeNode B=new BiTreeNode('B'); 9        BiTreeNode C=new BiTreeNode('C');10        BiTreeNode D=new BiTreeNode('D');11        BiTreeNode E=new BiTreeNode('E');12        BiTreeNode F=new BiTreeNode('F',null,A);13        BiTreeNode G=new BiTreeNode('G',B,null);14        BiTreeNode H=new BiTreeNode('H',G,null);15        BiTreeNode I=new BiTreeNode('I',null,E);16        BiTreeNode J=new BiTreeNode('J',D,I);17        BiTreeNode K=new BiTreeNode('K',F,H);18        BiTreeNode L=new BiTreeNode('L',C,J);19        BiTreeNode root=new BiTreeNode('M',K,L);20        return new BiTree(root);21    }22    public BiTree createBitree2(){23        BiTreeNode d=new BiTreeNode('D');24        BiTreeNode g=new BiTreeNode('G');25        BiTreeNode h=new BiTreeNode('H');26        BiTreeNode e=new BiTreeNode('E',g,null);27        BiTreeNode b=new BiTreeNode('B',d,e);28        BiTreeNode f=new BiTreeNode('F',null,h);29        BiTreeNode c=new BiTreeNode('C',f,null);30        BiTreeNode a=new BiTreeNode('A',b,c);31        return  new BiTree(a);32    }33 }

点击+可复制代码

4.二叉树的二叉链表表示法测试代码

1 package com.neusoft.Tree; 2  3 public class DebugBiTree { 4     public BiTree createBitree2(){ 5            BiTreeNode d=new BiTreeNode('D'); 6            BiTreeNode g=new BiTreeNode('G'); 7            BiTreeNode h=new BiTreeNode('H'); 8            BiTreeNode e=new BiTreeNode('E',g,null); 9            BiTreeNode b=new BiTreeNode('B',d,e);10            BiTreeNode f=new BiTreeNode('F',null,h);11            BiTreeNode c=new BiTreeNode('C',f,null);12            BiTreeNode a=new BiTreeNode('A',b,c);13            return  new BiTree(a);14        }15     public static void main(String[] args) {16         DebugBiTree debug=new DebugBiTree();17         BiTree biTree=debug.createBitree2();18         BiTreeNode root=biTree.getRoot();19         //Debug先根遍历20         System.out.println("(递归)先根遍历序列为：");21         biTree.preOrderTraverse(root);22         System.out.println();23         //Debug中根遍历24         System.out.println("(递归)中根遍历序列为：");25         biTree.inRootTraverse(root);26         System.out.println();27         //Debug后根遍历28         System.out.println("(递归)后根遍历序列为：");29         biTree.postRootTraverse(root);30         System.out.println();31         //Debug层次遍历32         System.out.println("(层次遍历序列为：)");33         biTree.levelTraverse();34         System.out.println();35     }36 }

点击+可复制代码

1 package com.neusoft.Tree; 2  3 public class DebugBiTree { 4     public BiTree createBitree2(){ 5            BiTreeNode d=new BiTreeNode('D'); 6            BiTreeNode g=new BiTreeNode('G'); 7            BiTreeNode h=new BiTreeNode('H'); 8            BiTreeNode e=new BiTreeNode('E',g,null); 9            BiTreeNode b=new BiTreeNode('B',d,e);10            BiTreeNode f=new BiTreeNode('F',null,h);11            BiTreeNode c=new BiTreeNode('C',f,null);12            BiTreeNode a=new BiTreeNode('A',b,c);13            return  new BiTree(a);14        }15     public static void main(String[] args) {16         DebugBiTree debug=new DebugBiTree();17         BiTree biTree=debug.createBitree2();18         BiTreeNode root=biTree.getRoot();19         //Debug先根遍历20         System.out.println("(递归)先根遍历序列为：");21         biTree.preOrderTraverse(root);22         System.out.println();23         //Debug中根遍历24         System.out.println("(递归)中根遍历序列为：");25         biTree.inRootTraverse(root);26         System.out.println();27         //Debug后根遍历28         System.out.println("(递归)后根遍历序列为：");29         biTree.postRootTraverse(root);30         System.out.println();31         //Debug层次遍历32         System.out.println("(层次遍历序列为：)");33         biTree.levelTraverse();34         System.out.println();35     }36 }

点击+可复制代码

5.运行结果显示

6.补充：二叉树的非递归实现及测试

（1）二叉树的非递归实现

1 package com.neusoft.Tree;  2 import com.neusoft.Queue.LinkQueue;  3 import com.neusoft.stack.LinkStack;  4 /**  5  * @author zhao-chj  6  * 二叉链表存储二叉树  7  * 1.导入链表和链栈的工具类  8  */  9 public class BiTree { 10     private BiTreeNode root; 11     public BiTreeNode getRoot() { 12         return root; 13     } 14     public void setRoot(BiTreeNode root) { 15         this.root = root; 16     } 17     public BiTree(){ 18         this.root=null; 19     } 20     public BiTree(BiTreeNode root){ 21         this.root=root; 22     } 23     //由先跟遍历和中根遍历创建一棵二叉树算法 24     /** 25      * @param preOrder 代表整棵树的先跟遍历 26      * @param inOrder  整棵树的中根遍历 27      * @param preIndex  先跟遍历从preOrder字符串中的开始位置 28      * @param inIndex  是中根遍历从字符串inOrder中 的开始位置 29      * @param count 树节点的个数 30      */ 31     public BiTree(String preOrder,String inOrder,int preIndex, 32             int inIndex,int count){ 33         if (count >0) {
   //先跟和中跟非空 34             //取出先跟遍历字符串中的第一个元素作为根节点 35             char r= preOrder.charAt(preIndex); 36             int i=0; 37             for(;i

二叉链表的递归实现和非递归实现

1 package com.neusoft.Tree;  2 import com.neusoft.Queue.LinkQueue;  3 import com.neusoft.stack.LinkStack;  4 /**  5  * @author zhao-chj  6  * 二叉链表存储二叉树  7  * 1.导入链表和链栈的工具类  8  */  9 public class BiTree { 10     private BiTreeNode root; 11     public BiTreeNode getRoot() { 12         return root; 13     } 14     public void setRoot(BiTreeNode root) { 15         this.root = root; 16     } 17     public BiTree(){ 18         this.root=null; 19     } 20     public BiTree(BiTreeNode root){ 21         this.root=root; 22     } 23     //由先跟遍历和中根遍历创建一棵二叉树算法 24     /** 25      * @param preOrder 代表整棵树的先跟遍历 26      * @param inOrder  整棵树的中根遍历 27      * @param preIndex  先跟遍历从preOrder字符串中的开始位置 28      * @param inIndex  是中根遍历从字符串inOrder中 的开始位置 29      * @param count 树节点的个数 30      */ 31     public BiTree(String preOrder,String inOrder,int preIndex, 32             int inIndex,int count){ 33         if (count >0) {
    //先跟和中跟非空 34             //取出先跟遍历字符串中的第一个元素作为根节点 35             char r= preOrder.charAt(preIndex); 36             int i=0; 37             for(;i

点击+复制代码

（2）测试代码

1 package com.neusoft.Tree; 2  3 public class DebugBiTree { 4     public BiTree createBitree2(){ 5            BiTreeNode d=new BiTreeNode('D'); 6            BiTreeNode g=new BiTreeNode('G'); 7            BiTreeNode h=new BiTreeNode('H'); 8            BiTreeNode e=new BiTreeNode('E',g,null); 9            BiTreeNode b=new BiTreeNode('B',d,e);10            BiTreeNode f=new BiTreeNode('F',null,h);11            BiTreeNode c=new BiTreeNode('C',f,null);12            BiTreeNode a=new BiTreeNode('A',b,c);13            return  new BiTree(a);14        }15     public static void main(String[] args) {16         DebugBiTree debug=new DebugBiTree();17         BiTree biTree=debug.createBitree2();18         BiTreeNode root=biTree.getRoot();19         //Debug先根遍历20         System.out.println("(递归)先根遍历序列为：");21         biTree.preOrderTraverse(root);22         System.out.println();23         System.out.println("(非递归)先根遍历序列为：");24         biTree.preRootTraverse();25         System.out.println();26         //Debug中根遍历27         System.out.println("(递归)中根遍历序列为：");28         biTree.inRootTraverse(root);29         System.out.println();30         System.out.println("(非递归)中根遍历序列为：");31         biTree.inRootTraverse();32         System.out.println();33         //Debug后根遍历34         System.out.println("(递归)后根遍历序列为：");35         biTree.postRootTraverse(root);36         System.out.println();37         System.out.println("(非递归)后根遍历序列为：");38         biTree.postRootTraverse();39         System.out.println();40         //Debug层次遍历41         System.out.println("(层次遍历序列为：)");42         biTree.levelTraverse();43         System.out.println();44     }45 }

测试二叉树的递归和非递归实现方式

1 package com.neusoft.Tree; 2  3 public class DebugBiTree { 4     public BiTree createBitree2(){ 5            BiTreeNode d=new BiTreeNode('D'); 6            BiTreeNode g=new BiTreeNode('G'); 7            BiTreeNode h=new BiTreeNode('H'); 8            BiTreeNode e=new BiTreeNode('E',g,null); 9            BiTreeNode b=new BiTreeNode('B',d,e);10            BiTreeNode f=new BiTreeNode('F',null,h);11            BiTreeNode c=new BiTreeNode('C',f,null);12            BiTreeNode a=new BiTreeNode('A',b,c);13            return  new BiTree(a);14        }15     public static void main(String[] args) {16         DebugBiTree debug=new DebugBiTree();17         BiTree biTree=debug.createBitree2();18         BiTreeNode root=biTree.getRoot();19         //Debug先根遍历20         System.out.println("(递归)先根遍历序列为：");21         biTree.preOrderTraverse(root);22         System.out.println();23         System.out.println("(非递归)先根遍历序列为：");24         biTree.preRootTraverse();25         System.out.println();26         //Debug中根遍历27         System.out.println("(递归)中根遍历序列为：");28         biTree.inRootTraverse(root);29         System.out.println();30         System.out.println("(非递归)中根遍历序列为：");31         biTree.inRootTraverse();32         System.out.println();33         //Debug后根遍历34         System.out.println("(递归)后根遍历序列为：");35         biTree.postRootTraverse(root);36         System.out.println();37         System.out.println("(非递归)后根遍历序列为：");38         biTree.postRootTraverse();39         System.out.println();40         //Debug层次遍历41         System.out.println("(层次遍历序列为：)");42         biTree.levelTraverse();43         System.out.println();44     }45 }

点击+复制代码

（3）验证代码

转载于:https://www.cnblogs.com/jackchen-Net/p/6800065.html

你可能感兴趣的文章

python中的网页标签等字符处理

Linux常用命令(十二)

Linux常用命令(十五)

Linux常用命令(十四)

Linux常用命令(十七)

Linux常用命令(十六)

day 3 修改haproxy.cfg 作业

sim usim Uim 区别

网页中插入透明Flash的方法和技巧

动态内存申请函数选择(realloc、malloc 、alloca、 calloc）

获取元素属性get_attribute

【BZOJ】【2132】圈地计划

ARM 的Thumb状态测试

Java有没有goto？

（转）makefile 的用法

求不相邻金币相加和的最大值--动态规划1

[转][osg]探索未知种族之osg类生物【目录】

四十九. Zabbix报警机制、 Zabbix进阶操作、监控案例

元类中__new__ 与 __init__的区别--day27

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！-- 愿君每日到此一游！

当前时间: 2024-11-30 09:54:30 当前IP: 18.224.55.193 联系邮箱:javaeecc@qq.com Copyright © 2020 - 2022 baihongyu.com 京ICP备2021015314号-2

强烈建议你试试无所不能的CHAT-GPT，快点击我

强烈建议你试试无所不能的CHAT-GPT，快点击我