二叉树的链式存储结构_二叉树链式存储结构

二叉树的链式存储结构就是用链表来表示一棵二叉树，即用链表来指示元素之间的逻辑关系。通常有两种存储形式：

链表中每个结点由三个域组成，除了数据域之外，还有两个指针域，分别用来给出该结点的左孩子和右孩子所在的存储地址。
链表中每个结点由四个域组成，除了数据域之外，还有三个指针域，分别用来给出该结点的左孩子、右孩子和双亲结点所在的存储地址。

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);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110

}
测试

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);
}
1
2
3
4
5
6
7
8