https://www.cnblogs.com/lfri/p/10256069.html

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

namespace BinaryTree
{
    //节点
    class TreeNode
    {
        public int data;
        public TreeNode left;
        public TreeNode right;
        public TreeNode(int data)
        {
            this.data = data;
            left = null;
            right = null;
        }
    }
    //树的操作
    class Tree
    {
        public TreeNode root = null;
        //前序遍历
        public void Preorder(TreeNode root)
        {
            if (root == null)
                return;
            Console.Write(root.data + " ");
            Preorder(root.left);
            Preorder(root.right);
        }
        //中序遍历
        public void Inorder(TreeNode root)
        {
            if (root == null)
                return;
            Inorder(root.left);
            Console.Write(root.data + " ");
            Inorder(root.right);
        }
        //后序遍历
        public void Postorder(TreeNode root)
        {
            if (root == null)
                return;
            Postorder(root.left);
            Postorder(root.right);
            Console.Write(root.data + " ");
        }
        //层序遍历
        public void Levelorder(TreeNode root)
        {
            Queue<TreeNode> queue = new Queue<TreeNode>();
            TreeNode current;
            queue.Enqueue(root);
            while (queue.Count > 0)
            {
                current = queue.Dequeue();
                if (current != null)
                {
                    Console.Write(current.data + " ");
                    queue.Enqueue(current.left);
                    queue.Enqueue(current.right);
                }
            }
        }
        //前序遍历(非递归)
        public void Preorder2(TreeNode root)
        {
            Stack<TreeNode> stack = new Stack<TreeNode>();
            TreeNode current = root;
            while (current != null || stack.Count > 0)
            {
                while (current != null)
                {
                    Console.Write(current.data + " ");
                    stack.Push(current);
                    current = current.left;
                }
                if (stack.Count > 0)
                {
                    current = stack.Pop().right;
                }
            }
        }
        //中序遍历(非递归)
        public void Inorder2(TreeNode root)
        {
            Stack<TreeNode> stack = new Stack<TreeNode>();
            TreeNode current = root;
            while (current != null || stack.Count > 0)
            {
                while (current != null)
                {
                    stack.Push(current);
                    current = current.left;
                }
                if (stack.Count > 0)
                {
                    current = stack.Pop();
                    Console.Write(current.data + " ");
                    current = current.right;
                }
            }
        }
        //后序遍历(非递归)
        public void Postorder2(TreeNode root)
        {
            Stack<TreeNode> stack = new Stack<TreeNode>();
            TreeNode current = root;
            TreeNode visited = null;
            while (current != null)
            {
                stack.Push(current);
                current = current.left;
            }
            while (stack.Count > 0)
            {
                if (stack.Peek().right == null || stack.Peek().right == visited)
                {
                    current = stack.Pop();
                    Console.Write(current.data + " ");
                    visited = current;
                }
                else
                {
                    current = stack.Peek().right;
                    while (current != null)
                    {
                        stack.Push(current);
                        current = current.left;
                    }
                }
            }
        }
        //求树的高度
        public int Height(TreeNode root)
        {
            if (root == null)
                return 0;
            int leftHeight;
            int rightHeight;
            leftHeight = Height(root.left);
            rightHeight = Height(root.right);
            return leftHeight > rightHeight ? 1 + leftHeight : 1 + rightHeight;
        }
        //求树的节点数
        public int NodeCount(TreeNode root)
        {
            if (root == null)
                return 0;
            int count;
            count = NodeCount(root.left) + NodeCount(root.right);
            return count + 1;
        }
        //输出所有的叶子节点
        public void PrintLeafNode(TreeNode root)
        {
            if (root == null)
                return;
            if (root.left == null && root.right == null)
            {
                Console.Write(root.data + " ");
                return;
            }
            if (root.left != null)
                PrintLeafNode(root.left);
            if (root.right != null)
                PrintLeafNode(root.right);
        }
        //销毁二叉树
        public void DestoryTree(TreeNode root)
        {
            if (root == null)
                return;
            DestoryTree(root.left);
            root.left = null;
            DestoryTree(root.right);
            root.right = null;
        }
        //查找节点
        public TreeNode Find(TreeNode root, int data)
        {
            TreeNode node = null;
            if (root == null)
                return null;
            if (root.data == data)
                return root;
            node = Find(root.left, data);
            if (node != null)
                return node;
            node = Find(root.right, data);
            return node;
        }
        //求树的节点的最大值
        public int Max(TreeNode root)
        {
            if (root == null)
                return 0;
            int a = Max(root.left);
            int b = Max(root.right);
            if (a > b)
                return a > root.data ? a : root.data;
            else
                return b > root.data ? b : root.data;
        }
        //求树的深度
        public int Depth(TreeNode root)
        {
            if (root == null)
                return 0;
            int left = Depth(root.left);
            int right = Depth(root.right);
            return 1 + (left > right ? left : right);
        }
        //求指定节点所在的高度
        public int NodeHeight(TreeNode root, int data, int h = 1)
        {
            int height;
            if (root == null)
                return 0;
            if (root.data == data)
                return h;
            height = NodeHeight(root.left, data, h + 1);
            if (height != 0)
                return height;
            height = NodeHeight(root.right, data, h + 1);
            return height;
        }
        //求第k层的节点数
        public int LevelNodeCount(TreeNode root,int k,int h = 1)
        {
            if (root == null)
                return 0;
            if (h == k) return 1;
            return LevelNodeCount(root.left, k, h + 1) + LevelNodeCount(root.right, k, h + 1);
        }
        //求第k层的叶子节点数
        public int LevelLeafNodeCount(TreeNode root,int k,int h = 1)
        {
            if (root == null)
                return 0;
            if (h == k && root.left == null && root.right == null) return 1;
            return LevelLeafNodeCount(root.left, k, h + 1) + LevelLeafNodeCount(root.right, k, h + 1);
        }
        //求只有一个孩子的节点总数
        public int OneChildNodeCount(TreeNode root)
        {
            if (root == null)
                return 0;
            if ((root.left != null && root.right == null) || (root.left == null && root.right != null))
                return OneChildNodeCount(root.left) + OneChildNodeCount(root.right) + 1;
            return OneChildNodeCount(root.left) + OneChildNodeCount(root.right);
        }
        //判断两个树是否相似，相似是说可以值不等，但是形态需要一样
        public bool Like(TreeNode root1,TreeNode root2)
        {
            if (root1 == null && root2 == null)
            {
                return true;
            }
            else if (root1 != null && root2 != null)
            {
                return Like(root1.left, root2.left) && Like(root1.right, root2.right);
            }
            else
            {
                return false;
            }
        }
        //输入某个点的所有祖先
        public bool AllFather(TreeNode root,int x)
        {
            if (root == null)
                return false;
            if ((root.left != null && root.left.data == x) || (root.right != null && root.right.data == x))
            {
                Console.Write(root.data + " ");
                return true;
            }
            bool left = AllFather(root.left, x);
            if(left)
            {
                Console.Write(root.data + " ");
                return true;
            }
            bool right = AllFather(root.right, x);
            if(right)
            {
                Console.Write(root.data + " ");
                return true;
            }
            return false;
        }
        //某节点的所有子孙
        public void AllChild(TreeNode root,int x)
        {
            if (root == null)
                return;
            if(root.data == x)
            {
                Preorder(root.left);
                Preorder(root.right);
            }
            else
            {
                AllChild(root.left, x);
                AllChild(root.right, x);
            }
        }
        //判断两个节点是否为兄弟
        public bool Brother(TreeNode root,int x,int y)
        {
            if (root == null)
                return false;
            if (root.left != null && root.right != null)
                if ((root.left.data == x && root.right.data == y) || (root.left.data == y && root.left.data == x))
                    return true;
            return Brother(root.left, x, y) || Brother(root.right, x, y);
        }
        //复制二叉树
        public void Copy(TreeNode root1,ref TreeNode root2)
        {
            if (root1 == null)
            {
                root2 = null;
                return;
            }
            root2 = new TreeNode(root1.data);
            Copy(root1.left, ref root2.left);
            Copy(root1.right, ref root2.right);
        }
        //交换二叉树的左右子树
        public void Change(TreeNode root)
        {
            if (root == null)
                return;
            if (root.left == null && root.right == null)
                return;
            TreeNode temp;
            temp = root.left;
            root.left = root.right;
            root.right = temp;

            Change(root.left);
            Change(root.right);
        }
        //判断一棵树是不是完全二叉树
        public bool CompleteTree(TreeNode root)
        {
            Queue<TreeNode> queue = new Queue<TreeNode>();
            bool b;
            queue.Enqueue(root);
            TreeNode node;
            while(queue.Count != 0)
            {
                node = queue.Dequeue();
                if (node.left != null)
                    queue.Enqueue(node.left);
                else
                {
                    if (node.right != null)
                        return false;
                    break;
                }
                if (node.right != null)
                    queue.Enqueue(node.right);
                else
                    break;
            }
            while (queue.Count != 0)
            {
                node = queue.Dequeue();
                if (node.left != null || node.right != null)
                {
                    return false;
                }
            }
            return true;
        }
        //判断一颗树是不是满二叉树
        public bool FullTree(TreeNode root)
        {
            if (root == null)
                return true;
            if(FullTree(root.left) && FullTree(root.right))
            {
                if (Depth(root.left) == Depth(root.right))
                    return true;
            }
            return false;
        }
    }
    class Program
    {
        static void Main(string[] args)
        {
            Tree tree = new Tree();
            TreeNode node1 = new TreeNode(1);
            TreeNode node2 = new TreeNode(2);
            TreeNode node3 = new TreeNode(3);
            TreeNode node4 = new TreeNode(4);
            TreeNode node5 = new TreeNode(5);
            TreeNode node6 = new TreeNode(6);
            TreeNode node7 = new TreeNode(7);
            TreeNode node8 = new TreeNode(8);
            TreeNode node9 = new TreeNode(9);
            TreeNode node10 = new TreeNode(10);
            tree.root = node1;
            node1.left = node2;
            node1.right = node3;
            node2.right = node4;
            node3.left = node5;
            node3.right = node6;
            node4.left = node10;
            node5.left = node7;
            node5.right = node8;
            node7.left = node9;

            Tree tree2 = new Tree();
            TreeNode node11 = new TreeNode(11);
            TreeNode node12 = new TreeNode(12);
            TreeNode node13 = new TreeNode(13);
            TreeNode node14 = new TreeNode(14);
            TreeNode node15 = new TreeNode(15);
            TreeNode node16 = new TreeNode(16);
            TreeNode node17 = new TreeNode(17);
            TreeNode node18 = new TreeNode(18);
            TreeNode node19 = new TreeNode(19);
            TreeNode node20 = new TreeNode(20);
            tree2.root = node11;
            node11.left = node12;
            node11.right = node13;
            node12.right = node14;
            node13.left = node15;
            node13.right = node16;
            node14.left = node20;
            node15.left = node17;
            node15.right = node18;
            node17.left = node19;

            Tree tree4 = new Tree();
            TreeNode node21 = new TreeNode(21);
            TreeNode node22 = new TreeNode(22);
            TreeNode node23 = new TreeNode(23);
            TreeNode node24 = new TreeNode(24);
            TreeNode node25 = new TreeNode(25);
            tree4.root = node21;
            node21.left = node22;
            node21.right = node23;
            node22.left = node24;
            node22.right = node25;

            Tree tree5 = new Tree();
            TreeNode node31 = new TreeNode(31);
            TreeNode node32 = new TreeNode(32);
            TreeNode node33 = new TreeNode(33);
            TreeNode node34 = new TreeNode(34);
            TreeNode node35 = new TreeNode(35);
            TreeNode node36 = new TreeNode(36);
            TreeNode node37 = new TreeNode(37);
            tree5.root = node31;
            node31.left = node32;
            node31.right = node33;
            node32.left = node34;
            node32.right = node35;
            node33.left = node36;
            node33.right = node37;

            Console.Write("前序遍历:");
            tree.Preorder(tree.root);
            Console.Write("\n中序遍历:");
            tree.Inorder(tree.root);
            Console.Write("\n后序遍历:");
            tree.Postorder(tree.root);
            Console.Write("\n层序遍历:");
            tree.Levelorder(tree.root);
            Console.Write("\n前序遍历(非递归):");
            tree.Preorder2(tree.root);
            Console.Write("\n中序遍历(非递归):");
            tree.Inorder2(tree.root);
            Console.Write("\n后序遍历(非递归):");
            tree.Postorder2(tree.root);
            Console.Write("\n树的高度:" + tree.Height(tree.root));
            Console.Write("\n树的节点数:" + tree.NodeCount(tree.root));
            Console.Write("\n树的叶子节点数:");
            tree.PrintLeafNode(tree.root);
            Console.Write("\n树的最大值:" + tree.Max(tree.root));
            TreeNode node = tree.Find(tree.root, 9);
            Console.Write("\n查找到的节点:" + node.data);
            Console.Write("\n求树的深度:" + tree.Depth(tree.root));
            Console.Write("\n查找节点所在的高度（0表示没有该节点）:" + tree.NodeHeight(tree.root, 9));
            Console.Write("\n某层的节点数:" + tree.LevelNodeCount(tree.root, 3));
            Console.Write("\n某层的叶子节点个数:" + tree.LevelLeafNodeCount(tree.root, 1));
            Console.Write("\n只有一个孩子的节点的个数:" + tree.OneChildNodeCount(tree.root));
            Console.Write("\n判断两个树是否相似:" + tree.Like(tree.root, tree2.root));
            Console.Write("\n某节点的所有祖先:");
            tree.AllFather(tree.root, 9);
            Console.Write("\n某节点的所有子孙:");
            tree.AllChild(tree.root, 3);
            Console.Write("\n判断两个节点是否为兄弟节点:" + tree.Brother(tree.root, 10, 7));
            Console.Write("\n复制二叉树(复制后的二叉树前序遍历):");
            Tree tree3 = new Tree();
            tree.Copy(tree.root,  ref tree3.root);
            tree.Preorder(tree3.root);
            Console.Write("\n交换左右子树(交换后的二叉树前序遍历):");
            tree.Change(tree3.root);
            tree.Preorder(tree3.root);
            Console.Write("\n判断是否是完全二叉树:" + tree.CompleteTree(tree4.root));
            Console.Write("\n判断是否是满二叉树:" + tree.FullTree(tree5.root));

            Console.ReadLine();
        }
    }
}