二叉树的基本操作

二叉树的建立

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Node* CreateBTree(Node*& T)
	{
		int ch;
		cin >> ch;
		if (ch != 0)
		{
			T = (Node*)malloc(sizeof(Node));
			T->data = ch;
			CreateBTree(T->lchild);
			CreateBTree(T->rchild);

		}
		else
		{
			T = NULL;
			return T;
		}
	}

二叉树三种排序

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
void PreOrder(Node* T)//先序遍历程序 
	{
		if (T != NULL)
		{
			cout << T->data;
			PreOrder(T->lchild);
			PreOrder(T->rchild);
		}
	}

	void InOrder(Node* T)//中序遍历程序 
	{
		if (T != NULL)
		{
			if (T->lchild != NULL) InOrder(T->lchild);
			cout << T->data;
			if (T->rchild != NULL) InOrder(T->rchild);
		}
	}
	void PostOrder(Node* T)//后序遍历程序 
	{
		if (T != NULL)
		{
			PostOrder(T->lchild);
			PostOrder(T->rchild);
			cout << T->data;
		}
	}

二叉树结点及深度操作

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
int Depth(Node* T)//计算树的深度
	{
		int depl, depr;
		if (T != NULL)
		{
			depl = Depth(T->lchild);
			depr = Depth(T->rchild);
			if (depl >= depr)
				return depl + 1;
			else
				return depr + 1;
		}
		else
			return 0;
	}
	int Size(Node* T)//计算二叉树结点个数 
	{
		if (T == NULL)
			return 0;
		else
			return 1 + Size(T->lchild) + Size(T->rchild);
	}
	int Size2(Node* T)//计算二叉树非叶子节点个数 
	{
		if (T != NULL)
		{
			if (T->lchild == NULL && T->rchild == NULL)
				return 0;
			else
				return Size2(T->lchild) + Size2(T->rchild) + 1;		
		}
		else
			return 0;
	}
};

完整代码

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
#include<iostream>
#include<cstdlib>
#include <malloc.h>
#include<cmath>
using namespace std;

struct Node
{
	int data;
	Node* lchild, * rchild;
};

class BTree
{
public:
	Node* CreateBTree(Node*& T)
	{
		int ch;
		cin >> ch;
		if (ch != 0)
		{
			T = (Node*)malloc(sizeof(Node));
			T->data = ch;
			CreateBTree(T->lchild);
			CreateBTree(T->rchild);

		}
		else
		{
			T = NULL;
			return T;
		}
	}
	void PreOrder(Node* T)//先序遍历程序 
	{
		if (T != NULL)
		{
			cout << T->data;
			PreOrder(T->lchild);
			PreOrder(T->rchild);
		}
	}

	void InOrder(Node* T)//中序遍历程序 
	{
		if (T != NULL)
		{
			if (T->lchild != NULL) InOrder(T->lchild);
			cout << T->data;
			if (T->rchild != NULL) InOrder(T->rchild);
		}
	}
	void PostOrder(Node* T)//后序遍历程序 
	{
		if (T != NULL)
		{
			PostOrder(T->lchild);
			PostOrder(T->rchild);
			cout << T->data;
		}
	}
	int Depth(Node* T)//计算树的深度
	{
		int depl, depr;
		if (T != NULL)
		{
			depl = Depth(T->lchild);
			depr = Depth(T->rchild);
			if (depl >= depr)
				return depl + 1;
			else
				return depr + 1;
		}
		else
			return 0;
	}
	int Size(Node* T)//计算二叉树结点个数 
	{
		if (T == NULL)
			return 0;
		else
			return 1 + Size(T->lchild) + Size(T->rchild);
	}
	int Size2(Node* T)//计算二叉树非叶子节点个数 
	{
		if (T != NULL)
		{
			if (T->lchild == NULL && T->rchild == NULL)
				return 0;
			else
				return Size2(T->lchild) + Size2(T->rchild) + 1;		
		}
		else
			return 0;
	}
};
int main()
{
	Node* S = NULL;//实参
	cout << "输入二叉树链表中各个域的值(输入0表示NULL)\n";
	BTree tree;
	tree.CreateBTree(S);
	cout << "建立的二叉树为：\n";
	tree.PreOrder(S);
	cout << " 先序\n";
	tree.InOrder(S);
	cout << " 中序\n";
	tree.PostOrder(S);
	cout << " 后序\n";
	cout << "\n该二叉树深度为:\n" <<  tree.Depth(S);
	cout << "\n该二叉树结点个数:\n" <<  tree.Size(S);
	cout << "\n该二叉树非叶子节点个数 :\n" <<  tree.Size2(S);
	return 0;
}

收获

二叉树建立及基本特点，递归函数的使用方法

改进

​ 了解二叉树的查找算法，丰富二叉树功能。下次呈现！！！