2022-08-01 回顾基础二叉树以及操作

二叉树常被用于实现二叉查找树和二叉堆。

在计算机科学中，二叉树是每个结点最多有两个子树的树结构。通常子树被称作“左子树”和“右子树”。

根据不同的用途可分为：

1、完全二叉树——若设二叉树的高度为h，除第 h 层外，其它各层 (1～h-1)
的结点数都达到最大个数，第h层有叶子结点，并且叶子结点都是从左到右依次排布，这就是完全二叉树。

2、满二叉树——除了叶结点外每一个结点都有左右子叶且叶子结点都处在最底层的二叉树。

3、平衡二叉树——平衡二叉树又被称为AVL树（区别于AVL算法），它是一棵二叉排序树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

/*
File:       binary_tree.cpp
Function:   回顾二叉树的一些操作，创建、销毁、遍历
Writer:     syq
Time:       2022-08-01


*/




#include 
#include 
#include 

typedef int KEY_VALUE;



/*
定义二叉树的节点

*/

struct BinaryTreeNode
{
    struct BinaryTreeNode* m_left;
    struct BinaryTreeNode* m_right;

    KEY_VALUE m_nKey;   //key

};

/*
定义二叉树，二叉树可以从它的根节点进行遍历

*/

struct BinaryTree
{
    struct BinaryTreeNode* pRoot;
};



/*
创建一个二叉树的节点

*/

struct BinaryTreeNode* CreateTreeNode(KEY_VALUE nKey)
{
    struct BinaryTreeNode* pNode = (struct BinaryTreeNode*)malloc(sizeof(struct BinaryTreeNode));
    if(pNode)
    {       
        std::cout<<"create address:"<<pNode<<std::endl;
        pNode->m_left = pNode->m_right = nullptr;
        pNode->m_nKey = nKey;
        return pNode;
    }
    return nullptr;
}


/*
向一个二叉树中插入一个二叉树节点，如果key已经存在则不需要执行插入

*/

int BinaryTreeInsert(struct BinaryTree* pTree,KEY_VALUE nKey)
{
    if(pTree == nullptr)
    {
        return -1;
    }
    if(pTree->pRoot == nullptr)
    {
        //根节点为空的时候
        pTree->pRoot = CreateTreeNode(nKey);
        return 0;
    }
    
    //根节点
    struct BinaryTreeNode* pRoot = pTree->pRoot;
    struct BinaryTreeNode* pTmp = pTree->pRoot;
    //进行遍历，同时确定确定插入位置
    while(pRoot != nullptr)
    {
        pTmp = pRoot;
        if(nKey < pTmp->m_nKey)
        {
            //左子树
            pRoot = pTmp->m_left;
        }
        else if(nKey > pTmp->m_nKey)
        {
            pRoot = pTmp->m_right;
        }
    }
    //pRoot已经为nullptr了，则上一个有效节点是pTmp;
    if (nKey < pTmp->m_nKey) 
    {
		pTmp->m_left = CreateTreeNode(nKey);
	} else 
    {
		pTmp->m_right = CreateTreeNode(nKey);
	}
    
    return 0;
}


/*
销毁m某个节点开始的，二叉子树，采用中序遍历
*/
int BinaryTree_Destory(struct BinaryTreeNode* pNode)
{
    
    if (pNode == nullptr) return 0;
	
	BinaryTree_Destory(pNode->m_left);
    
	free(pNode);
    std::cout<<"free address:"<<pNode<<std::endl;
	BinaryTree_Destory(pNode->m_right);
    return 0;
}



/*
二叉树的遍历,前序，中序，后续遍历
前序遍历：先根节点，再左节点，最后右节点
中序遍历：先左节点，再根节点，最后右节点
后序遍历：先左节点，再右节点，最后根节点
*/


int BinaryTree_Traversal(struct BinaryTreeNode* pNode)
{
    if (pNode == nullptr) return 0;
	
	BinaryTree_Traversal(pNode->m_left);
    std::cout << pNode->m_nKey<<std::endl;
	
	BinaryTree_Traversal(pNode->m_right);
    return 0;
}



int main()
{
    int keyArray[10] = {1,3,5,6,11,2,4,88,66,55};

	struct BinaryTree T = {0};
	int i = 0;
	for (i = 0;i < 10;i ++) {
		BinaryTreeInsert(&T, keyArray[i]);
	}

	BinaryTree_Traversal(T.pRoot);

	getchar();
    BinaryTree_Destory(T.pRoot);
    getchar();
}
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
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168