精华内容
下载资源
问答
  • 主要介绍了Java中二叉树数据结构的实现示例,包括前中后序遍历和求二叉树深度的方法,需要的朋友可以参考下
  • 二叉搜索,顾名思义,就是用来方便搜索的二叉树。... 一、由于是二叉树,采用链式结构。  二、二叉搜索中存储的信息key不能重复。  三、二叉搜索中的左子树全都比根结点小,右子全都...

     二叉搜索树,顾名思义,就是用来方便搜索的二叉树。  

    其定义有以下要点 :   

                                  一、由于是二叉树,采用链式结构。

                                  二、二叉搜索树中存储的信息key不能重复。

                                  三、二叉搜索树中的左子树全都比根结点小,右子树全都比根结点大。

    有了上述定义,我们引入相关的操作,主要有插入,查找,删除。

     

    #pragma once 
    #include <stdio.h>
    #include <assert.h>
    #include <stdlib.h>
    typedef struct STreeNode{
    	int key;
    	struct  STreeNode  * pLeft;
    	struct  STreeNode  * pRight;
    }STreeNode;
    
    // key 不允许重复
    // key 不允许更改
    //结点左边的值都小于结点,结点右边的值都大于结点
    
    // 是否找到 ,1 找到0 没找到
    
    int Find(STreeNode *Node, int key)
    {
    	while (Node!=NULL)
    	{
    		if (Node->key == key){
    			return 1;
    		}
    		if (key<Node->key ){
    			Node = Node->pLeft;
    		}
    		if (key>Node->key){
    			Node = Node->pRight;
    		}
    	}
    	return 0;
    }
    STreeNode * CreadTree(int key){
    	STreeNode *pNode = (STreeNode*)malloc(sizeof(STreeNode));
    	pNode->key = key;
    	pNode->pLeft = pNode->pRight = NULL;
    	return pNode;
    }
    //插入,成功返回1,失败返回0
    int Insert(STreeNode ** pNode, int key)
    {
    	STreeNode * Node = *pNode;
    	STreeNode *parent = NULL;
    	while (Node!=NULL)
    	{
    		if (Node->key == key){
    			return 0;
    		}
    		else if (key>Node->key)
    		{
    			parent = Node;
    			Node = Node->pRight;
    		}
    		else
    		{
    			parent = Node;
    			Node = Node->pLeft;
    		}
    	}
    	//遍历后的parent,若仍为空则是根结点,否则是最后一个叶子结点
    
    	//表示pNode是一颗空树,直接插到根结点处
    	if (parent == NULL){
    		*pNode = CreadTree(key);
    		return 1;
    	}
    	if (key < parent->key){
    		parent->pLeft = CreadTree(key);
    	}
    	if (key>parent->key)
    	{
    		parent->pRight = CreadTree(key);
    	}
    	return 0;
    }
    //递归查找,成功返回1,失败返回-1
    int FindR(STreeNode *Node, int key)
    {
    	if (Node->key==key)
    	{
    		return 1;
    	}
    	else if (key>Node->key)
    	{
    		return FindR(Node->pRight, key);
    	}
    	else
    	{
    		return FindR(Node->pLeft, key);
    	}
    	return 0;
    }
    //递归插入,成功返回1,失败返回-1
    int InsertR(STreeNode *Node, int key)
    {
    	if (Node->key==key){
    		return -1;
    	}
    	if (Node==NULL)
    	{
    		Node = CreadTree(key);
    	}
    	if (key<Node->key)
    	{
    		return InsertR(Node->pLeft, key);
    	}
    	else
    	{
    		return InsertR(Node->pRight, key);
    	}
    }
    //递归删除,成功返回1.失败返回-1
    int RemoveR(STreeNode **pRoot, int key)
    {
    	if (*pRoot == NULL){
    		return -1;
    	}
    	if (key>(*pRoot)->key)
    	{
    		return RemoveR(&(*pRoot)->pRight, key);
    	}
    	if (key<(*pRoot)->key)
    	{
    		return RemoveR(&(*pRoot)->pLeft, key);
    	}
    	//没找到,则pRoot会为空,返回-1,表示失败
    
    	//找到的话,就开始删除
    	if ((*pRoot)->pLeft==NULL)
    	{
    		*pRoot = (*pRoot)->pRight;
    		return 0;
    	}
    	if ((*pRoot)->pRight==NULL)
    	{
    		*pRoot = (*pRoot)->pLeft;
    		return 0;
    	}
    	// 左右孩子都不为空, 替换删除法, 找左子树最大的
    
    	STreeNode *swap = *pRoot;
    	while (swap->pRight)//找到最后一个右子树,不能为空
    	{
    		swap = swap->pRight;
    	}
    	(*pRoot)->key = swap->key;
    	return RemoveR(&((*pRoot)->pLeft), swap->key);
    	return 0;
    }
    void Test()
    {
    	STreeNode *Node = NULL;
    	Insert(&(Node), 3);
    	Insert(&(Node), 5);
    	Insert(&(Node), 9);
    	Insert(&(Node), 3);
    	Insert(&(Node), 4);
    	Insert(&(Node), 1);
    	RemoveR(&Node, 4);
    }

     

    关于二叉搜索树的主要操作如上所示,其中有递归的方式,但若二叉搜索树过大,则会调用大量栈帧,严重影响效率。

    由于代码都为亲力亲为,所思所写。  若有问题,欢迎随时之处。

    展开全文
  • 二叉树前序递归与非递归遍历2.二叉树中序递归与非递归遍历3.二叉树后序递归与非递归遍历4. 1.二叉树前序递归与非递归遍历 递归代码: /** * Definition for a binary tree node. * public class TreeNode { * int...

    1.二叉树前序递归与非递归遍历

    递归代码:

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class BinaryTree {     
        public void preorderTraversal(TreeNode root) {
            if(root != null) {
                System.out.println(root.val); //每次遍历都打印当前节点,然后再去打印左右子树节点,至于左右子树再怎么向下递归打印它的左右子树我们就不关心了
                preorderTraversal(root.left);  //递归调用,遍历左子树,打印左子树的节点
                preorderTraversal(root.right); //递归调用遍历右子树,打印左子树节点
            }
        }
    }
    

    非递归代码:

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class BinaryTree {
        public void preorderTraversal(TreeNode root) {
            if(root == null) {     //空树直接返回,就不用遍历了
                return;
            }
            Stack<TreeNode> s = new Stack<>();
            s.push(root); //根节点入栈
            while(!s.empty()) {    //循环条件:栈不为空,因为栈不为空说明每遍历完
                TreeNode cur = s.pop();    //此时栈顶保存的就是根节点,由于前序遍历先打印根节点,所以先将根节点出栈,
                System.out.println(cur.val);  //打印根节点
                //由于栈先进后出特性,所以想先打印左子树节点,就将右子树节点先入栈
                if(cur.right != null) {  
                    s.push(cur.right);
                } 
                if(cur.left != null) {
                    s.push(cur.left);
                }
            }
        }
    }
    

    2.二叉树中序递归与非递归遍历

    递归代码:

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
     class  BinaryTree {
        public void inorderTraversal(TreeNode root) {
            if(root != null) {
                inorderTraversal(root.left);    //一直递归调用到左子树为空,其实就相当于已经遍历了左子树
                System.out.println(root.val);   //所以按照次序,这里直接打印根节点
                inorderTraversal(root.right);   //然后递归调用,遍历右子树节点
            }
        }
    }
    

    非递归代码:

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class  BinaryTree {
        public void inorderTraversal(TreeNode root) {
            if(root == null) {   //传的根节点为空直接返回,不用遍历了
                return;
            }
            Stack<TreeNode> s = new Stack<>();
            TreeNode cur = root;   //定义一个引用指向头节点,用来遍历二叉树
            while(cur!=null || !s.empty()) {  //循环条件:cur!=null 或者栈不为空时说明还没遍历完
                while(cur != null) {
                    s.push(cur);       //尽可能将节点左子树依次压入栈中
                    cur = cur.left;
                }
                //此时栈顶的元素是最左侧的元素,它的左子树为空,相当于左子树已经遍历了,直接将其出栈并打印
                 cur = s.pop();    
                 System.out.println(cur.val); 
                 cur = cur.right;  //左子树与根都遍历了,此时应该遍历它右节点了
            }
        }
    }
    

    3.二叉树后序递归与非递归遍历

    递归代码:

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class  BinaryTree {
        public void postorderTraversal(TreeNode root) {
            if(root != null) {
                postorderTraversal(root.left);
                postorderTraversal(root.right);
                System.out.println(root.val);
            }
        }
    }
    

    非递归代码:

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class  BinaryTree{
        public void postorderTraversal(TreeNode root) {
            Stack<TreeNode> s = new Stack<>();
            TreeNode cur = root;
            TreeNode lastTime = null;  //用它来记录上一次遍历的节点,后面用来和当前节点比较,看看它是不是当前节点的右子树
            while(cur != null || !s.empty()) {  //cur不为空和栈不为空都说明节点没有遍历完,需要继续循环
                while(cur != null) {
                    s.push(cur);      //尽可能将节点左子树依次压入栈中
                    cur = cur.left;
                }
                 //此时栈顶的元素是最左侧的元素,它的左子树为空,相当于左子树已经遍历了,但是不能直接打印。
                 //第一次当然很清楚是从左子树到达的根,因为它的左子树刚刚遍历完。
                 //但是后面有些有些情况无法判断它是从哪到的根,所以需要判断当前节点的上一个遍历节点是不是其右子树。
                TreeNode temp = s.peek();
                //右子树为空不用遍历可以直接打印,或者刚刚从右子树回来也可以直接打印当前节点
                if(temp.right == null || temp.right == lastTime)  {
                    System.out.println(temp.val);
                    lastTime = temp;   //每次遍历都用lastTime保存,以便下次遍历时与节点右子树比较。
                    s.pop();
                }else {
                    cur = temp.right;   //右子树不为空且每遍历,就需要将右子树压栈遍历
                }
            }
        }
    }
    

    4.二叉树的层序遍历

    题目链接: leetcode102 二叉树的层序遍历

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        public List<List<Integer>> levelOrder(TreeNode root) {
            List<List<Integer>> ret = new ArrayList<>();
            if(root==null) {
                return ret;
            }
            Queue<TreeNode> q = new LinkedList<>();
            q.offer(root);         //先将根节点放入队列中
            while(!q.isEmpty()) {  //队列不为空说明还没遍历完
                int size = q.size(); //size为当前层的元素个数
                List<Integer> level = new ArrayList<>(size);//用level来保存一层元素
                //一次性遍历一层的元素
                for(int i=0;i<size;i++) {
                    TreeNode cur = q.poll();  //将当前层节点依次出队列
                    level.add(cur.val);     //将当前层节点值放进level中
                    //如果节点有左孩子,就将左孩子入队列
                    if(cur.left != null) {
                        q.offer(cur.left);
                    }
                    //如果节点有右孩子,就将右孩子入队列
                    if(cur.right != null) {
                        q.offer(cur.right);
                    }
                }
                ret.add(level);   //每遍历完一层就将当前层结果放入ret中
            }
            return ret;
        }
    }
    

    5.检查两棵树是否相同

    题目链接:leetcode100 两颗相同的树

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        public boolean isSameTree(TreeNode p, TreeNode q) {
            if(p==null && q==null) {
                return true;
            }
            if(p==null || q==null) {
                return false;
            }
            //两棵树都不为空,就比较其节点值
            if(p.val != q.val) {
                return false;
            }
            //根节点比较之后就得继续检查他们的左右子树是否相同了
            return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
        }
    }
    

    6.检查一棵树是否为另一棵树的子树

    题目链接:leetcode572 另一棵树的子树
    题目描述: 给定两个非空二叉树 s 和 t,检验 s 中是否包含和 t 具有相同结构和节点值的子树。s 的一个子树包括 s 的一个节点和这个节点的所有子孙。s 也可以看做它自身的一棵子树。

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        public boolean isSubtree(TreeNode s, TreeNode t) {
            //s为空树时,没有子树
            if(s == null) {
                return false;
            }
            //空树为任何非空树子树
            if(t == null) {
                return true;
            }
            //两者都不为空时则判断其是否为同一棵树
            if(isSameTree(s,t)) {
                return true;
            }
            //递归判断t是否为s的左子树或者右子树
            return isSubtree(s.left,t) || isSubtree(s.right,t);
        }
        public static boolean isSameTree(TreeNode p, TreeNode q) {
            if(p == null && q == null) {
                return true;
            }
            if(p == null || q == null) {
                return false;
            }
            if(p.val != q.val) {
                return false;
            }
            return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
        }
     }
    

    7.求二叉树的最大深度

    题目链接:leetcode104 二叉树最大深度

    题目描述: 给定一个二叉树,找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
     class Solution {
        public int maxDepth(TreeNode root) {
            if(root == null) {
                return 0;
            }
            return Math.max(maxDepth(root.left)+1,maxDepth(root.right)+1);
        }
    }
    

    8.判断一颗二叉树是否是平衡二叉树

    题目链接: leetcode110 平衡二叉树
    题目描述: 给定一个二叉树,判断它是否是高度平衡的二叉树。
    本题中,一棵高度平衡二叉树定义为:一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。

    解法一:自顶向下

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
     class Solution {
        public boolean isBalanced(TreeNode root) {
            if(root == null) {
                return true;
            }
            if(Math.abs(height(root.left)-height(root.right)) > 1) {
                return false;
            }
            return isBalanced(root.left) && isBalanced(root.right);
        }
        private int height(TreeNode root) {
            if(root == null) {
                return 0;
            }
            return Math.max(height(root.left)+1,height(root.right)+1);
        }
    }
    

    解法二:自底向上
    方法一计算 height存在大量冗余。每次调用 height时,要同时计算其子树高度。但是自底向上计算,每个子树的高度只会计算一次。

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
     //递归到底判断左右子树是否平衡,不平衡返回-1,平衡就返回当前节点的高度。
    class Solution {
        public boolean isBalanced(TreeNode root) {
            return height(root) != -1;
        }
        private int height(TreeNode root) {
            if(root == null) {
                return  0;
            }
            int leftHeight = height(root.left);
            //如果其左子树不平衡就不用往下判断了,它肯定不平衡
            if(leftHeight == -1) {
                return -1;
            }
            int rightHeight = height(root.right);
            //如果其右子树不平衡,也直接返回-1
            if(rightHeight == -1) {
                return -1;
            }
            
            return Math.abs(rightHeight-leftHeight) < 2 ? Math.max(leftHeight,rightHeight)+1 : -1;
        }
    }
    

    9.检查一棵二叉树是否镜像对称

    题目链接: leetcode101 对称二叉树
    题目描述: 给定一个二叉树,检查它是否是镜像对称的。

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
     //可以把一棵树拆成两棵树看
    class Solution {
        public boolean isSymmetric(TreeNode root) {
            return isSame(root,root);
        }
        private static boolean isSame(TreeNode a,TreeNode b) {
            if(a == null && b == null) {
                return true;
            }
            if(a == null || b == null) {
                return false;
            }
            if(a.val != b.val) {
                return false;
            }
            return isSame(a.left,b.right) && isSame(a.right,b.left);
        }
    }
    

    10.求一棵二叉树的镜像

    题目链接: leetcode27 二叉树的镜像
    题目描述: 请完成一个函数,输入一个二叉树,该函数输出它的镜像。

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
     //求镜像,即将二叉树每个节点的左右子节点交换即可
    class Solution {
        public TreeNode mirrorTree(TreeNode root) {
            if(root == null) {
                return null;
            }
            Stack<TreeNode> s = new Stack<>();
            s.push(root);
            while(!s.empty()) {
                TreeNode node = s.pop();
                if(node.left != null) {
                    s.push(node.left);
                } 
                if(node.right != null) {
                    s.push(node.right);
                }
                TreeNode temp = node.left;
                node.left = node.right;
                node.right = temp;
            }
            return root;
        }
    }
    

    11.根据一棵树的前序遍历与中序遍历构造二叉树

    题目链接: leetcode105 从前序和中序遍历序列构建二叉树

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
     class Solution {
        public TreeNode buildTree(int[] preorder, int[] inorder) {
            for(int i = 0;i < inorder.length;i++) {
                if(inorder[i] == preorder[0]) {
                    TreeNode root = new TreeNode(preorder[0]);
                    //递归构建二叉树的左子树
                    root.left = buildTree(Arrays.copyOfRange(preorder,1,i+1),Arrays.copyOfRange(inorder,0,i));
                    //递归构建二叉树的右子树
                    root.right = buildTree(Arrays.copyOfRange(preorder,i+1,preorder.length),Arrays.copyOfRange(inorder,i+1,inorder.length));
                    //返回根节点
                    return root;
                }
            }
            return null;
        }
    }
    

    12.根据一棵树的中序遍历与后序遍历构造二叉树

    题目链接: leetcode106 从中序和后序遍历序列构建二叉树

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        public TreeNode buildTree(int[] inorder, int[] postorder) {
            for(int i = 0; i < inorder.length; i++) {
                if(inorder[i] == postorder[postorder.length-1]) {
                    TreeNode root = new TreeNode(postorder[postorder.length-1]);
                    //递归构建二叉树的左子树
                    root.left = buildTree(Arrays.copyOfRange(inorder,0,i),Arrays.copyOfRange(postorder,0,i));
                    //递归构建二叉树的右子树
                    root.right = buildTree(Arrays.copyOfRange(inorder,i+1,inorder.length),Arrays.copyOfRange(postorder,i,postorder.length-1));
                    //返回根节点
                    return root;
                }
            }
            return null;
        }
    }
    

    13.二叉树的最近公共祖先

    题目链接: leetcode236 二叉树的最近公共祖先

    题目描述: 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。百度百科中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。”

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    
    class Solution {
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            if(root == p || root == q) {
                return root;
            }
            Stack<TreeNode> s = new Stack<>();
            TreeNode cur = root.left;
            //设置两个标志位,看看p,q是否都在根节点左侧
            Boolean flag1 = false;
            Boolean flag2 = false;
            while(cur != null || !s.empty()) {
                while(cur != null) {
                    s.push(cur);
                    cur = cur.left;
                }
                cur = s.pop();
                if(cur == p) {
                    flag1 = true;
                }
                if(cur == q) {
                    flag2 = true;
                }
                cur = cur.right;
            }
            //如果p,q都在左子树,就以左子树为根节点递归查找
            //如果p,q都在右子树,就以右子树为根节点递归查找
            //如果p,q在根节点两侧,那么根节点就是其最近公共祖先
            if(flag1 && flag2) {
                return lowestCommonAncestor(root.left,p,q);
            }else if(!flag1 && !flag2){
                return lowestCommonAncestor(root.right,p,q);
            }
            return root;
        }
    }
    
    展开全文
  • 这里又叫做二叉搜索代码://二叉排序(二叉搜索Binary Search Tree)//杨鑫#include #include typedef struct node{int key;struct node *lchild, *rchild;}BSTNode, *BSTree;//插入int InsertBST(BSTree *bst, ...

    这里又叫做二叉搜索树

    代码:

    //二叉排序树(二叉搜索树Binary Search Tree)

    //杨鑫

    #include

    #include

    typedef struct node

    {

    int key;

    struct node *lchild, *rchild;

    }BSTNode, *BSTree;

    //插入

    int InsertBST(BSTree *bst, int k)

    {

    BSTree r, s, pre;

    r = (BSTree)malloc(sizeof(BSTNode));

    r->key = k;

    r->lchild = NULL;

    r->rchild = NULL;

    if(*bst == NULL)

    {

    *bst = r;

    return 1;

    }

    pre = NULL;

    s = *bst;

    while(s)

    {

    if(k == s->key)

    return 0;

    else if(k < s->key)

    {

    pre = s;

    s = s->lchild;

    }

    else

    {

    pre = s;

    s = s->rchild;

    }

    }

    if(k < pre->key)

    pre->lchild = r;

    else

    pre->rchild = r;

    return 1;

    }

    void CreateBST(BSTree *bst)

    {

    int key;

    *bst = NULL;

    scanf("%d", &key);

    while(key != -1)

    {

    InsertBST(bst, key);

    scanf("%d", &key);

    }

    }

    /*

    *打印二叉树:

    *中序遍历

    * */

    void InOrder(BSTree root)

    {

    if(root != NULL)

    {

    InOrder(root->lchild);

    printf(" %d ", root->key);

    InOrder(root->rchild);

    }

    }

    /*

    *搜索

    * */

    BSTree SearchBST(BSTree bst, int key)

    {

    BSTree q;

    q = bst;

    //递归

    while(q)

    {

    if(q->key == key)

    return q;

    if(q->key > key)

    q=q->lchild;

    else

    q=q->rchild;

    }

    return NULL; //查找失败

    }

    int main()

    {

    BSTree T;

    int tag = 1;

    int m, n;

    printf("建立二叉排序树,请输入序列以-1结束:\n");

    CreateBST(&T);

    printf("中序遍历二叉树,序列为:\n");

    InOrder(T);

    printf("\n");

    while(tag != 0)

    {

    printf("请输入你要查找的元素:\n");

    scanf("%d", &n);

    if(SearchBST(T, n) == NULL)

    printf("抱歉查找失败!\n");

    else

    printf("查找成功!查找的数字为%d\n", SearchBST(T,n)->key);

    printf("是否继续查找 是 :请按 1 否则按 0:\n");

    scanf("%d", &tag);

    }

    return 0;

    }

    结果:

    24b8703f0fb23d8e3c08c2a723ace98c.png

    展开全文
  • 包含以下基本操作实现: 前序中序后序遍历的递归非递归写法; 给定序列构建二叉树; 层序遍历; 节点数目; 叶子节点数目; 数的高度;

    给定一个前序序列数组构造一个二叉树

    思路:首先序列中要有给定的非法值,也就是二叉树中对应的空节点;对于构造一个二叉树可以使用递归的思想:先构造当前节点,再构造左子树,再右子树,直到遇到非法值时,将NULL返回,使得上一个节点的一端链接到NULL,图示如下:

    这里写图片描述

        /*  int arr[] = { 1,2,3,'#','#',4,'#','#',5,6 ,'#','#','#' };
        BinaryTree<int> tree1(arr, sizeof(arr) / sizeof(arr[0]), '#');*/
    
        BinaryTree(const T* arr, size_t sz, const T& invalid)
        {
            size_t index = 0;
            _root = _CreatTree(arr, sz, index, invalid);
        }
    
        Node* _CreatTree(const T* arr, size_t sz, size_t& index, const T& invalid)
        {
            Node* node = NULL;
            if (arr[index] != invalid)
            {
                node = new Node(arr[index]);
                node->_left = _CreatTree(arr, sz, ++index, invalid);
                node->_right = _CreatTree(arr, sz, ++index, invalid);
            }
            return node;
        }

    前、中、后序遍历递归写法:

    前序遍历:先遍历根节点,再遍历左子树,再遍历右子树;所以最先输出根节点;
    中序遍历:先遍历根节点左子树,再遍历根节点,再遍历右子树;
    后序遍历:先遍历左子树,再右子树,最后根节点。
    //前序
        void PrevOrederR()
        {
            _PrevOrederR(_root);
            cout<<endl;
        }
    
        void _PrevOrderR(Node* node)
        {
            if (node == NULL)
                return;
    
            cout << node->_data << " ";
            _PrevOrderR(node->_left);
            _PrevOrderR(node->_right);
        }
    
    //中序
        void MidOrderR()
        {
            _MidOrderR(_root);
            cout<<endl;
        }
    
        void _MidOrderR(Node* node)
        {
            if (node == NULL)
                return;
    
            _MidOrder(node->_left);
            cout << node->_data << " ";
            _MidOrder(node->_right);
        }
    
    //后序
        void BackOrderR()
        {
            _BackOrderR(_root);
            cout<<endl;
        }
    
    
        void _BackOrderR(Node* node)
        {
            if (node == NULL)
                return;
    
            _BackOrderR(node->_left);
            _BackOrderR(node->_right);
            cout << node->_data << " ";
        }
    输出结果:拿一开始构造的二叉树为例

    这里写图片描述


    前、中、后序遍历非递归写法:

    思路:将递归转递归无非就是转为循环或者使用栈来模拟递归的过程;前序和后序比较简单,在后序遍历时需要注意加判断当前节点的右子树是否已经遍历过,只有当左右子树都遍历过后,才可输出当前根节点。
        //遍历非递归
        void PrevOrderNR()
        {
            stack<Node*> s;
            Node* cur = _root;
            while (cur || !s.empty())
            {
                while (cur != NULL)
                {
                    s.push(cur);
                    cout << cur->_data << " ";
                    cur = cur->_left;
                }
                //到最左根节点,该回溯了
                if (!s.empty())
                {
                    cur = s.top();
                    s.pop();
                    cur = cur->_right;
                }
            }
            cout << endl;
        }
    
        void MidOrderNR()
        {
            stack<Node*> s;
            Node* cur = _root;
    
            while (cur != NULL || !s.empty())
            {
                while (cur != NULL)
                {
                    s.push(cur);
                    cur = cur->_left;
                }
    
                //到最左节点
                if (!s.empty())
                {
                    cur = s.top();
                    cout << cur->_data << " ";
                    s.pop();
                    cur = cur->_right;
                }
            }
            cout << endl;
        }
    
        void BackOrderNR()
        {
            stack<Node*> s;
            Node* cur = _root;
            Node* prev = NULL;
    
            while (cur != NULL || !s.empty())
            {
                while (cur != NULL)
                {
                    s.push(cur);
                    cur = cur->_left;
                }
    
                Node* top = s.top();
    
                if (top->_right == NULL || top->_right == prev)
                {
                    cout << top->_data << " ";
                    s.pop();
                }
                else
                {   //说明此时右子树还没判断,不可直接pop
                    cur = top->_right;
                }
                prev = top;
            }
            cout << endl;
        }
    输出结果:

    这里写图片描述


    层序遍历:

    思路:利用队列先进先出的特性完成
        void LevelOrder()
        {
            queue<Node*> q;
            Node* node = _root;
            if (node != NULL)
                q.push(node);
    
            while (!q.empty())
            {
                Node* cur = q.front();
                cout << cur->_data << " ";
                q.pop();
                if (cur->_left != NULL)
                    q.push(cur -> _left);
                if (cur->_right != NULL)
                    q.push(cur->_right);
            }
            cout << endl;
        }
    
    //输出结果:1 2 5 3 4 6

    求节点数目:

    思路一:利用子问题的思想:左子树节点个数加右子树节点个数加自己的一个,如果当前节点为NULL,则返回0;
    
        int SizeByChildQue()
        {
            return _SizeByChildQue(_root);
        }
    
        int _SizeByChildQue(Node* node)
        {
            if (node == NULL)
                return 0;
            return _SizeByChildQue(node->_left) + _SizeByChildQue(node->_right) + 1;
        }

    思路二:利用遍历的思想:给定一个参数,遍历所有节点,只要不为NULL,节点个数加1
        int SizeByTrav()
        {
            size_t size = 0;
            _SizeByTrav(_root, size);
            return size;
        }
    
        void _SizeByTrav(Node* node, size_t& size)
        {
            if (node == NULL)
                return;
    
            size++;
            _SizeByTrav(node->_left, size);
            _SizeByTrav(node->_right,size);
        }

    求叶子节点数目:如同求节点数目,只不过在统计数目时需要判断是否左右都为NULL,所以也可分为两种写法:

    思路一:子问题:左子树叶子节点个数加右子树叶子节点个数,同时还要注意如果只有一个节点。
        int LeafSizeByChildQue()
        {
            return _LeafSizeByChildQue(_root);
        }
    
        int _LeafSizeByChildQue(Node* node)
        {
            if (node == NULL)
                return 0;
    
            //进行判断,只有当左右都为空时才算做一个叶子节点
            if (node->_left == NULL && node->_right == NULL)
            {
                return 1;
            }
            return _LeafSizeByChildQue(node->_left) + _LeafSizeByChildQue(node->_right);
        }

    思路二:遍历思想,只有当当前节点为叶子节点时,才对计数+1;切记size要传引用,否则回到第一个栈帧时size仍为0!
        int LeafSizeByTrav()
        {
            size_t size = 0;
            _LeafSizeByTrav(_root, size);
            return size;
        }
    
        void _LeafSizeByTrav(Node* node, size_t& size)
        {
            if (node == NULL)
                return;
    
            if (node->_left == NULL && node->_right == NULL)
                size++;
    
            _LeafSizeByTrav(node->_left, size);
            _LeafSizeByTrav(node->_right, size);
        }

    二叉树的高度:

    思路:需要注意的是,高度是最长的那条路;划分为子问题为:该节点的高度等于左子树和右子树高度中大的那个再加上1。
        size_t Height()
        {
            return _Height(_root);
        }
    
        size_t _Height(Node* node)
        {
            if (node == NULL)
                return 0;
    
            size_t lHeight = _Height(node->_left);
            size_t rHeight = _Height(node->_right);
            //注意返回时要加上当前的高度1
            return lHeight > rHeight ? lHeight + 1 : rHeight + 1;
        }

    完整代码可查看https://github.com/SssUuuu/Data_structure/blob/master/BinaryTree.h

    展开全文
  • 栈顶元素恰好是叶子节点,也是该节点的根节点,此时的操作不应该是将其出栈(因为还没打印),而是要继续遍历其右子,当右子树遍历完成后,该节点又再次出现在栈顶, 此刻表明该节点的左子树打印完了,右子也打印完了....
  • 摘要:今天用C撸了一遍数据中二叉树常见操作的实现,将实现过程中感觉有意思的几个功能实现记录下来方便以后复习~先序遍历递归实现
  • 前言 三大基本遍历 前序遍历 递归版本的前序遍历 非递归版本的前序遍历 判断前序遍历数组是否...遍历重建二叉搜索 前序遍历和中序遍历重建二叉树 前序结果重建二叉搜索 后序结果重建二叉搜索 深度...
  • 二叉树的层序遍历(js)

    2021-08-06 12:47:51
    除了先序、中序、后序三种遍历...层序遍历采用配合队列的方式来实现,其原因是它是从左往右遍历的,所以队列这种数据结构非常适合它。 var levelOrder = function(root) { if (!root) { return []; } var res = [];
  • 数据结构之二叉搜索

    千次阅读 2018-08-26 00:12:51
    数据结构中,包括很多的结构,像二叉树、二叉搜索、线段、字典、红黑等。本小节介绍的是二叉树和二叉搜索,其余的结构,会在后面的文章中再进行介绍。 在介绍二叉树之前,我们先准备些预备...
  • 数据结构』二叉搜索

    千次阅读 2019-07-11 19:02:14
    什么是二叉搜索?二叉搜索的基本操作。二叉搜索的查找、插入、删除等。二叉搜索的性能分析。二叉搜索的模拟实现(C++和Java)。模拟实现中遇到的问题。
  • 初学数据结构本人感受就是,对于栈的创建和的创建(类)相当于一个模板,以后如果用到的话,基本上就是再这个上面做根据自己需要扩充和使用,所以对于非递归后序遍历和非递归中序遍历都可接着使用。 如果有错误,...
  • 本总结主要是以“尚硅谷Java算法教程”的学习教程为主,加上一些个人的理解 为何需要 1、数组存储方式的分析 ...缺点:在进行检索时,效率仍然较低,比如(检索某个值,需要从头节点开始遍历) 3、 存储
  • Leetcode中二叉树中的搜索相关题目解析以及java实现(第二篇) 接上一篇,继续看二叉树中的搜索的相关问题和java的实现。 [236] Lowest Common Ancestor of a Binary Tree [156] Binary Tree Upside Down: [617] ...
  • 二叉树指的是每个节点最多只能有两个子树的有序。通常左边的子树被称为“左子树”(left subtree),右边的子树被称为右子。 二叉树的每个节点最多只有2棵子树,二叉树的子树次序不能颠倒。 二、顺序存储...
  • 定义最多有两棵子树的有序,称为二叉树。二叉树是一种特殊的。递归定义:二叉树是n(n>=0)个有限结点构成的集合。N=0称为空二叉树;n>0的二叉树由一个根结点和两互不相交的,分别称为左子树和右子的...
  • = None: print_mid(root.rchild) # 使用层序遍历打印二叉树的内容 from collections import deque def print_divide(root): if root == None: return 0 queue = deque() queue.append(root) while len(queue) > 0: p...
  • 二叉搜索「中序遍历」得到的值构成的序列一定是升序的 中序遍历时,判断当前节点是否大于中序遍历的前一个节点,如果大于,说明满足 BST,继续遍历;否则直接返回 false。 class Solution { long pre = Long.MIN_...
  • 本节将介绍可能在二叉搜索上执行的一些基本操作。接下来要讲解的是一个简单的类,该类实现了用一个二叉树来存储整数值。创建二叉搜索现在使用 IntBinaryTree 类来演示基本的二叉树操作。在本示例中,二叉树结点...
  • 是一种常见的数据结构,由一系列节点和节点之间的关系组成。的搜索和遍历是笔试和面试经常考的。最基本的——二叉树,顾名思义,父节点最多只有两个子节点。我们先创建一个节点类: pub...

空空如也

空空如也

1 2 3 4 5 ... 16
收藏数 319
精华内容 127
关键字:

数据结构中二叉树遍历

数据结构 订阅