数据结构-树

基于C/C++二叉树的构建与操作。

---

二叉树-递归实现

---

树的结点

typedef int BT_ElemType;

//树的结点结构
typedef struct BTNode{
    BT_ElemType data;
    BTNode *L_child, *R_child;//左右孩子结点的指针
} BTNode;

树的创建

BTNode *BiTree_Create()
{
    BT_ElemType data;
    scanf("%d", &data);//手动输入树的结点值
    BTNode *T;
    if (data == 0) //当遇到0时，令树的根节点为NULL，从而结束该分支的递归
    {
        T = NULL;//空分支
        return T;
    }
    else
    {
        T = (BTNode *)malloc(sizeof(BTNode));//创建新的树节点
        //先序创建树
        T->data = data;//先给根节点赋值
        T->L_child = BiTree_Create();//创建左子树
        T->R_child = BiTree_Create();//创建右子树
    }
    return T;
}

访问结点数据

//访问节点数据
void BiTree_Vist_Node(BTNode *T)
{
    printf("%d ", T->data);
}

前序遍历

//前序遍历
void BiTree_Preorder_Traversal(BTNode *T)
{
    if (T)
    {
        BiTree_Vist_Node(T);
        BiTree_Preorder_Traversal(T->L_child);
        BiTree_Preorder_Traversal(T->R_child);
    }
}

中序遍历

//中序遍历
void BiTree_Inorder_Traversal(BTNode *T)
{
    if (T)
    {
        BiTree_Inorder_Traversal(T->L_child);
        BiTree_Vist_Node(T);
        BiTree_Inorder_Traversal(T->R_child);
    }
}

后序遍历

//后序遍历
void BiTree_Postorder_Traversal(BTNode *T)
{
    if (T)
    {
        BiTree_Postorder_Traversal(T->L_child);
        BiTree_Postorder_Traversal(T->R_child);
        BiTree_Vist_Node(T);
    }
}

双序遍历

//二叉树的双序遍历
void BiTree_DblOrder_Traverse(BTNode *T)
{
    if(T)
    {
        BiTree_Vist_Node(T);
        BiTree_DblOrder_Traverse(T->L_child);
        BiTree_Vist_Node(T);
        BiTree_DblOrder_Traverse(T->R_child);
    }
}

树的复制

//二叉树的复制
void BiTree_Copy(BTNode *T, BTNode *NewT)
{
    if (T == NULL)
    {
        NewT = NULL;
    }
    else
    {
        NewT = (BTNode *)malloc(sizeof(BTNode));
        NewT->data = T->data;
        BiTree_Copy(T->L_child, NewT->L_child);
        BiTree_Copy(T->R_child, NewT->R_child);
    }
}

树的深度

//树的深度
int BiTree_Depth(BTNode *T)
{
    if (T == NULL)
        return 0;
    else
    {
        int m = BiTree_Depth(T->L_child);
        int n = BiTree_Depth(T->R_child);
        if (m > n)
            return (m + 1);
        else
            return (n + 1);
    }
}

结点个数

//统计二叉树中结点的个数
int BiTree_Node_Count(BTNode *T)
{
    if (T == NULL)
        return 0;
    else
        return BiTree_Node_Count(T->L_child) + BiTree_Node_Count(T->R_child) + 1;
}

···

---

### 二叉树-非递归实现

---

结点结构

//树的结点结构
typedef struct BTNode{
    BT_ElemType data;
    BTNode *L_child, *R_child;
    int visitCount;//用于非递归的后序遍历
} BTNode;

先序遍历

//先序遍历-使用栈(Stack)
void Preorder_Traversal(BTNode *T)
{
    stack <BTNode *> TreeStack;//声明一个树的栈名为TreeStack
    BTNode *p = T; //辅助结点指针
    while (p || !TreeStack.empty())//p不指向NULL或者栈内非空
    {
        if (p)//p不指向NULL
        {
            printf("%d ", p->data);//访问结点值
            TreeStack.push(p);//将p压入栈中,后进先出
            p = p->L_child;//p指向他的左孩子
        }
        else//p指向NULL
        {
            p = TreeStack.top();//取得栈顶指针
            TreeStack.pop();//开始出栈,即访问左节点为空
            p = p->R_child;//开始访问出战的左节点为空的父节点的右结点
        }
    }
}

中序遍历

// 中序遍历 
void Inorder_Traverse(BTNode* T)    
{    
    stack <BTNode*> TreeStack;
    BTNode* p = T;

    while (p || !TreeStack.empty())//p不指向NULL或者栈非空
    {
        if (p)//p不指向NULL
        {
            TreeStack.push(p);//压进栈内
            p = p->L_child;//访问他的左孩子
        }
        else//p指向NULL
        {
            p = TreeStack.top();//取得栈顶指针
            printf("%d ", p->data);//访问根节点
            TreeStack.pop();//根结点的左孩子开始出栈
            p = p->R_child;//访问目前根节点的右孩子
        }
    }
}

后序遍历

// 后序遍历
void Postorder_Traversal(BTNode *T)
{
    stack<BTNode *> TreeStack;
    BTNode *p = T;
    while (p || !TreeStack.empty())
    {
        if (p) //不指向NULL
        {
            p->visitCount = 1; //访问根节点一次
            TreeStack.push(p); //压入栈中
            p = p->L_child;    //访问左结点
        }
        else //指向NULL
        {
            p = TreeStack.top();
            if (p->visitCount == 2)
            {
                TreeStack.pop(); //出栈
                printf("%d ", p->data); //读出栈顶的值
                p = NULL;//指向空
            }
            else //只有访问过一次
            {
                p->visitCount++;   //访问次数+1
                p = p->R_child;    //访问右孩子
            }
        }
    }
}

层序遍历

// 层序遍历
void Levelorder_Traversal(BTNode *T)
{
    if (!T)
    {
        return;
    }
    queue<BTNode *> TreeQueue; //调用队列
    TreeQueue.push(T);//树的根节点入队
    BTNode *p = T;
    while (!TreeQueue.empty())//队列非空
    {
        p = TreeQueue.front();//指向队头
        TreeQueue.pop();//出队
        printf("%d ", p->data);//取值
        if (p->L_child)//存在左结点,入队
        {
            TreeQueue.push(p->L_child);
        }
        if (p->R_child)//存在右结点,入队
        {
            TreeQueue.push(p->R_child);
        }
    }
}

···

---

### 调用栈与队列

---

使用命名空间

using namespace std; //使用命名空间调用队列堆栈

引入头文件

#include <queue>
#include <stack>

调用

stack<BTNode *> TreeStack;      //声明一个元素为树结点指针的栈，名为TreeStack

基本操作

xx.empty() //为空则返回真
xx.pop() //删除元素
xx.push() //增加元素

···

---

### 测试源码

---

递归/非递归实现源码，请点击这里获取

---

随时补充

---