数据结构：：二叉树的基本操作

#include <iostream>
#include <stdlib.h>
#include<bits/stdc++.h>
using namespace std;
//数据元素类型
typedef char ElemType;
//二叉树结点定义
typedef struct TreeNode
{
    ElemType data;
    struct TreeNode *lson, *rson;
} TreeNode;
//二叉树类
class BinaryTree
{
private:
    TreeNode *root;
public:
    BinaryTree()
    {
        root = NULL;
    };
    ~BinaryTree()
    {
        MakeEmpty(root);
    }
    void MakeEmpty(TreeNode *t);
    void create( )
    {
        root = cp_create(root);
    };  //完全前序建立二叉树，空指针用@表示
    TreeNode *cp_create(TreeNode *t);
    int height(TreeNode *t) ;    //求二叉树的高度
    void output()
    {
        Pro_height(root);
    };
    void Pro_height(TreeNode *t);  // 前序顺序输出各个元素结点为根的子树的高度
    void output2( ) { Index_print(root,1); };
    void Index_print(TreeNode *t,int l);  //缩进目录形式输出二叉树
};
//二叉树置空
void BinaryTree::MakeEmpty(TreeNode *t)
{
    if (t != NULL)
    {
        MakeEmpty(t->lson);
        MakeEmpty(t->rson);
        delete t;
    }
}
//完全前序序列创建二叉树，空指针用@表示
TreeNode *BinaryTree::cp_create(TreeNode *t)
{
    ElemType v;
    cin >> v;
    if (v != ‘@‘)
    {
        t = new TreeNode;
        t->data = v;
        t->lson = cp_create(t->lson);
        t->rson = cp_create(t->rson);
    }
    else
        t = NULL;
    return t;

}

void BinaryTree::Pro_height(TreeNode *t)
{
    if(!t)
        return ;
    else
    {
        cout<<"Height("<<t->data<<")="<<height(t)<<endl;
        Pro_height(t->lson);
        Pro_height(t->rson);
    }
}

int  BinaryTree::height(TreeNode *t)
{
    if (t)
    {
        int dpt1 = height(t->lson);//获取当前结点的左子树深度
        int dpt2 = height(t->rson);//获取当前结点的右子树深度
        return (dpt1 > dpt2) ? (dpt1 + 1) : (dpt2 + 1);//仅选择当前最深的数值+基础值1，根结点默认深度为1
    }
    else
        return 0;
}
void BinaryTree::Index_print(TreeNode* t, int l)
{
    if (t==NULL) return ;
    for(int i=0;i<l-1;i++)
        cout<<"       ";
    printf("%2d",l);
    cout<<t->data<<endl;
    Index_print(t->lson,l+1);
    Index_print(t->rson,l+1);
}
int main()
{
    BinaryTree t;
    t.create();
    t.output();
    return 0;

}

#pragma once
#ifndef BINARYTREE_H
#define BINARYTREE_H
#include<iostream>
#include<stack>//用栈和循环模拟递归
#include<deque>
#include<algorithm>
using std::cout;
using std::cin;
using std::endl;
using std::stack;
using std::deque;
 
 
template<typename T>
class BNode {//创建二叉树结点类
public:
    T data;//存储数据
    BNode<T>* leftchild, * rightchild;//创建该结点的左右孩子指针
    BNode(T mydata = T())://二叉树结点类初始化
        leftchild(nullptr), rightchild(nullptr),data(mydata){}
    friend int IsExistLf(BNode<T>* Node)//判断该结点是否有左孩子，如果有取出其数据
    {
        if (Node->leftchild == nullptr)
            return 0;
        cout << Node->leftchild->data << endl;
        return 1;
    }
    friend int IsExistRt(BNode<T>* Node)//判断该结点是否有左孩子，如果有取出其数据
    {
        if (Node->rightchild == nullptr)
            return 0;
        cout << Node->rightchild->data << endl;
        return 1;
    }
};
 
template<typename T>
class BinaryTreeLinkedList
{
public:
    BinaryTreeLinkedList();
    BNode<T>* Creat(BNode<T>* root);//初始化一棵二叉树，其前序序列由键盘输入BinaryTreeLinkedList；
    BNode<T>* CreateTree(T* a, size_t n, const T& invalid, size_t& index);
    //BNode<T>* Create(BNode<T>* root);
    ~BinaryTreeLinkedList();//析构函数，释放二叉链表中各结点的存储空间
    void SetRecursiveFlag(bool ret);//设置RecursiveFlag
 
    void PreOrder(BNode<T>* root);//前序遍历二叉树
    void InOrder(BNode<T>* root);//中序遍历二叉树
    void PostOrder(BNode<T>* root);//后序遍历二叉树
    void Levelorder(BNode<T>* root);//层序遍历二叉树
    int Depth(BNode<T>* root);//返回二叉树的深度
    int LeafNodeNum(BNode<T>* root);//返回二叉树叶子结点的个数
    int AllNodeNum(BNode<T>* root);//返回二叉树所有结点的个数
    
private:
    static int num;
    BNode<T>* root;//指向根结点的头指针
    bool RecursiveFlag;    //RecursiveFlag是指采用递归编写遍历，当为false时采用循环编写遍历    
    void Release(BNode<T>* root);//析构函数调用
    
};
template<typename T>
int BinaryTreeLinkedList<T>::num = 0;
 
template<typename T>
BinaryTreeLinkedList<T>::BinaryTreeLinkedList() :root(nullptr), RecursiveFlag(true)
{
}
 
//初始化一棵二叉树，其前序序列由键盘输入BinaryTreeLinkedList；
template<typename T>
BNode<T>* BinaryTreeLinkedList<T>::Creat(BNode<T>* root)
{
    char ch;
    //cin.get(ch);
    cin >> ch;
    //if (ch == ‘#‘)
    //    //root = nullptr;
    //else
    //{
    //    root = new BNode<T>(ch);
    //    //root->data = ch;
    //    cout << "数据为: " << root->data << "地址为: " << root << endl;
    //    Creat(root->leftchild);
    //    Creat(root->rightchild);
    //}
    if ((ch != ‘#‘))
    {
        root = new BNode<T>(ch);
        cout << "数据为: " << root->data << "地址为: " << root << endl;
        Creat(root->leftchild);
        Creat(root->rightchild);        
    }    
    return root;
}
 
template<typename T>
BNode<T>* BinaryTreeLinkedList<T>::CreateTree(T* a, size_t n, const T& invalid, size_t& index)
{
    //BNode<T>* root = nullptr;
    if (a[index] != invalid)
    {
        root = new BNode<T>(a[index]);
        //root->data = a[index];
        cout << "数据为: " << root->data << "地址为: " << root << endl;
        root->leftchild = CreateTree(a, n, invalid, ++index);
        
        root->rightchild = CreateTree(a, n, invalid, ++index);
    }
    return root;
}
 
 
 
//析构函数，释放二叉链表中各结点的存储空间
template<typename T>
BinaryTreeLinkedList<T>::~BinaryTreeLinkedList()
{
    Release(root);
}
 
//设置RecursiveFlag
template<typename T>
void BinaryTreeLinkedList<T>::SetRecursiveFlag(bool ret)
{
    RecursiveFlag = ret;
}
 
//前序遍历二叉树
//若二叉树为空，则空操作返回，否则
//（1）访问根结点；
//（2）前序遍历根结点的左子树；
//（3）前序遍历根结点的右子树。
template<typename T>
void BinaryTreeLinkedList<T>::PreOrder(BNode<T>* root)
{
    if (RecursiveFlag)//采用递归遍历
    {
    if (!root)
        return;
    else
    {
        //++num;
        cout << root->data << "  ";
        PreOrder(root->leftchild);
        PreOrder(root->rightchild);
    }
    }
    else //采用栈和循环遍历
    {
        stack<BNode<T>*> mystack;//创建一个可以存储二叉树结点的栈
        if (root)
        {
            ////循环前的初始化
            //mystack.push(root);//将根结点压入栈中
            //cout << root->data << "  ";
            //root = root->leftchild;
            while (root || !mystack.empty())//当当前结点不为空或者栈不空都应执行循环
            {
                while (root)//如果此时该结点的左孩子不为空指针，那么要继续压栈
                {
                    mystack.push(root);
                    cout << root->data << "  ";//打印当前结点信息
                    root = root->leftchild;
                }
                if (!mystack.empty())//此时该结点的左孩子为空指针，那么我们需要访问该结点的右孩子
                {
                    root = mystack.top();//获取当前结点的指针
                    root = root->rightchild;
                    mystack.pop();//此结点的弹出，它的信息已经全部利用完了(左右孩子都访问了一遍所以他没有利用价值了)
                }
            }
        }
    }
}
 
//中序遍历二叉树
//若二叉树为空，则空操作返回，否则
//（1）中序遍历根结点的左子树；
//（2）访问根结点；
//（3）中序遍历根结点的右子树。
template<typename T>
void BinaryTreeLinkedList<T>::InOrder(BNode<T>* root)
{
    if (RecursiveFlag)//采用递归遍历
    {
        if (root)
        {
            PreOrder(root->leftchild);
            cout << root->data << "  ";
            PreOrder(root->rightchild);
        }
        else
            return;
    }
    else //采用栈和循环遍历
    {
        stack<BNode<T>*> mystack;//创建一个可以存储二叉树结点的栈
        if (root)
        {
            while (root || !mystack.empty())
            {
                while (root)//只进行压栈和结点向左伸展
                {
                    mystack.push(root);
                    root = root->leftchild;
                }
                if (!mystack.empty())//当左孩子为空时，需要打印该结点的信息，同时访问该结点的右孩子
                {
                    root = mystack.top();//获取当前结点的指针
                    cout << root->data << "  ";//打印当前最左侧结点的信息
                    root = root->rightchild;
                    mystack.pop();//出栈
                }
            }
            return;
        }
        return;
    }
}
 
//后序遍历二叉树
//若二叉树为空，则空操作返回，否则
//（1）后序遍历根结点的左子树；
//（2）后序遍历根结点的右子树；
//（3）问根结点。
template<typename T>
void BinaryTreeLinkedList<T>::PostOrder(BNode<T>* root)
{
    if (RecursiveFlag)//采用递归遍历
    {
        if (root)
        {
            PostOrder(root->leftchild);
            PostOrder(root->rightchild);
            cout << root->data << "  ";
        }
        else
            return;
    }
    else //采用循环遍历
    {
        //stack<BNode<T>*> mystack;//创建一个可以存储二叉树结点的栈
        //if (root)
        //{
        //    while (root || mystack.size() != 1)//当当前结点不为空或者栈不空都应执行循环
        //    {
        //        while (root)//如果此时该结点的左孩子不为空指针，那么要继续压栈
        //        {
        //            mystack.push(root);
        //            root = root->leftchild;
        //        }
        //        if (!mystack.empty())//此时该结点的左孩子为空指针，那么我们需要访问该结点的右孩子
        //        {
        //            if (mystack.size() != 1&&root->rightchild)
        //            {
        //                root = mystack.top();//获取当前结点的指针
        //                cout << root->data << "  ";//打印当前最左侧结点的信息
        //                root = root->rightchild;
        //                mystack.pop();//出栈
        //            }
        //            else//说明现在仅剩下根结点了
        //            {
        //                root = mystack.top();
        //                root = root->rightchild;
        //            }
        //        }
        //    }
        //    root = mystack.top();//访问最后一个结点根结点
        //    cout << root->data << "  ";
        //    mystack.pop();
        //    return;
        //}
        //return;
    }
}
 
//层序遍历二叉树
template<typename T>
void BinaryTreeLinkedList<T>::Levelorder(BNode<T>* root)
{
    deque<BNode<T>*> mydeque;
    if (root)
    {
        //循环起端初始化
        mydeque.push_back(root);
        while (!mydeque.empty())//当队列不空时要继续出队和入队，因为队列先进先出
        {
            root = mydeque.front();//取出队列队头元素
            cout << root->data << "  ";
            mydeque.pop_front();//出队
            if (root->leftchild) {
                mydeque.push_back(root->leftchild);
            }
            if (root->rightchild) {
                mydeque.push_back(root->rightchild);
            }
        }
    }
    return;
}
 
 
//返回二叉树的深度
template<typename T>
int BinaryTreeLinkedList<T>::Depth(BNode<T>* root)
{
    if (root) 
    {
        int dpt1 = Depth(root->leftchild);//获取当前结点的左子树深度
        int dpt2 = Depth(root->rightchild);//获取当前结点的右子树深度
        return (dpt1 > dpt2) ? (dpt1 + 1) : (dpt2 + 1);//仅选择当前最深的数值+基础值1，根结点默认深度为1
    }
    else
        return 0;
}
 
//返回二叉树叶子结点的个数
template<typename T>
int BinaryTreeLinkedList<T>::LeafNodeNum(BNode<T>* root)
{
    if (root == nullptr)
        return 0;
    else if (root->leftchild == nullptr && root->rightchild == nullptr)
        return 1;
    else
        return LeafNodeNum(root->leftchild) + LeafNodeNum(root->rightchild);
}
 
//返回二叉树所有结点的个数
template<typename T>
int BinaryTreeLinkedList<T>::AllNodeNum(BNode<T>* root)
{
    if (root == nullptr)
        return 0;
    else
        return AllNodeNum(root->leftchild) + AllNodeNum(root->rightchild) + 1;
}
 
 
//析构函数调用
template<typename T>
void BinaryTreeLinkedList<T>::Release(BNode<T>* root)
{
    if (root)//如果当前结点不为空时，则进入递归
    {
        Release(root->leftchild);//释放左子树
        Release(root->rightchild);//释放右子树
        delete root;
    }
    return;
}
#endif // !BINARYTREE_

#include<iostream>
#include"binary_tree.h"
 
int main()
{
    BinaryTreeLinkedList<char> myBT;
    BNode<char>* root = new BNode<char>(‘A‘);//按照前序遍历创建节点
    root->leftchild= new BNode<char>(‘B‘);
    root->leftchild->rightchild = new BNode<char>(‘D‘);
    root->rightchild = new BNode<char>(‘C‘);
    cout << "树的深度为:" << myBT.Depth(root) << endl;
    cout << "树的叶子结点个数为:" << myBT.LeafNodeNum(root) << endl;
    cout << "树的所有结点个数为:" << myBT.AllNodeNum(root) << endl;
    //myBT.SetRecursiveFlag(false);
    cout << "递归前序遍历:" << endl;
    myBT.PreOrder(root);
    cout << endl;
    cout << "递归中序遍历:" << endl;
    myBT.InOrder(root);
    cout << endl;
    cout << "递归后序遍历:" << endl;
    myBT.PostOrder(root);
    cout << endl;
    cout << "层序遍历:" << endl;
    myBT.Levelorder(root);
    cout << endl;
    myBT.SetRecursiveFlag(false);
    cout << "栈与循环前序遍历:" << endl;
    myBT.PreOrder(root);
    //cout << endl;
    //cout << "栈与循环中序遍历:" << endl;
    //myBT.InOrder(root);
    //cout << endl;
    cout << endl;
    //size_t index = 0;
    //char x[9] = { ‘A‘,‘B‘,‘#‘,‘D‘,‘#‘,‘#‘,‘C‘,‘#‘,‘#‘ };
    //root = myBT.CreateTree(x, sizeof(x) / sizeof(char), ‘#‘, index);
    //root = myBT.Creat(root);
    //cout << IsExistLf(root) << endl;
    //cout << IsExistRt(root) << endl;
}

https://blog.csdn.net/candand_python/article/details/105426256?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522159201408119195239829350%2522%252C%2522scm%2522%253A%252220140713.130102334.pc%255Fall.%2522%257D&request_id=159201408119195239829350&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~first_rank_ecpm_v3~pc_rank_v3-1-105426256.first_rank_ecpm_v3_pc_rank_v3&utm_term=%E4%BA%8C%E5%8F%89%E9%93%BE%E5%BC%8Fc%2B%2B