©2020-2024 ioDraw All rights reserved
二叉树的链式存储结构就是用链表来表示一棵二叉树，即用链表来指示元素之间的逻辑关系。通常有两种存储形式：
链表中每个结点由三个域组成，除了数据域之外，还有两个指针域，分别用来给出该结点的左孩子和右孩子所在的存储地址。
链表中每个结点由四个域组成，除了数据域之外，还有三个指针域，分别用来给出该结点的左孩子、右孩子和双亲结点所在的存储地址。
class NodeL
{
Node root;
public static int index;
public Node CreateBTree( int[] a){ Node root = null; if(a[index]!='#'){ root =
new Node(a[index]); index++; root.setLChild(CreateBTree(a)); index++;
root.setRChild(CreateBTree(a)); } return root; } int getnodeNumber(Node n) {
if(n==null) return 0; return getnodeNumber(n.LeftC)+getnodeNumber(n.RightC)+1;
} int getLNumber(Node n) { if(n==null) return 0;
if(n.LeftC==null&&n.RightC==null) return 1; return
getLNumber(n.LeftC)+getLNumber(n.RightC); } //线序遍历 void preorder(Node n) {
if(n==null) return ; else { System.out.print(n.data+" "); preorder(n.LeftC);
preorder(n.RightC); } } //中序遍历 void inorder(Node n) { if(n==null) return ; else
{ inorder(n.LeftC); System.out.print(n.data+" "); inorder(n.RightC); } } //后续遍历
void postorder(Node n) { if(n==null) return ; else { postorder(n.LeftC);
postorder(n.RightC); System.out.print(n.data+" "); } } //按层次遍历 void
Printnode(Node n) { Node root = n; Queue <Node> queue = new
LinkedList<Node>();//用来存放树的结点，先进先出 LinkedList<Node> list = new
LinkedList<Node>(); queue.offer(root); //将根节点入队 while(!queue.isEmpty()){ Node
pre = queue.poll(); list.add(pre); //将结点入链 if(pre.LeftC!=null)
queue.offer(pre.LeftC); if(pre.RightC!=null) queue.offer(pre.RightC); }
Iterator<Node> it = list.iterator();//方便遍历结点 while(it.hasNext()){ Node cur =
(Node)it.next(); System.out.print(cur.data+", "); } } //求二叉树的深度 int
getDath(Node n) { if(n==null) return 0; int l=getDath(n.LeftC); int
r=getDath(n.RightC); return Math.max(l, r)+1; } //求二叉树中以元素值为X的节点为根的子数的 void
getXnumber(Node n,int x) { if(n==null) return ; else { if(n.data==x) {
System.out.println("元素值为 "+x+" 的子数为： "+ getDath(n)); } if(n.LeftC!=null)
getXnumber(n.LeftC,x); if(n.RightC!=null) getXnumber(n.RightC,x); } }
}
测试
public static void text2()
{
NodeL tree = new NodeL();
int[] a = new
int[]{10,3,2,’#’,’#’,4,’#’,9,8,’#’,’#’,9,’#’,’#’,18,13,’#’,’#’,21,’#’,’#’ };
tree.root=tree.CreateBTree(a);
System.out.print(“先序遍历：”);
tree.preorder(tree.root);
System.out.print("\n中序遍历：");
tree.inorder(tree.root);
System.out.print("\n后序遍历：");
tree.postorder(tree.root);
System.out.println();
System.out.print("层序遍历："); tree.Printnode(tree.root); System.out.println();
System.out.println("结点数："+tree.getnodeNumber(tree.root));
System.out.println("叶子数："+tree.getLNumber(tree.root));
System.out.println("深度："+tree.getDath(tree.root));
tree.getXnumber(tree.root,2); }