Java数据结构之二叉树的构建与遍历

---

代码

本篇博客提供以下功能的代码：

• 用户输入字符序列，生成二叉树，并用二叉链表存储
• 二叉树的前序、中序、后序递归遍历
• 二叉树的前序、中序非递归遍历

二叉树结点类

public class BinaryNode<T> {
	public T data;
	public  BinaryNode<T> left;
	public BinaryNode<T> right;
    public BinaryNode()
	{
		this.data=null;
		this.left=null;
		this.right=null;
	}
    public BinaryNode(T data)
    {
    	this.data=data;
    	this.left=null;
    	this.right=null;
    }
    public BinaryNode(T data,BinaryNode<T> left,BinaryNode<T> right)
    {
    	this.data=data;
    	this.left=left;
    	this.right=right;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

二叉树实现类

public class BinaryTree<T> {
	public BinaryNode<T> root;
	static int i=0;
	public BinaryTree(T[] arr)
	{
		this.root=CreateTree(arr);
		System.out.println("创建成功");
	}
	//构造
	private BinaryNode<T> CreateTree(T[] arr)
	{
		BinaryNode<T> p=null;
		
		if(this.i<arr.length)
		{
			if(arr[this.i]!=(T)null)
			{
				p=new BinaryNode<T>(arr[i]);
				this.i++;
				p.left=CreateTree(arr);
				p.right=CreateTree(arr);
			}
			else
			{
				this.i++;
			}
			
		}
		return p;
	}
	//递归遍历
	//先序遍历 根左右
	public void PreOrder(BinaryNode<T> root)
	{
		if(root!=null)
		{
			System.out.println(root.data);
			PreOrder(root.left);
			PreOrder(root.right);
		}
	}
	//中序遍历 左根右
	public void InOrder(BinaryNode<T> root)
	{
		if(root!=null)
		{
			InOrder(root.left);
			System.out.println(root.data);
			InOrder(root.right);
		}
	}
	//后序遍历 左右根
	public void PostOrder(BinaryNode<T> root)
	{
		if(root!=null)
		{
			PostOrder(root.left);
			PostOrder(root.right);
			System.out.println(root.data);
		}
	}
	//非递归遍历
	public void preOrder(BinaryNode<T> root)
	{
		SeqStack<BinaryNode> st=new SeqStack<>();
		BinaryNode<T> temp=root;
		if(temp!=null)
			st.push(temp);
		while(!st.isEmpty())
		{
			temp=st.pop();
			System.out.println(temp.data);
			if(temp.right!=null)
				st.push(temp.right);
			if(temp.left!=null)
				st.push(temp.left);
		}
		
	}
	//
	public void inOrder(BinaryNode<T> root)
	{
		SeqStack<BinaryNode> st=new SeqStack<>();
		BinaryNode<T> temp=root;
	
		
		while(!st.isEmpty()||temp!=null)
		{
			//从某节点出发边压栈边找到该结点的最左叶子结点
			while(temp!=null)
			{
				st.push(temp);
				temp=temp.left;
				
			}
			
		
			  if(!st.isEmpty())
			  {
				temp=st.pop();
				System.out.println(temp.data);
				temp=temp.right;
			  }
		    
			
		}
		
		
	}
}
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 class Test {

	public static void main(String[] args)
	{
		String[] arr ={"A","B","C",null,null,"D","E",null,"G",null,null,"F",null,null,null};
		BinaryTree<String> tree=new BinaryTree<String>(arr);
		Scanner input=new Scanner(System.in);
		
		
			tree.inOrder(tree.root);
			
		
		
	}

	
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17