c语言层序遍历创建二叉树,二叉树的建立与遍历完整代码C语言

发布时间：2022-11-23

本文目录一览：

  1. 请问C语言如何创建二叉树？？？？
  2. 二叉树的建立与遍历(C语言)
  3. 急求C语言写二叉树的遍历

请问C语言如何创建二叉树？？？？

创建二叉树的源程序如下：

#include <cstdlib>
#include <stdio.h>
typedef struct node
{
    // 树的结点
    int data;
    struct node* left;
    struct node* right;
} Node;
typedef struct
{
    // 树根
    Node* root;
} Tree;
void insert(Tree* tree, int value) // 创建树
{
    Node* node = (Node*)malloc(sizeof(Node)); // 创建一个节点
    node->data = value;
    node->left = NULL;
    node->right = NULL;
    if (tree->root == NULL) // 判断树是不是空树
    {
        tree->root = node;
    }
    else
    {
        // 不是空树
        Node* temp = tree->root; // 从树根开始
        while (temp != NULL)
        {
            if (value < temp->data) // 小于就进左儿子
            {
                if (temp->left == NULL)
                {
                    temp->left = node;
                    return;
                }
                else
                {
                    // 继续判断
                    temp = temp->left;
                }
            }
            else // 否则进右儿子
            {
                if (temp->right == NULL)
                {
                    temp->right = node;
                    return;
                }
                else
                {
                    // 继续判断
                    temp = temp->right;
                }
            }
        }
    }
    return;
}
void inorder(Node* node) // 树的中序遍历
{
    if (node != NULL)
    {
        inorder(node->left);
        printf("%d ", node->data);
        inorder(node->right);
    }
}
int main()
{
    Tree tree;
    tree.root = NULL; // 创建一个空树
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) // 输入n个数并创建这个树
    {
        int temp;
        scanf("%d", &temp);
        insert(&tree, temp);
    }
    inorder(tree.root); // 中序遍历
    getchar();
    getchar();
    return 0;
}

扩展资料：

简单二叉树定义范例：此树的顺序结构为：ABCDE

#include <cstdlib>
#include <stdio.h>
#include <string>
int main()
{
    Node* p = new Node;
    Node* p = head;
    head = p;
    std::string str;
    std::cin >> str;
    creat(p, str, 0); // 默认根结点在str下标0的位置
    return 0;
}
// p为树的根结点（已开辟动态内存）,str为二叉树的顺序存储数组ABCD##E或其他顺序存储数组，r当前结点所在顺序存储数组位置
void creat(Node* p, std::string str, int r)
{
    p->data = str[r];
    if (str[r * 2 + 1] == '#' || r * 2 + 1 > str.size() - 1)
        p->lch = NULL;
    else
    {
        p->lch = new Node;
        creat(p->lch, str, r * 2 + 1);
    }
    if (str[r * 2 + 2] == '#' || r * 2 + 2 > str.size() - 1)
        p->rch = NULL;
    else
    {
        p->rch = new Node;
        creat(p->rch, str, r * 2 + 2);
    }
}

二叉树的建立与遍历(C语言)

楼主你好~~~“ф”字符的源代码我忘记了，我这里有一个自己写过的遍历算法

#include <iostream.h>
typedef struct btnode
{
    char data;
    struct btnode *Lchild, *Rchild;
} *bitreptr;
void Create(bitreptr p)
{
    char n;
    p = new btnode;
    cin >> n;
    if (n != '#')
    {
        p->data = n;
        Create(p->Lchild);
        Create(p->Rchild);
    }
    else
        p = NULL;
}
void preorder(bitreptr p)
{
    if (p)
    {
        cout << p->data << " ";
        preorder(p->Lchild);
        preorder(p->Rchild);
    }
}
void midorder(bitreptr p)
{
    if (p)
    {
        midorder(p->Lchild);
        cout << p->data << " ";
        midorder(p->Rchild);
    }
}
void postorder(bitreptr p)
{
    if (p)
    {
        postorder(p->Lchild);
        postorder(p->Rchild);
        cout << p->data << " ";
    }
}
void change(bitreptr p)
{
    bitreptr t, q;
    if (p)
    {
        t = p->Lchild;
        q = p->Rchild;
        p->Lchild = q;
        p->Rchild = t;
        change(p->Lchild);
        change(p->Rchild);
    }
}
void main()
{
    char i;
    cout << "请选择所需功能（'A'输出该二叉树序列，'B'输出交换后二叉树序列)" << endl;
    cin >> i;
    bitreptr p;
    cout << "输入数据：";
    Create(p);
    switch (i)
    {
    case 'A':
        cout << "前序:";
        preorder(p);
        cout << endl;
        cout << "中序:";
        midorder(p);
        cout << endl;
        cout << "后序:";
        postorder(p);
        cout << endl;
        break;
    case 'B':
        change(p);
        cout << "交换二叉树前序:";
        preorder(p);
        cout << endl;
        cout << "交换二叉树中序:";
        midorder(p);
        cout << endl;
        cout << "交换二叉树后序:";
        postorder(p);
        cout << endl;
        break;
    }
}

这个算法输入时要以“#”代表空节点，及将[测试数据] “ABCффDEфGффф”改成“ABC##DE#G##F###”即可。另外我的算法包括了二叉树左右子树交换的代码“change(bitreptr p)”，只要楼主稍作修改就可以得到你想要的完美结果~

急求C语言写二叉树的遍历

BinaryTree.h

/********************************************************************
created: 2006/07/04
filename: BinaryTree.h
author: 李创
purpose: 演示二叉树的算法
*********************************************************************/
#ifndef BinaryTree_H
#define BinaryTree_H
#include <stdlib.h>
#include <stack>
class BinaryTree
{
private:
    typedef int Item;
    typedef struct TreeNode
    {
        Item Node;
        TreeNode* pRight;
        TreeNode* pLeft;
        TreeNode(Item node = 0, TreeNode* pright = NULL, TreeNode* pleft = NULL)
            : Node(node), pRight(pright), pLeft(pleft)
        {
        }
    } TreeNode, *PTreeNode;
public:
    enum TraverseType
    {
        PREORDER = 0, // 前序
        INORDER = 1,  // 中序
        POSTORDER = 2, // 后序
        LEVELORDER = 3 // 层序
    };
    BinaryTree(Item Array[], int nLength);
    ~BinaryTree();
    PTreeNode GetRoot()
    {
        return m_pRoot;
    }
    // 遍历树的对外接口
    // 指定遍历类型和是否是非递归遍历,默认是递归遍历
    void Traverse(TraverseType traversetype, bool bRec = true);
private:
    PTreeNode CreateTreeImpl(Item Array[], int nLength);
    void DetroyTreeImpl(PTreeNode pTreenode);
    void PreTraverseImpl(PTreeNode pTreenode); // 递归前序遍历树
    void InTraverseImpl(PTreeNode pTreenode);  // 递归中序遍历树
    void PostTraverseImpl(PTreeNode pTreenode); // 递归后序遍历树
    void NoRecPreTraverseImpl(PTreeNode pTreenode); // 非递归前序遍历树
    void NoRecInTraverseImpl(PTreeNode pTreenode);  // 非递归中序遍历树
    void NoRecPostTraverseImpl(PTreeNode pTreenode); // 非递归后序遍历树
    void LevelTraverseImpl(PTreeNode pTreenode);
    PTreeNode m_pRoot; // 根结点
    // 采用STL里面的stack作为模拟保存链表结点的stack容器
    typedef std::stack<BinaryTree::PTreeNode> TreeNodeStack;
};
#endif

BinaryTree.cpp

/********************************************************************
created: 2006/07/04
filename: BinaryTree.cpp
author: 李创
purpose: 演示二叉树的算法
*********************************************************************/
#include <iostream>
#include <assert.h>
#include <queue>
#include "BinaryTree.h"
BinaryTree::BinaryTree(Item Array[], int nLength)
    : m_pRoot(NULL)
{
    assert(NULL != Array);
    assert(nLength > 0);
    m_pRoot = CreateTreeImpl(Array, nLength);
}
BinaryTree::~BinaryTree()
{
    DetroyTreeImpl(m_pRoot);
}
// 按照中序递归创建树
BinaryTree::PTreeNode BinaryTree::CreateTreeImpl(Item Array[], int nLength)
{
    int mid = nLength / 2;
    PTreeNode p = new TreeNode(Array[mid]);
    if (nLength > 1)
    {
        p->pLeft = CreateTreeImpl(Array, nLength / 2);
        p->pRight = CreateTreeImpl(Array + mid + 1, nLength / 2 - 1);
    }
    return p;
}
void BinaryTree::DetroyTreeImpl(PTreeNode pTreenode)
{
    if (NULL != pTreenode->pLeft)
    {
        DetroyTreeImpl(pTreenode->pLeft);
    }
    if (NULL != pTreenode->pRight)
    {
        DetroyTreeImpl(pTreenode->pRight);
    }
    delete pTreenode;
    pTreenode = NULL;
}
// 遍历树的对外接口
// 指定遍历类型和是否是非递归遍历,默认是递归遍历
void BinaryTree::Traverse(TraverseType traversetype, bool bRec /*= true*/)
{
    switch (traversetype)
    {
    case PREORDER: // 前序
        if (true == bRec)
        {
            std::cout << "递归前序遍历树\n";
            PreTraverseImpl(m_pRoot);
        }
        else
        {
            std::cout << "非递归前序遍历树\n";
            NoRecPreTraverseImpl(m_pRoot);
        }
        break;
    case INORDER: // 中序
        if (true == bRec)
        {
            std::cout << "递归中序遍历树\n";
            InTraverseImpl(m_pRoot);
        }
        else
        {
            std::cout << "非递归中序遍历树\n";
            NoRecInTraverseImpl(m_pRoot);
        }
        break;
    case POSTORDER: // 后序
        if (true == bRec)
        {
            std::cout << "递归后序遍历树\n";
            PostTraverseImpl(m_pRoot);
        }
        else
        {
            std::cout << "非递归后序遍历树\n";
            NoRecPostTraverseImpl(m_pRoot);
        }
        break;
    case LEVELORDER: // 层序
        std::cout << "层序遍历树\n";
        LevelTraverseImpl(m_pRoot);
        break;
    }
    std::cout << std::endl;
}
// 递归前序遍历树
void BinaryTree::PreTraverseImpl(PTreeNode pTreenode)
{
    if (NULL == pTreenode)
        return;
    std::cout << "Item = " << pTreenode->Node << std::endl;
    PreTraverseImpl(pTreenode->pLeft);
    PreTraverseImpl(pTreenode->pRight);
}
// 非递归前序遍历树
void BinaryTree::NoRecPreTraverseImpl(PTreeNode pTreenode)
{
    if (NULL == pTreenode)
        return;
    TreeNodeStack NodeStack;
    PTreeNode pNode;
    NodeStack.push(pTreenode);
    while (!NodeStack.empty())
    {
        while (NULL != (pNode = NodeStack.top())) // 向左走到尽头
        {
            std::cout << "Item = " << pNode->Node << std::endl; // 访问当前结点
            NodeStack.push(pNode->pLeft); // 左子树根结点入栈
        }
        NodeStack.pop(); // 左子树根结点退栈
        if (!NodeStack.empty())
        {
            pNode = NodeStack.top();
            NodeStack.pop(); // 当前结点退栈
            NodeStack.push(pNode->pRight); // 当前结点的右子树根结点入栈
        }
    }
}
// 中序遍历树
// 中序遍历输出的结果应该和用来初始化树的数组的排列顺序一致
void BinaryTree::InTraverseImpl(PTreeNode pTreenode)
{
    if (NULL == pTreenode)
        return;
    if (NULL != pTreenode->pLeft)
    {
        InTraverseImpl(pTreenode->pLeft);
    }
    std::cout << "Item = " << pTreenode->Node << std::endl;
    if (NULL != pTreenode->pRight)
    {
        InTraverseImpl(pTreenode->pRight);
    }
}
// 非递归中序遍历树
void BinaryTree::NoRecInTraverseImpl(PTreeNode pTreenode)
{
    if (NULL == pTreenode)
        return;
    TreeNodeStack NodeStack;
    PTreeNode pNode;
    NodeStack.push(pTreenode);
    while (!NodeStack.empty())
    {
        while (NULL != (pNode = NodeStack.top())) // 向左走到尽头
        {
            NodeStack.push(pNode->pLeft);
        }
        NodeStack.pop();
        if (!NodeStack.empty() && NULL != (pNode = NodeStack.top()))
        {
            std::cout << "Item = " << pNode->Node << std::endl;
            NodeStack.pop();
            NodeStack.push(pNode->pRight);
        }
    }
}
// 后序遍历树
void BinaryTree::PostTraverseImpl(PTreeNode pTreenode)
{
    if (NULL == pTreenode)
        return;
    if (NULL != pTreenode->pLeft)
    {
        PostTraverseImpl(pTreenode->pLeft);
    }
    if (NULL != pTreenode->pRight)
    {
        PostTraverseImpl(pTreenode->pRight);
    }
    std::cout << "Item = " << pTreenode->Node << std::endl;
}
// 非递归后序遍历树
void BinaryTree::NoRecPostTraverseImpl(PTreeNode pTreenode)
{
    if (NULL == pTreenode)
        return;
    TreeNodeStack NodeStack;
    PTreeNode pNode1, pNode2;
    NodeStack.push(pTreenode);
    pNode1 = pTreenode->pLeft;
    bool bVisitRoot = false; // 标志位,是否访问过根结点
    while (!NodeStack.empty())
    {
        while (NULL != pNode1) // 向左走到尽头
        {
            NodeStack.push(pNode1);
            pNode1 = pNode1->pLeft;
        }
        pNode1 = NodeStack.top();
        NodeStack.pop();
        if (NULL == pNode1->pRight) // 如果没有右子树就是叶子结点
        {
            std::cout << "Item = " << pNode1->Node << std::endl;
            pNode2 = pNode1;
            pNode1 = NodeStack.top();
            if (pNode2 == pNode1->pRight) // 如果这个叶子结点是右子树
            {
                std::cout << "Item = " << pNode1->Node << std::endl;
                NodeStack.pop();
                pNode1 = NULL;
            }
            else // 否则访问右子树
            {
                pNode1 = pNode1->pRight;
            }
        }
        else // 访问右子树
        {
            if (pNode1 == pTreenode || true == bVisitRoot) // 如果已经访问过右子树那么就退出
            {
                std::cout << "Item = " << pNode1->Node << std::endl;
                return;
            }
            else
            {
                if (pNode1 == pTreenode)
                {
                    bVisitRoot = true;
                }
                NodeStack.push(pNode1);
                pNode1 = pNode1->pRight;
            }
        }
    }
}
// 按照树的层次从左到右访问树的结点
void BinaryTree::LevelTraverseImpl(PTreeNode pTreenode)
{
    if (NULL == pTreenode)
        return;
    // 层序遍历用于保存结点的容器是队列
    std::queue<PTreeNode> NodeQueue;
    PTreeNode pNode;
    NodeQueue.push(pTreenode);
    while (!NodeQueue.empty())
    {
        pNode = NodeQueue.front();
        NodeQueue.pop();
        std::cout << "Item = " << pNode->Node << std::endl;
        if (NULL != pNode->pLeft)
        {
            NodeQueue.push(pNode->pLeft);
        }
        if (NULL != pNode->pRight)
        {
            NodeQueue.push(pNode->pRight);
        }
    }
}

main.cpp

/********************************************************************
created: 2006/07/04
filename: main.cpp
author: 李创
purpose: 测试二叉树的算法
*********************************************************************/
#include "BinaryTree.h"
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <iostream>
void DisplayArray(int array[], int length)
{
    for (int i = 0; i < length; i++)
    {
        printf("array[%d] = %d\n", i, array[i]);
    }
}
void CreateNewArray(int array[], int length)
{
    for (int i = 0; i < length; i++)
    {
        array[i] = rand() % 256 + i;
    }
}
int main()
{
    int array[10];
    srand(time(NULL));
    // 创建数组
    CreateNewArray(array, 10);
    DisplayArray(array, 10);
    BinaryTree* pTree = new BinaryTree(array, 10);
    // 测试前序遍历
    pTree->Traverse(BinaryTree::PREORDER);
    std::cout << "root = " << pTree->GetRoot()->Node << std::endl;
    std::cout << "root-left = " << pTree->GetRoot()->pLeft->Node << std::endl;
    std::cout << "root-right = " << pTree->GetRoot()->pRight->Node << std::endl;
    pTree->Traverse(BinaryTree::PREORDER, false);
    // 测试中序遍历
    pTree->Traverse(BinaryTree::INORDER);
    std::cout << "root = " << pTree->GetRoot()->Node << std::endl;
    std::cout << "root-left = " << pTree->GetRoot()->pLeft->Node << std::endl;
    std::cout << "root-right = " << pTree->GetRoot()->pRight->Node << std::endl;
    pTree->Traverse(BinaryTree::INORDER, false);
    // 测试后序遍历
    pTree->Traverse(BinaryTree::POSTORDER);
    std::cout << "root = " << pTree->GetRoot()->Node << std::endl;
    std::cout << "root-left = " << pTree->GetRoot()->pLeft->Node << std::endl;
    std::cout << "root-right = " << pTree->GetRoot()->pRight->Node << std::endl;
    pTree->Traverse(BinaryTree::POSTORDER, false);
    // 测试层序遍历
    pTree->Traverse(BinaryTree::LEVELORDER);
    system("pause");
    delete pTree;
    return 0;
}
推荐文章