数据结构-二叉树
数据结构
9 分钟 读完 (大约 1388 个字)

数据结构-二叉树

　　二叉树是指数的度为2的有序数。它是一种非常重要的数结构，在计算机领域中有着广泛的应用。二叉树的递归定义为：二叉树或者是一颗空数，或者是一颗由一个根结点和两颗互不相交的分别称为根的左子树和右子树所组成的非空树，左子树和右子树又同样都是一颗二叉树。

二叉树的存储结构

　　同单链表相同，二叉链表既可由独立分配的结点链接而成，也可由数组中的元素结点链接而成。

独立结点

1
2
3
4
5
6
7
8
9
10
11
12
13
public class BTreeNode {
	Object element;
	BTreeNode left,rigth;
	public BTreeNode(Object element){
		this.element=element;
		left=rigth=null;
	}
	public BTreeNode(Object element,BTreeNode left,BTreeNode rigth){
		this.element=element;
		this.left=left;
		this.rigth=rigth;
	}
}

元素结点

1
2
3
4
5
6
7
8
9
10
11
12
public class ABTreeNode {
	Object element;
	int left,rigth;
	public ABTreeNode(Object element){
		this.element=element;
	}
	public ABTreeNode(Object element,int left,int rigth){
		this.element=element;
		this.left=left;
		this.rigth=rigth;
	}
}

二叉树的方法

创建二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public void creat(){ 
	System.out.println("请按照树的先序遍历顺序组织数据");
	System.out.println("一个结点的二叉树11，输入：11 0 0");
	root=creat0();
}

private BTreeNode creat0(){  //递归构造 二叉树
	BTreeNode p;
	int date;
	System.out.print("输入数据:");
	date=in.nextInt();
	if(date==0){
		p=null;
	}else{
		p=new BTreeNode(date);
		p.left=creat0();
		p.rigth=creat0();
	}
	return p;
}

二叉树遍历

  1. 先序遍历

    1
    2
    3
    4
    5
    6
    7
    public void preOrder(BTreeNode bt){  //先序遍历二叉树
    	if(bt!=null){
    		System.out.print(bt.element+" ");
    		preOrder(bt.left);
    		preOrder(bt.rigth);
    	}
    }

  2. 中序遍历

    1
    2
    3
    4
    5
    6
    7
    public void inOrder(BTreeNode bt){  //中序遍历二叉树
    	if(bt!=null){
    		preOrder(bt.left);
    		System.out.print(bt.element+" ");
    		preOrder(bt.rigth);
    	}		
    }

  3. 后序遍历

    1
    2
    3
    4
    5
    6
    7
    public void postOrder(BTreeNode bt){  //后序遍历二叉树
    	if(bt!=null){
    		preOrder(bt.left);
    		preOrder(bt.rigth);
    		System.out.print(bt.element+" ");
    	}
    }

  4. 层次遍历

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    public void levelOrder(BTreeNode bt){ //层次遍历二叉树
    	Queue que=new LinkedList();// 创建一个队列
    	BTreeNode p=null;
    	que.add(bt); //添加
    	while(!que.isEmpty()){
    		p=(BTreeNode)que.poll();//取出第一个并且删除
    		System.out.print(p.element+" ");
    		if(p.left!=null) que.add(p.left);//如果左子树不为空，在队尾添加
    		if(p.rigth!=null) que.add(p.rigth);//如果右子树不为空,在队尾添加
    	}
    }

其他方法

  1. 判断二叉树是否为空

    1
    2
    3
    public boolean isEmpty(){ //判断二叉树是否为空
    	return root==null;
    }

  2. 求二叉树的深度

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    public int depthBTree(BTreeNode bt){ //求二叉树的深度
    	if(bt==null)
    		return 0;    //空结点，返回0并结束递归
    	else{
    		int left=depthBTree(bt.left);   //计算左子树的深度
    		int rigth=depthBTree(bt.rigth);   //计算右子树的深度
    		if(left>rigth)
    			return left+1;
    		else
    			return rigth+1;
    	}
    }

  3. 求二叉树中的结点数

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    public int countBTree(BTreeNode bt){ //求二叉树中的结点数
    	if(bt==null)
    		return 0;  //若结点为空 返回0 ，否则它等于左子树中的结点树与右子树中的结点数之和加一，这个一表示根结点
    	else
    		return countBTree(bt.left)+countBTree(bt.rigth)+1;
    }

    public int findBTree(BTreeNode bt,int x){//从二叉树查找值为x的结点，若存在则返回该结点的完整值
    	if(bt==null) return -1;
    	else{
    		if(bt.element==x)
    			return bt.element;
    		else{
    			int y;
    			y=findBTree(bt.left, x); if(y!=-1) return y;//左子树查找
    			y=findBTree(bt.rigth, x); if(y!=-1) return y;//右子树查找
    			return -1;
    		}
    	}
    }

  4. 清除二叉树

    1
    2
    3
    public void cleatBTree(){ //清除二叉树
    	root=null;
    }

实现代码


结点

1
2
3
4
5
6
7
8
9
10
11
12
13
public class BTreeNode {
	int element;
	BTreeNode left,rigth;
	public BTreeNode(int element){
		this.element=element;
		left=rigth=null;
	}
	public BTreeNode(int element,BTreeNode left,BTreeNode rigth){
		this.element=element;
		this.left=left;
		this.rigth=rigth;
	}
}

二叉树

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
111
112
113
114
115
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class linkBinaryTree {
	protected BTreeNode root;
	private Scanner in =new Scanner(System.in);
	public linkBinaryTree(){ //无参构造函数
		root=null;
	}
	
	public BTreeNode getRoot(){ //返回树根指针的值
		return root;
	}
	
	public void creat(){ 
		System.out.println("请按照树的先序遍历顺序组织数据");
		System.out.println("一个结点的二叉树11，输入：11 0 0");
		root=creat0();
	}
	
	private BTreeNode creat0(){  //递归构造 二叉树
		BTreeNode p;
		int date;
		System.out.print("输入数据:");
		date=in.nextInt();
		if(date==0){
			p=null;
		}else{
			p=new BTreeNode(date);
			p.left=creat0();
			p.rigth=creat0();
		}
		return p;
	}
	
	public void preOrder(BTreeNode bt){  //先序遍历二叉树
		if(bt!=null){
			System.out.print(bt.element+" ");
			preOrder(bt.left);
			preOrder(bt.rigth);
		}
	}
	
	public void inOrder(BTreeNode bt){  //中序遍历二叉树
		if(bt!=null){
			preOrder(bt.left);
			System.out.print(bt.element+" ");
			preOrder(bt.rigth);
		}		
	}
	
	public void postOrder(BTreeNode bt){  //后序遍历二叉树
		if(bt!=null){
			preOrder(bt.left);
			preOrder(bt.rigth);
			System.out.print(bt.element+" ");
		}
	}
	
	public void levelOrder(BTreeNode bt){ //层次遍历二叉树
		Queue que=new LinkedList();// 创建一个队列
		BTreeNode p=null;
		que.add(bt); //添加
		while(!que.isEmpty()){
			p=(BTreeNode)que.poll();//取出第一个并且删除
			System.out.print(p.element+" ");
			if(p.left!=null) que.add(p.left);//如果左子树不为空，在队尾添加
			if(p.rigth!=null) que.add(p.rigth);//如果右子树不为空,在队尾添加
		}
	}
	
	public boolean isEmpty(){ //判断二叉树是否为空
		return root==null;
	}
	
	public int depthBTree(BTreeNode bt){ //求二叉树的深度
		if(bt==null)
			return 0;    //空结点，返回0并结束递归
		else{
			int left=depthBTree(bt.left);   //计算左子树的深度
			int rigth=depthBTree(bt.rigth);   //计算右子树的深度
			if(left>rigth)
				return left+1;
			else
				return rigth+1;
		}
	}
	
	public int countBTree(BTreeNode bt){ //求二叉树中的结点数
		if(bt==null)
			return 0;  //若结点为空 返回0 ，否则它等于左子树中的结点树与右子树中的结点数之和加一，这个一表示根结点
		else
			return countBTree(bt.left)+countBTree(bt.rigth)+1;
	}
	
	public int findBTree(BTreeNode bt,int x){//从二叉树查找值为x的结点，若存在则返回该结点的完整值
		if(bt==null) return -1;
		else{
			if(bt.element==x)
				return bt.element;
			else{
				int y;
				y=findBTree(bt.left, x); if(y!=-1) return y;//左子树查找
				y=findBTree(bt.rigth, x); if(y!=-1) return y;//右子树查找
				return -1;
			}
		}
	}
	
	public void cleatBTree(){ //清除二叉树
		root=null;
	}
	
}

喜欢这篇文章？打赏一下作者吧

Servlet技术
JDBC对象
关注我

链接

分类

标签云

C++ Python 爬虫

最新文章

归档

标签

C++ 4
Python 1
爬虫 1

最新文章

归档

标签

C++ 4
Python 1
爬虫 1
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×