二叉树的节点结构
//二叉链表表示 private TreeNode leftNode; private TreeNode rightNode; int data;
一、创建一个二叉树
//创建一个树 //如果输入有问题转换就有异常产生 public TreeNode CreateTree() { try { Console.WriteLine("===If you input -1 it will be break!"); Console.Write("===Input you data:"); int data = int.Parse(Console.ReadLine()); Console.WriteLine("===----------------------"); if (data == -1) return null; else { TreeNode node = new TreeNode(); node.Data = data; Console.WriteLine("\n===Input {0} left data:", data); node.LeftNode = CreateTree(); Console.WriteLine("\n===Input {0} right data:", data); node.RightNode = CreateTree(); return node; } } catch (Exception) { Console.WriteLine("\n===Yon Input Error! So this node is null!!!"); return null; } }
二、先序遍历递归
public void DLR(TreeNode t) { if(!IsNull(t)){ Console.Write("{0} ",t.Data); DLR(t.LeftNode); DLR(t.RightNode); } }
//非递归实现 public void test1(TreeNode root) { Stack<TreeNode> stack = new Stack<TreeNode>(); TreeNode index=root; while(index!=null||stack.Count>0){ if(index!=null){ Console.Write("{0} ",index.Data); stack.Push(index); index = index.LeftNode; } else { index = stack.Pop(); //stack.Pop(); index = index.RightNode; } } }
三、中序遍历
public void LDR(TreeNode t) { if (!IsNull(t)) { LDR(t.LeftNode); Console.Write("{0} ", t.Data); LDR(t.RightNode); } }
//中序非递归 public void test2(TreeNode root) { Stack<TreeNode> stack = new Stack<TreeNode>(); TreeNode index = root; while (index != null || stack.Count > 0) { if (index != null) { // Console.Write("{0} ", index.Data); stack.Push(index); index = index.LeftNode; } else { index = stack.Pop(); Console.Write("{0} ", index.Data); //stack.Pop(); index = index.RightNode; } } }
四、后序遍历
public void LRD(TreeNode t) { if (!IsNull(t)) { LRD(t.LeftNode); LRD(t.RightNode); Console.Write("{0} ", t.Data); } }
//非递归后序 public void test3(TreeNode root){ Stack<TreeNode> stack = new Stack<TreeNode>(); Stack<int> flag = new Stack<int>(); TreeNode index=root; //index为树木的根了 //然后都入栈 第一次访问的标记为0 ,第二次访问为1 while (index != null || stack.Count > 0) { if (index != null) { stack.Push(index); index = index.LeftNode; flag.Push(0); }else { index = stack.Pop(); int flag_index = flag.Pop(); if (flag_index == 0) { flag.Push(1); stack.Push(index); index = index.RightNode; } else { Console.Write("{0} ",index.Data); index = null; } } } }
五、借助队列按层遍历(广度优先遍历)
public void test4(TreeNode root) { Queue<TreeNode> queue = new Queue<TreeNode>(); queue.Enqueue(root); while(queue.Count>0){ TreeNode t = queue.Dequeue(); Console.Write(t.Data+" "); if (t.LeftNode != null) queue.Enqueue(t.LeftNode); if (t.RightNode != null) queue.Enqueue(t.RightNode); } }
六、深度的计算
public int deep(TreeNode root) { if (root == null) return 0; else { int deepLeft = 0; int deepRight = 0; deepLeft = deep(root.LeftNode); deepRight = deep(root.RightNode); return deepLeft > deepRight ? deepLeft + 1 : deepRight + 1; }
其他:叶子数的计算
前驱后继的获取(中序线索二叉树)
树森林-〉二叉树
相关推荐
1.二叉树的基本操作实现【问题描述】建立一棵二叉树,用递归方法实现二叉树的如下基本操作:(1)按先序序列构造一棵二叉链表表示的二叉树T;...ABCDEFG【选做内容】采用非递归算法实现二叉树遍历。
二叉树遍历问题二叉树遍历问题二叉树遍历问题二叉树遍历问题二叉树遍历问题二叉树遍历问题二叉树遍历问题二叉树遍历问题二叉树遍历问题二叉树遍历问题二叉树遍历问题二叉树遍历问题二叉树遍历问题二叉树遍历问题...
易语言二叉树遍历源码,二叉树遍历,二叉树_取下级树,内存_读整数内存,读整数内存_
二叉树遍历 二叉树遍历
1、二叉树的遍历是指从根节点出发,按照某种次序依次访问二叉树中的所有结点,使得每个节点被访问依次且仅被访问一次。 2、前序遍历: 规则是若二叉树为空,则空操作返回,否则先访问根节点,然后前序遍历左子树,...
二叉树遍历问题 ⼀、⼆叉树的重要性 很多经典算法如 回溯、⼴度优先遍历、分治、动态规划等通常需要转化为树的问题,⽽树的题⽬难免涉及到递归的问题,因此掌握树的三 种遍历框架是必须的。 先序遍历:根,左,右 ...
二叉树遍历问题-二叉树遍历问题
主要介绍了php实现的二叉树遍历算法,结合具体实例形式分析了php针对二叉树的常用前序、中序及后序遍历算法实现技巧,需要的朋友可以参考下
ppt画出了二叉树遍历的流程图流程图,设计先、中、后序的递归与非递归思想,即宽度优先的实现,详细对应遍历思想的代码实现见博客:https://blog.csdn.net/weixin_43763430/article/details/124417058
二叉树遍历,c语言 实现数据结构二叉树遍历
二叉树遍历问题 二叉树遍历问题-前序, 中序, 后序二叉树遍历问题-前序, 中序, 后序二叉树遍历问题-前序, 中序, 后序二叉树遍历问题-前序, 中序, 后序二叉树遍历问题-前序, 中序, 后序二叉树遍历问题-前序...
对于二叉树,有前序、中序以及后序三种遍历方法。因为树的定义本身就是递归定义,因此采用递归的方法去实现树的三种遍历不仅容易理解而且代码很简洁。而对于树的遍历若采用非递归的方法,就要采用栈去模拟实现
本程序主要实现的是二叉树的先序,中序,后序遍历算法
许多实际问题抽象出来的数据结构往往是二叉树形式,即使是一般的树也能简单地转换为二叉树,而且二叉树的存储结构及其算法都较为简单,因此二叉树显得特别重要。二叉树特点是每个结点最多只能有两棵子树,且有左右之...
对二叉树的生存,二叉树遍历等,有前序的,中序的,后序的,层次的,求结点数的等.