2022-08-01 Review the basic binary tree and operations

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

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

According to different uses can be divided into：

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

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

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

/* File: binary_tree.cpp Function: Review some operations on binary trees,创建、销毁、遍历 Writer: syq Time: 2022-08-01 */




#include <stdio.h>
#include <stdlib.h>
#include <iostream>

typedef int KEY_VALUE;



/* 定义二叉树的节点 */

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

    KEY_VALUE m_nKey;   //key

};

/* 定义二叉树,A binary tree can be traversed from its root node */

struct BinaryTree
{
    
    struct BinaryTreeNode* pRoot;
};



/* Create a binary tree node */

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;
}


/* Insert a binary tree node into a binary tree,如果keyIf it already exists there is no need to perform an insert */

int BinaryTreeInsert(struct BinaryTree* pTree,KEY_VALUE nKey)
{
    
    if(pTree == nullptr)
    {
    
        return -1;
    }
    if(pTree->pRoot == nullptr)
    {
    
        //When the root node is empty
        pTree->pRoot = CreateTreeNode(nKey);
        return 0;
    }
    
    //根节点
    struct BinaryTreeNode* pRoot = pTree->pRoot;
    struct BinaryTreeNode* pTmp = pTree->pRoot;
    //进行遍历,At the same time, determine the insertion position
    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了,Then the last valid node is pTmp;
    if (nKey < pTmp->m_nKey) 
    {
    
		pTmp->m_left = CreateTreeNode(nKey);
	} else 
    {
    
		pTmp->m_right = CreateTreeNode(nKey);
	}
    
    return 0;
}


/* 销毁mfrom a node,binary tree,采用中序遍历 */
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();
}