当前位置:首页 > 数据结构与算法 > 正文内容

C# 二叉树

admin6个月前 (12-29)数据结构与算法189

这里实现了二叉树的创建与插入结点,前中后序遍历的递归实现以及前序遍历的非递归实现,层序遍历的非递归实现。

插入结点时采用二叉排序树的方式,没有处理有相同结点时的情况,按下面代码中插入结点时,构成的二叉树如下:

二叉树.jpg

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace _20201225二叉树
{
    class Program
    {
        static void Main(string[] args)
        {
            Tree tree = new Tree(10);
            MethodsOfTree.Insert(tree, 7);
            MethodsOfTree.Insert(tree, 6);
            MethodsOfTree.Insert(tree, 8);
            MethodsOfTree.Insert(tree, 14);
            MethodsOfTree.Insert(tree, 13);
            MethodsOfTree.Insert(tree, 15);
            MethodsOfTree.Insert(tree, 5);

            MethodsOfTree.PreTraversalTree(tree);
            Console.WriteLine();
            MethodsOfTree.PreTraversalTree(tree);
            Console.WriteLine();
            MethodsOfTree.LevelOrderTraversal(tree);

            Console.ReadKey();
        }

    }

    public class Tree
    {
        /// <summary>
        /// 数据
        /// </summary>
        public int Data;
        /// <summary>
        /// 左孩子
        /// </summary>
        public Tree LeftChild;
        /// <summary>
        /// 右孩子
        /// </summary>
        public Tree RightChild;

        //构造函数
        public Tree(int data)
        {
            LeftChild = null;
            RightChild = null;
            Data = data;
        }
    }

    public class MethodsOfTree
    {
        /// <summary>
        /// 按照二叉排序树的方式插入数据
        /// </summary>
        /// <param name="root">二叉树根节点</param>
        /// <param name="newData">待插入的新数据</param>
        public static void Insert(Tree root, int newData)
        {
            int currentNodeValue = root.Data;
            if (currentNodeValue > newData)
            {
                if (root.LeftChild == null)
                {
                    root.LeftChild = new Tree(newData);
                }
                else
                {
                    Insert(root.LeftChild, newData);
                }

            }
            else
            {
                if (root.RightChild == null)
                {
                    root.RightChild = new Tree(newData);
                }
                else
                {
                    Insert(root.RightChild, newData);
                }
            }

        }

        /// <summary>
        /// 二叉树的先序遍历(根左右)
        /// </summary>
        /// <param name="t">二叉树</param>
        public static void PreTraversalTree(Tree t)
        {
            Console.WriteLine(t.Data);
            if (t.LeftChild != null)
            {
                PreTraversalTree(t.LeftChild);
            }
            if (t.RightChild != null)
            {
                PreTraversalTree(t.RightChild);
            }
        }

        /// <summary>
        /// 二叉树的中序遍历(左根右)
        /// </summary>
        /// <param name="t">二叉树</param>
        public static void InTraversalTree(Tree t)
        {
            if (t.LeftChild != null)
            {
                InTraversalTree(t.LeftChild);
            }
            Console.WriteLine(t.Data);
            if (t.RightChild != null)
            {
                InTraversalTree(t.RightChild);
            }
        }

        /// <summary>
        /// 二叉树的后序遍历(左右根)
        /// </summary>
        /// <param name="t">二叉树</param>
        public static void PosTraversalTree(Tree t)
        {
            if (t.LeftChild != null)
            {
                PosTraversalTree(t.LeftChild);
            }
            if (t.RightChild != null)
            {
                PosTraversalTree(t.RightChild);
            }
            Console.WriteLine(t.Data);
        }

        /// <summary>
        /// 二叉树的前序遍历非递归实现
        /// </summary>
        /// <param name="root">根节点</param>
        public static void PreTraversalTree2(Tree root)
        {
            Stack<Tree> stack = new Stack<Tree>();
            Tree temp = root;
            while (temp != null || stack.Count != 0)
            {
                while (temp != null)
                {
                    Console.WriteLine(temp.Data);
                    stack.Push(temp);
                    temp = temp.LeftChild;
                }
                if (stack.Count != 0)
                {
                    temp = stack.Pop();
                    temp = temp.RightChild;
                }
            }
        }

        /// <summary>
        /// 二叉树的层序遍历
        /// </summary>
        /// <param name="root">二叉树的根节点</param>
        public static void LevelOrderTraversal(Tree root)
        {
            Queue<Tree> queue = new Queue<Tree>();
            queue.Enqueue(root);
            while (queue.Count != 0)
            {
                Tree tempNode = queue.Dequeue();
                Console.WriteLine(tempNode.Data);
                if (tempNode.LeftChild != null)
                {
                    queue.Enqueue(tempNode.LeftChild);
                }
                if (tempNode.RightChild != null)
                {
                    queue.Enqueue(tempNode.RightChild);
                }
            }
        }
    }
}

20200104更新,增加部分C++的代码,稍有不同的是有删除二叉树的操作,使用的是后序遍历的递归实现,不过是把输出数据改成了释放内存。

#include <iostream>
#include <queue>
using namespace std;

struct TreeNode
{
    int Data;
    TreeNode *LeftChild = NULL;
    TreeNode *RightChild = NULL;
};

//插入结点
void InsertNode(TreeNode *root, int newData);
//前序遍历
void PreTranverseTree(TreeNode *root);
//层序遍历
void LevelTranversalTree(TreeNode *root);
//删除树
void DeleteTree(TreeNode *root);

int main()
{
    TreeNode *root = new TreeNode{10};
    InsertNode(root, 7);
    InsertNode(root, 6);
    InsertNode(root, 8);
    InsertNode(root, 14);
    InsertNode(root, 13);
    InsertNode(root, 15);
    InsertNode(root, 5);

    PreTranverseTree(root);

    DeleteTree(root);
    //LevelTranversalTree(root);
}

void InsertNode(TreeNode *root, int newData)
{
    if (root->Data > newData)
    {
        if (root->LeftChild == NULL)
        {
            root->LeftChild = new TreeNode{newData};
        }
        else
        {
            InsertNode(root->LeftChild, newData);
        }
    }
    else
    {
        if (root->RightChild == NULL)
        {
            root->RightChild = new TreeNode{newData};
        }
        else
        {
            InsertNode(root->RightChild, newData);
        }
    }
}

void PreTranverseTree(TreeNode *root)
{
    cout << root->Data << endl;
    if (root->LeftChild != NULL)
    {
        PreTranverseTree(root->LeftChild);
    }
    if (root->RightChild != NULL)
    {
        PreTranverseTree(root->RightChild);
    }
}

void LevelTranversalTree(TreeNode *root)
{
    queue<TreeNode *> q;

    q.push(root);

    while (!q.empty())
    {
        TreeNode *temp = q.front();
        q.pop();

        cout << temp->Data << endl;

        if (temp->LeftChild != NULL)
        {
            q.push(temp->LeftChild);
        }
        if (temp->RightChild != NULL)
        {
            q.push(temp->RightChild);
        }
    }
}

void DeleteTree(TreeNode *root)
{
    if (root == NULL)
        return;
    DeleteTree(root->LeftChild);
    DeleteTree(root->RightChild);
    delete root;
    root = NULL;
    return;
}

下一篇关于二叉树的链接在这:https://lovedm.club/?id=126

版权声明:本文由cyhu's essay发布,如需转载请注明出处。

本文链接:https://lovedm.club/?id=110

相关文章

数据结构

数据结构

数据结构:逻辑结构:反映数据元素之间的逻辑关系。包括:集合:数据结构中的元素之间除了“同属一个集合” 的相互关系外,别无其他关系。线性结构:数据结构中的元素存在一对一的相互关系。树形结构:数据结构中的...

线性表

线性表

线性表(linear list)是数据结构的一种,一个线性表是n个具有相同特性的数据元素的有限序列。数据元素是一个抽象的符号,其具体含义在不同的情况下一般不同。1.集合中必存在唯一的一个“第一元素”。...

中缀表达式转后缀表达式

中缀表达式转后缀表达式

转换过程如下:1、运算数:直接输出;2、左括号:压入堆栈;3、右括号:将栈顶的运算符弹出并输出,直到遇到左括号(出栈,不输出);4、运算符:若优先级大于栈顶运算符时,则把它压栈;若优先级小于等于栈顶运...

单链表

单链表

单链表存储一个直接后继的地址,用一组任意的存储单元存储线性表中的元素。数据域(数据元素)+指针域(指示后继元素存储位置) = 结点,如下图:a和b是两个结点,其中a的指针域保存了指向b的地址。以结点的...

线性表的顺序结构(顺序表)

线性表的顺序结构(顺序表)

顺序表,线性表的一种,其存储时需要开辟一块足够大的连续的空间,数据之间的存放是相连的,中间没有空隙。顺序表的初始化:需要指定顺序表的大小,这个大小要足够大,还要将元素个数初始化为0。按照位置查找元素:...

以层序插入二叉树结点

这里以层序插入二叉树的结点,以先序遍历输出。上一篇关于二叉树的内容在这里:https://lovedm.club/?id=110using System; using Syste...