来自大佬群主的第二题

所谓层次遍历，是将二叉树中的元素从根节点按照节点层数一层层的输出。

代码如下：

int GetDepth(bitreenode *root)
{
    int depth=0;
    bitreenode *p=root;
    queue<bitreenode*> q;
    q.push(p);  //根指针入队
    while(!q.empty())
    {
        depth++;  //高度加一
        int width=q.size();  //获取当前层次宽度
        for(int i=0;i<width;i++)
        {
            p=q.front();  //获取队顶元素
            q.pop();  //弹出队顶元素
            if(p->leftchild!=NULL)  //左孩子入队
                q.push(p->leftchild);
            if(p->rightchild!=NULL)  //右孩子入队
                q.push(p->rightchild);
        }

    }
    cout<<depth<<endl;
}

二叉树的前序遍历

二叉树的中序遍历

二叉树的后序遍历

二叉树的前层次序遍历

求叶子节点

求树高

又前序遍历和中序遍历求树

Java代码拿去即可运行

package leetcode;

public class TreeNode {

    private Integer value;
    private TreeNode left;
    private TreeNode right;


    public TreeNode() {
    }

    public TreeNode(Integer value) {
        this.value=value;
    }

    public TreeNode(Integer value, TreeNode left, TreeNode right) {
        this.value = value;
        this.left = left;
        this.right = right;
    }

    public Integer getValue() {
        return value;
    }

    public void setValue(Integer value) {
        this.value = value;
    }

    public TreeNode getLeft() {
        return left;
    }

    public void setLeft(TreeNode left) {
        this.left = left;
    }

    public TreeNode getRight() {
        return right;
    }

    public void setRight(TreeNode right) {
        this.right = right;
    }
}

package tree;

import leetcode.TreeNode;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Objects;

public class Test {
    public static void main(String[] args) {
//        TreeNode treeNode1 = new TreeNode(1);
//        TreeNode treeNode2 = new TreeNode(2);
//        TreeNode treeNode3 = new TreeNode(3);
//        TreeNode treeNode4 = new TreeNode(4);
//        TreeNode treeNode5 = new TreeNode(5);
//        treeNode2.setLeft(treeNode4);
//        treeNode2.setRight(treeNode5);
//        treeNode1.setLeft(treeNode2);
//        treeNode1.setRight(treeNode3);
//        System.out.println(getHeight(treeNode1));
        int[] a={1,2,4,5,3};
        int[] b={4,2,5,1,3};
        TreeNode treeNode1=buildTree(a,b);
        LevelOrderTraversal(treeNode1);
    }

    /*************先序遍历****************/
    static void PreOrderTraversal(TreeNode treeNode) {
        if (treeNode != null) {
            System.out.println(treeNode.getValue()); // 打印根
            PreOrderTraversal(treeNode.getLeft());  // 进入左子树
            PreOrderTraversal(treeNode.getRight());  // 进入右子树
        }
    }

    /*************中序遍历****************/
    static void midOrderTraversal(TreeNode treeNode) {
        if (treeNode != null) {

            midOrderTraversal(treeNode.getLeft());  // 进入左子树
            System.out.println(treeNode.getValue()); // 打印根
            midOrderTraversal(treeNode.getRight());  // 进入右子树
        }
    }

    /*************后序遍历****************/
    static void lastOrderTraversal(TreeNode treeNode) {
        if (treeNode != null) {
            lastOrderTraversal(treeNode.getLeft());  // 进入左子树
            lastOrderTraversal(treeNode.getRight());  // 进入右子树
            System.out.println(treeNode.getValue()); // 打印根
        }
    }

    /**********层次遍历*************/
    public static void LevelOrderTraversal(TreeNode treeNode) {
        LinkedList<TreeNode> q = new LinkedList<>();   // 创建队列
        TreeNode node;
        if (Objects.isNull(treeNode))
            return;

        q.push(treeNode);  // treeNode 入队
        while (!q.isEmpty()) {
            node = q.getFirst();  // 访问队首元素
            q.pop();  // 出队
            System.out.println(node.getValue().toString());
            if (node.getLeft() != null) {// 如果存在左儿子结点
                q.addLast(node.getLeft());  // 入队
            }
            if (node.getRight() != null) {
                q.addLast(node.getRight());
            }
        }
    }

    /***************输出叶子结点********************/
    static void findLeaves(TreeNode treeNode) {
        if (treeNode != null) {
            if (Objects.isNull(treeNode.getLeft()) && Objects.isNull(treeNode.getRight())) {
                System.out.println(treeNode.getValue()); // 打印根
            }
            findLeaves(treeNode.getLeft());  // 进入左子树
            findLeaves(treeNode.getRight());  // 进入右子树
        }
    }

    /********************树的高度*****************/
    static int getHeight(TreeNode treeNode) {
        int hl, hr, maxh;
        if (treeNode != null) {
            hl = getHeight(treeNode.getLeft());  // 求左子树高度
            hr = getHeight(treeNode.getRight());  // 求右子树高度
            maxh = (hl > hr) ? hl : hr;
            return maxh + 1;  // 当前结点高度为左右子树最大的高度+1
        } else
            return 0;
    }
    /******************前序中序遍历序列构造二叉树**************************/
    public static TreeNode buildTree(int[] preorder, int[] inorder) {
        if(preorder.length==0)return null;
        TreeNode root = new TreeNode(preorder[0]);
        int num=0;
        for(int i =0; i<inorder.length; i++){
            if(inorder[i]==root.getValue()){
                num=i;
                break;
            }
        }
        int[] preLeft = Arrays.copyOfRange(preorder,1,num+1);
        int[] preRight = Arrays.copyOfRange(preorder,num+1,preorder.length);

        int[] inoLeft = Arrays.copyOfRange(inorder,0,num);
        int[] inoRight = Arrays.copyOfRange(inorder,num+1,inorder.length);
        root.setLeft(buildTree(preLeft,inoLeft));
        root.setRight(buildTree(preRight,inoRight));
        return root;
    }


}

递归和非递归方法（层次遍历）计算二叉树高度

1.递归方式计算二叉树高度

int Btdepth(BiTree T){
    if(!T) return 0;
    ldep=Btdepth(T->lchild);
    rdep=Btdepth(T->rchild);
    return ldep>rdep? ldep+1:rdep+1;
}

2.层次遍历方法计算二叉树高度：
算法思想：last指向每层最右结点，level为高度。从头节点开始，
边入队，然后再出队进行层次遍历，并将孩子结点入队，此时rear
指向下一层最右结点。而我们在出队遍历时，遍历完当前层front
指向的也是最右结点。所以在代码中，front==last作为判断遍历完
当前层的条件。rear指向的是下层的最右结点，故将last赋值为rear。

int Btdepth(BiTree T){
    if(!T) return 0;
    int last=0, level=0;
    int front=-1, rear=-1;
    BiTree Q[MaxSize];//设置队列Q，元素为二叉树的结点指针，且容量足够
    Q[++rear]=T;//根节点入队
    BiTree p;
    while(front<rear){//队不空则循环
        p=Q[++front];//队列元素出队，即正在访问的结点
        if(p->lchild) Q[++rear]=p->lchild;//左孩子入队
        if(p->rchild) Q[++rear]=r->rchild;//有孩子入队
        if(front==last){//处理该层的最右结点
            level++;//层数加1
            last=rear;//last指向下层
        }
    }
}