二叉树的有关操作

二叉树链式存储的建立，遍历等

#include<stdio.h>
#include<malloc.h>

struct BTNode{
    char data;//数据域
    struct BTNode * pLchild;//p是指针，L是左，child是孩子；即为左子树指针
    struct BTNode * pRchild//右子树指针
}
//函数声明
struct BTNode * CreateBTree();//生成根节点地址和二叉树
PreTraverseBTree();//先序遍历
InTraverseBTree();//中序遍历
PostTraverseBTree();//后序遍历

int main(){
   struct BTNode * pT = CreateBTree();//获取根节点地址

   PreTraverseBTree(pT);//先序遍历
   InTraverseBTree(pT);//中序遍历
   PostTraverseBTree(pT);//后序遍历

    return 0;
}

struct BTNode * CreateBTree(){
    //静态声明结点，动态分配内存
    struct BTNode pA = (struct BTNode *)malloc(sizeof(struct BTNode));
    struct BTNode pB = (struct BTNode *)malloc(sizeof(struct BTNode));
    struct BTNode pC = (struct BTNode *)malloc(sizeof(struct BTNode));
    struct BTNode pD = (struct BTNode *)malloc(sizeof(struct BTNode));
    struct BTNode pE = (struct BTNode *)malloc(sizeof(struct BTNode));

    //各个结点数据域存值
    pA->data = 'A';
    pB->data = 'B';
    pC->data = 'C';
    pD->data = 'D';
    pE->data = 'E';

    //每个结点的左右指针域都要指向一个地址，注：为空就写NULL
    pA->pLchild = pB;//根节点A的左指针域指向B结点的地址
    pA->pRchild = pC;//根节点A的右指针域指向C结点的地址
    pB->pLchild =  pB->pRchild = NULL;//结点B的左右指针域都为空 
    pC->pLchild = pD;//节点C的左指针域指向D结点的地址
    pC->pRchild = NULL;//结点C的右指针域为空
    pD->pLchild = NULL;//结点D的左指针域为空
    pD->pRchild = pE;//结点D的右指针域指向E结点的地址
    pE->pLchild =  pE->pRchild = NULL;//结点E的左右指针域都为空 

    return pA;//返回根节点A的地址
}

//先序遍历
PreTraverseBTree(struct BTNode * pT){
    //每次递归加判断，若先遍历左子树全部为空就结束递归，才能遍历右子树
    if(pT!=NULL){

     printf("%c\n",pT->data);//先访问根节点

     if(pT->pLchild!=NULL){
         PreTraverseBTree(pT->pLchild);//pT->pLchild可以代表整个左子树
     }//再访问左子树

     if((pT->pRchild!=NULL){
         PreTraverseBTree(pT->pRchild);//pT->pRchild可以代表整个右子树
     }//最后访问右子树
    } 
}

//中序遍历
InTraverseBTree(struct BTNode * pT){
    if(pT!=NULL){

     if(pT->pLchild!=NULL){
         PreTraverseBTree(pT->pLchild);//pT->pLchild可以代表整个左子树
     }//先访问左子树

      printf("%c\n",pT->data);//再访问根节点

     if((pT->pRchild!=NULL){
         PreTraverseBTree(pT->pRchild);//pT->pRchild可以代表整个右子树
     }//最后访问右子树
    } 
}

//后序遍历
PostTraverseBTree(struct BTNode * pT){
   if(pT!=NULL){

     if(pT->pLchild!=NULL){
         PreTraverseBTree(pT->pLchild);//pT->pLchild可以代表整个左子树
     }//先访问左子树

     if((pT->pRchild!=NULL){
         PreTraverseBTree(pT->pRchild);//pT->pRchild可以代表整个右子树
     }//再访问右子树

     printf("%c\n",pT->data);//最后访问根节点
    }  
}

二叉树的两种遍历(迭代递归)

二叉树的前序遍历

示例:

输入: [1,null,2,3]  
   1
    \
     2
    /
   3 

输出: [1,2,3]

解答1(递归)

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        helper(root,res);
        return res;
    }
    public void helper(TreeNode root,List<Integer> res){
        if(root != null){
            res.add(root.val);//先输出节点的值
            if(root.left != null){
                helper(root.left,res);
            }
            if(root.right != null){
                helper(root.right,res);
            }
        }
    }
}

解答2(DFS深度优先遍历)

class Solution {
  public List<Integer> preorderTraversal(TreeNode root) {
    LinkedList<TreeNode> stack = new LinkedList<>();
    LinkedList<Integer> output = new LinkedList<>();
    if (root == null) {
      return output;
    }

    stack.add(root);
    while (!stack.isEmpty()) {//因为开始就会放入根节点的左右字树节点，所以直到最后为空才完成遍历
      TreeNode node = stack.pollLast();//返回栈顶的值并从栈中删除节点
      output.add(node.val);//在***中加入这个值
      if (node.right != null) {
        stack.add(node.right);
      }
      if (node.left != null) {
        stack.add(node.left);
      }
    }
    return output;
  }
}