C# 二叉树
这里实现了二叉树的创建与插入结点，前中后序遍历的递归实现以及前序遍历的非递归实现，层序遍历的非递归实现。
插入结点时采用二叉排序树的方式，没有处理有相同结点时的情况，按下面代码中插入结点时，构成的二叉树如下：
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
鲁公网安备 37148202000241号