精华内容
下载资源
问答
  • python编写二叉树算法

    2018-11-12 21:11:42
         ... 二叉树的遍历是树的一种重要的运算。所谓遍历是指对树中所有结点的信息的访问,即依次对树中每个...以下使用深度优先和广度优先遍历二叉树算法。 广度优先遍历...
           二叉树的遍历是树的一种重要的运算。所谓遍历是指对树中所有结点的信息的访问,即依次对树中每个结点访问一次且仅访问一次,我们把这种对所有节点的访问称为遍历(traversal)。那么树的两种重要的遍历模式是深度优先遍历和广度优先遍历,深度优先一般用递归,广度优先一般用队列。以下使用深度优先和广度优先遍历二叉树算法。

    广度优先遍历:

    
    class Node(object):
        """二叉树的节点类型"""
    
        def __init__(self, item):
            self.item = item  # 存储节点的真是值
            self.lchild = None  # 指向左子树的指针
            self.rchild = None  # 指向➡右子树的指针
    
    
    class BinaryTree(object):
        """二叉树"""
    
        def __init__(self, node=None):
            self.root = node
    
        def add(self, item):
            """为树添加节点(广度优先遍历的思想)"""
            if self.root is None:
                self.root = Node(item)  # 空树
            else:
                queue = []  # 初始化队列
                queue.append(self.root)  # 将根节点入队列
                while len(queue) > 0:
                    node = queue.pop(0)  # 弹出节点
                    # 弹出判断节点是否有左右子树
                    if not node.lchild:
                        # 没有左子树,将新节点添加上去即可
                        node.lchild = Node(item)
                        # 注意:树每次只添加一个节点,添加完毕退出循环
                        return
                    else:
                        # 有左子树,继续将左子树添加到队列中
                        queue.append(node.lchild)
    
                    if not node.rchild:
                        # 没有右子树,将新节点添加上去即可
                        node.rchild = Node(item)
                        return
                    else:
                        # 有右子树,继续将右子树添加到队列中
                        queue.append(node.rchild)
    
        def breath_travel(self):
            """广度优先遍历"""
            if self.root is Node:
                return
            queue = []  # 树不为空,初始化队列
            queue.append(self.root)
            while len(queue) > 0:
                node = queue.pop(0)  # 弹出元素
                print(node.item, end=" ")
    
                # 判断是否有左右子树
                if node.lchild:
                    # 左子树有值添加到队列继续遍历
                    queue.append(node.lchild)
                if node.rchild:
                    # 右子树有值添加到队列继续遍历
                    queue.append(node.rchild)
    
    
    if __name__ == '__main__':
        tree = BinaryTree()
        for i in range(10):
            tree.add(i)
        tree.breath_travel()
        print(" ")
        
    输出:0 1 2 3 4 5 6 7 8 9 
    

    深度优先遍历:

    
    class Node(object):
        """二叉树的节点类型"""
    
        def __init__(self, item):
            self.item = item  # 存储节点的真是值
            self.lchild = None  # 指向左子树的指针
            self.rchild = None  # 指向➡右子树的指针
    
    
    class BinaryTree(object):
        """二叉树"""
    
        def __init__(self, node=None):
            self.root = node
    
        def add(self, item):
            """为树添加节点(广度优先遍历的思想)"""
            if self.root is None:
                self.root = Node(item)  # 空树
            else:
                queue = []  # 初始化队列
                queue.append(self.root)  # 将根节点入队列
                while len(queue) > 0:
                    node = queue.pop(0)  # 弹出节点
                    # 弹出判断节点是否有左右子树
                    if not node.lchild:
                        # 没有左子树,将新节点添加上去即可
                        node.lchild = Node(item)
                        # 注意:树每次只添加一个节点,添加完毕退出循环
                        return
                    else:
                        # 有左子树,继续将左子树添加到队列中
                        queue.append(node.lchild)
    
                    if not node.rchild:
                        # 没有右子树,将新节点添加上去即可
                        node.rchild = Node(item)
                        return
                    else:
                        # 有右子树,继续将右子树添加到队列中
                        queue.append(node.rchild)
    
    
        def preorder(self, root):
            """
            先序遍历: 根节点 左子树 右子树
            :param root:
            结果:0 1 3 7 8 4 9 2 5 6
            """
            if root is None:
                return
            print(root.item, end=" ")  # 1.根节点 0 1 3 7 8 4 9 2 5 6
            self.preorder(root.lchild)  # 2.递归调用左子树 1 3 7 9 5
            self.preorder(root.rchild)  # 3.递归调用右子树 8 4 2 6
    
        def inorder(self, root):
            """
            中序遍历:左子树 根节点 右子树
            :param root:
            结果:7 3 8 1 9 4 0 5 2 6
            """
            if root is None:
                return
            self.inorder(root.lchild)  # 1.递归调用左子树
            print(root.item, end=" ")  # 2.根节点
            self.inorder(root.rchild)  # 3.递归调用右子树
    
        def postorder(self, root):
            """
            后序遍历:左子树  右子树 根
            :param root:
            结果:7 8 3 9 4 1 5 6 2 0
            """
            if root is None:
                return
            self.postorder(root.lchild)  # 1.递归调用左子树
            self.postorder(root.rchild)  # 2.递归调用右子树
            print(root.item, end=" ")  # 3.根节点
    
    
    if __name__ == '__main__':
        tree = BinaryTree()
        for i in range(10):
            tree.add(i)
        tree.preorder(tree.root)
        print(" ")
        tree.inorder(tree.root)
        print(" ")
        tree.postorder(tree.root)
    
    
    展开全文
  • 编写创建二叉树算法

    千次阅读 2016-02-02 18:40:41
    ①、编写创建二叉树算法; ②、编写查找节点的算法; ③、编写找孩子节点的算法; ④、编写二叉树高度的算法; ⑤、编写输出二叉树算法; ⑥、编写先序遍历递归算法; ⑦、编写主函数。 代码如下: #...

    ①、编写创建二叉树的算法;

    ②、编写查找节点的算法;

    ③、编写找孩子节点的算法;

    ④、编写求二叉树高度的算法;

    ⑤、编写输出二叉树的算法;

    ⑥、编写先序遍历递归算法;

    ⑦、编写主函数。

    代码如下:

    #include<stdio.h>
    #include<stdlib.h>
    #include<malloc.h>
    #include<iostream>
    #define MaxSize 50
    //①:
    void CreateBTNode(BTNode * &b,char *str){  
       BTNode *St[MaxSize], *p=NULL;
       int top=-1,k,j=0;  
       char ch;
       b=NULL;				//建立的二叉树初始时为空
       ch=str[j];
       while (ch!='\0')  	      //str未扫描完时循环
       {  
    	   switch(ch){
    			case '(':
    				top++;  St[top]=p;  k=1;  break;//为左孩子节点
    			case ')':top--;break;
    			case ',':k=2; break;  
             				//为孩子节点右节点
    			default:
    				p=(BTNode *)malloc(sizeof(BTNode));
    				p->data=ch;p->lchild=p->rchild=NULL;
    			if (b==NULL)    	//p为二叉树的根节点
    				b=p;
    			else{    		//已建立二叉树根节点
    				switch(k) 
    				{
    	    			case 1:St[top]->lchild=p;break;
    					case 2:St[top]->rchild=p;break;
    				}
           }
         }
         j++;ch=str[j];
       }
    }
    //②:
    BTNode *FindNode(BTNode *b,char x) 
    {  BTNode *p;
       if (b==NULL) return NULL;
       else if (b->data==x) return b;
       else
       {   p=FindNode(b->lchild,x);
    	 if (p!=NULL) return p;
    	 else return FindNode(b->rchild,x);
       }
    }
    
    //③:
    BTNode *LchildNode(BTNode *p){
          return p->lchild;
     }
      BTNode *RchildNode(BTNode *p){
          return p->rchild;
    }
    //④:
    int BTNodeDepth(BTNode *b) 
    {  int lchilddep,rchilddep;
       if (b==NULL) 
    	   return(0); //空树的高度为0
       else{
    	   lchilddep=BTNodeDepth(b->lchild); //求左子树的高度为lchilddep
      		rchilddep=BTNodeDepth(b->rchild); //求右子树的高度为rchilddep
    		return (lchilddep>rchilddep)?(lchilddep+1):(rchilddep+1);
       }
    }
    
    //⑤:
    void DispBTNode(BTNode *b) 
    {  if (b!=NULL)
       {  printf("%c",b->data);
    	 if (b->lchild!=NULL || b->rchild!=NULL)
    	 {  printf("(");
    	    DispBTNode(b->lchild); //递归处理左子树
    	    if (b->rchild!=NULL) printf(",");
    	    DispBTNode(b->rchild); //递归处理右子树
    	    printf(")");
    	 }
       }
    }
    //⑥:
    void PreOrder(BTNode *b){  
    	if (b!=NULL){
    		printf("%c ",b->data); //访问根节点
    	    PreOrder(b->lchild);
    	    PreOrder(b->rchild);
           }
      }
    //⑦:
    void main(){
    	char str[] = "A(B(D(,G)),C(E,F))";
    	BTNode *b;
    	CreateBTNode(b,str);
    
    	printf("输出二叉树:\n");
    	printf("\n");
    	DispBTNode(b);
    	printf("\n");
    
    	printf("二叉树的高度是:\n");
    	int h = BTNodeDepth(b);
    	printf("\n");
    	printf("%d",h);
    	printf("\n");
    
    	printf("二叉树的左孩子:\n");
    	BTNode *lchild  = LchildNode(b);
    	printf("\n");
    	DispBTNode(lchild);
    	printf("\n");
    
    	printf("二叉树的右孩子:\n");
    	BTNode *rchild = RchildNode(b);
    	printf("\n");
    	DispBTNode(rchild);
    	printf("\n");
    	
    	printf("查找“D”的二叉树节点:\n");
    	BTNode *child = FindNode(b,'D');
    	printf("\n");
    	DispBTNode(child);
    	printf("\n");


    展开全文
  • CPU:T6670 2.20GHZ 内存:2G 系统:WIN7 用VB调用VC编写二叉树排序DLL排序,10万个数排序只需要0.3秒,100万个数排序只需要5.3秒左右
  • 二叉树算法

    2017-03-29 17:05:35
    要求将队列处理成循环队列,入队和出队操作单独编写算法,并在异常情况下(如队满)时打印出错。Status Link(BiTree b, BiTree &head, BiTree &tail) { // 二叉树b, head和tail分别为生成的单链表的

    试从键盘输入一整数序列a1,a2,…,an,请编程实现:当ai>0时,ai进队,当ai<0时,将队头元素出队,当ai=0时,表示输入结束。要求将队列处理成循环队列,入队和出队操作单独编写算法,并在异常情况下(如队满)时打印出错。

    Status Link(BiTree b, BiTree &head, BiTree &tail)   { 
        // 二叉树b, head和tail分别为生成的单链表的头尾指针,采用先序遍历
        if (b)  {  // 二叉树非空
            if ((b->lchild == NULL) && (b->rchild == NULL)) {//叶子结点
                if (head == NULL)   { //单链表为空,即遇到第一个叶子结点
                    head = b;     // 头尾指针均指向该结点
                  tail = b;
                }
               else {
                    tail->rchild = b;  //仅将尾指针指向的结点链接到该结点
                  tail = b;     // 同时调整尾指针
                }
            }
           if (b->lchild) Link(b->lchild, head, tail);
           if (b->rchild) Link(b->rchild, head, tail);
        } // end of if
    } // end of function
    

    假设二叉树采用二叉链表的存储结构存储,请编写一个算法,求一个二叉树中的结点的最大值。

    答:当该二叉树只有一个结点时,结点的最大值即为该结点的数据域中的值,f(T) = T->data; 否则,f(T) = max{f(T->lchild), f(T->rchild), T->data}。对应的算法如下:
    
    ElemType MaxNode(BiTree T)  { //求二叉树T的结点最大值
        if (!T) return ERROR;   //二叉树为空
    else {  //二叉树非空
           max = T->data;  //将最大值max设为当前根结点的数据域中的数值
        if ((T->lchild == NULL) && (T->rchild == NULL))/* 二叉树只有一个结点 */
            return T->data;
       else {
            if (T->lchild != NULL)
              max_l = MaxNode(T->lchild);
          if (max_l > max) max = max_l;
          if (T->rchild != NULL)
              max_r = MaxNode(T->rchild);
          if (max_r > max) max = max_r;
          return max;
        } // end of else
    } // end of else
    } //end of function
    
    
    

    假设二叉树采用链式存储结构存储,请设计一个算法,求二叉树b的宽度(具有结点数最多的那一层上的结点总数)。

    答:采用队列支持的层次遍历,在对二叉树每层的结点的遍历过程中统计该层结点的总数,并将其记录在数组number中,其中number[i]对应第i层的结点数目,最后计算出number中的最大值。对应的算法如下:
    
    Status BTWidth(BiTree b)    { //求二叉树b的宽度
        InitQueue(Q);   // 初始化队列
       EnQueue(Q, b);  // 根结点入队
       De_counter = 1;  /* De_counter记录当前层的结点数目,第一层结点数目为1 */
       layer = 1;  //layer 指明当前层次,初始值为1
       number[layer++] = De_counter; /*数组number存放每层的结点数,0号位置不用 */
       while ( !QueueEmpty(Q))  {  //层次遍历
    En_counter = 0;  
            for (i = 0; i < De_counter; i ++)   {  /*将当前层的结点出队,并同时将其孩子结点入队,这个过程中用En_counter记录下层的结点总数 */
                DeQueue(Q, p) ; 
            if (p->lchild != NULL) {EnQueue(Q, p->lchild) ; En_counter++;}
            if (p->rchild != NULL) {EnQueue(Q, p->rchild) ; En_counter++;}
    } // end of for
    number[layer++] = En_counter;
    De_counter = En_counter;
        }  // end of while
    //最后求出数组number中的最大值
    max = number[1];
    for (i = 1; i < layer; i ++)    
        if (number[i] > max)
            max = number[i];
    
    return max;  // 返回二叉树b的宽度
    }
    
    
    展开全文
  • 二叉树算法题汇总

    千次阅读 2019-05-19 12:39:59
    基础算法二叉树中的节点个数 求二叉树的深度(高度) 求二叉树第k层的节点个数 求二叉树中叶子节点的个数 判断两棵二叉树是否相同的树 判断二叉树是不是平衡二叉树二叉树的镜像 判断两个二叉树是否...

    目录

    二叉树的遍历

    前序遍历

    中序遍历

    后序遍历

    层次遍历

    基础算法

    求二叉树中的节点个数

    求二叉树的深度(高度)

    求二叉树第k层的节点个数

    求二叉树中叶子节点的个数

    判断两棵二叉树是否相同的树

    判断二叉树是不是平衡二叉树

    求二叉树的镜像

    判断两个二叉树是否互相镜像

    判断是否为二分查找树BST


    本文的实例代码基于JAVA编写

    首先给出节点的数据结构

    public class TreeNode {
    	int val;
    	TreeNode left;
    	TreeNode right;
    
    	TreeNode(int x) {
    		val = x;
    	}
    }

    二叉树的遍历

    前序遍历

    题目参考LeetCode(144)

    递归解法

    • 如果二叉树为空,空操作
    • 如果二叉树不为空,访问根节点,前序遍历左子树,前序遍历右子树
    List<Integer> list = new ArrayList<Integer>();	
    public List<Integer> preorderTraversal(TreeNode root) {
    	if (root != null) {
    		list.add(root.val);
    		if (root.left != null) {
    			preorderTraversal(root.left);
    		}
    		if (root.right != null) {
    			preorderTraversal(root.right);
    		}
    
    	}
    	return list;
    }

    非递归

    List<Integer> list = new ArrayList<Integer>();	
    public List<Integer> preorderTraversal(TreeNode root) {
    	Stack<TreeNode> stack = new Stack<>();
    	while (root != null || !stack.isEmpty()) {
    		while (root != null) {
    			list.add(root.val);
    			stack.add(root);
    			root = root.left;
    		}
    		if (!stack.isEmpty()) {
    			TreeNode node = stack.pop();
    			root = node.right;
    		}
    	}
    	return list;
    }

    中序遍历

    题目参考LeetCode(94)

    递归解法

    • 如果二叉树为空,空操作
    • 如果二叉树不为空,中序遍历左子树,访问根节点,中序遍历右子树
    List<Integer> list = new ArrayList<Integer>();	
    public List<Integer> inorderTraversal(TreeNode root) {
    	if (root != null) {
    		if (root.left != null) {
    			inorderTraversal(root.left);
    		}
    		list.add(root.val);
    		if (root.right != null) {
    			inorderTraversal(root.right);
    		}
    	}
    	return list;
    }

    非递归解法:用栈先把根节点的所有左孩子都添加到栈内,然后输出栈顶元素,再处理栈顶元素的右子树。

    List<Integer> list = new ArrayList<Integer>();	
    public List<Integer> inorderTraversal(TreeNode root) {
    	Stack<TreeNode> stack = new Stack<>();
    	while (root != null || !stack.isEmpty()) {
    		while (root != null) {
    			stack.add(root);
    			root = root.left;
    		}
    		if (!stack.isEmpty()) {
    			root = stack.pop();
    			list.add(root.val);
    			root = root.right;
    		}
    	}
    	return list;
    }

    后序遍历

    题目参考LeetCode(145)

    递归解法

    • 如果二叉树为空,空操作
    • 如果二叉树不为空,后序遍历左子树,后序遍历右子树,访问根节点
    List<Integer> list = new ArrayList<Integer>();
    public List<Integer> postorderTraversal(TreeNode root) {
    	if (root != null) {
    		if (root.left != null) {
    			postorderTraversal(root.left);
    		}
    		if (root.right != null) {
    			postorderTraversal(root.right);
    		}
    		list.add(root.val);
    	}
    	return list;
    }

    非递归解法:双栈法。

    List<Integer> list = new ArrayList<Integer>();	
    public List<Integer> postorderTraversal(TreeNode root) {
    	Stack<TreeNode> stack1 = new Stack<>();
    	Stack<TreeNode> stack2 = new Stack<>();
    	if (root != null) {
    		stack1.add(root);
    	}
    	while (!stack1.isEmpty()) {
    		TreeNode node = stack1.pop();
    		stack2.add(node);
    		if (node.left != null) {
    			stack1.add(node.left);
    		}
    		if (node.right != null) {
    			stack1.add(node.right);
    		}
    	}
    	while (!stack2.isEmpty()) {
    		list.add(stack2.pop().val);
    	}
    	return list;
    }

    层次遍历

    思路:分层遍历二叉树(按层次从上到下,从左到右)迭代,相当于广度优先搜索,使用队列实现。队列初始化,将根节点压入队列。当队列不为空,进行如下操作:弹出一个节点,访问,若左子节点或右子节点不为空,将其压入队列。

    public static void levelTraversal(TreeNode root){
        if(root == null) {
            return;
        }
        Queue<TreeNode> queue = new LinkedList<>(); // 对列保存树节点
        queue.add(root);
        while (!queue.isEmpty()) {
            TreeNode temp = queue.poll();
            System.out.print(temp.val + "->");
            if (temp.left != null) { // 添加左右子节点到对列
                queue.add(temp.left);
            }
            if (temp.right != null) {
                queue.add(temp.right);
            }
        }
    }

    变形:按层保存,题目参考LeetCode(102)

    public List<List<Integer>> levelOrder(TreeNode root) {
    	List<List<Integer>> list = new ArrayList<List<Integer>>();
    	Queue<TreeNode> queue = new LinkedList<>();
    	if (root != null) {
    		queue.add(root);
    	}
    	while (!queue.isEmpty()) {
    		int size = queue.size();
    		List<Integer> l = new ArrayList<>();
    		while (size > 0) {
    			TreeNode node = queue.poll();
    			if (node.left != null) {
    				queue.add(node.left);
    				l.add(node.left.val);
    			}
    			if (node.right != null) {
    				queue.add(node.right);
    				l.add(node.right.val);
    			}
    			size--;
    		}
    		list.add(l);
    	}
    	return list;
    }

    基础算法

    求二叉树中的节点个数

    递归解法: O(n)O(n)

    • 如果二叉树为空,节点个数为0
    • 如果二叉树不为空,二叉树节点个数 = 左子树节点个数 + 右子树节点个数 + 1
    public static int getNodeNumRec(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return getNodeNumRec(root.left) + getNodeNumRec(root.right) + 1;
    }

    非递归解法:O(n)O(n)。基本思想同LevelOrderTraversal。即用一个Queue,在Java里面可以用LinkedList来模拟

    public static int getNodeNum(TreeNode root) {
        if (root == null) {
            return 0;
        }
        Queue<TreeNode> queue =  new LinkedList<>(); // 用队列保存树节点,先进先出
        queue.add(root);
        int count = 1; // 节点数量
        while (!queue.isEmpty()) {
            TreeNode temp = queue.poll(); // 每次从对列中删除节点,并返回该节点信息
            if (temp.left != null) { // 添加左子孩子到对列
                queue.add(temp.left);
                count++;
            }
            if (temp.right != null) { // 添加右子孩子到对列
                queue.add(temp.right);
                count++;
            }
        }
        return count;
    }

    求二叉树的深度(高度)

    题目参考LeetCode(104)

    递归解法: O(n)O(n)

    • 如果二叉树为空,二叉树的深度为0
    • 如果二叉树不为空,二叉树的深度 = max(左子树深度, 右子树深度) + 1
    public int maxDepth(TreeNode root) {
    	int d = 0;
    	if (root == null) {
    		return 0;
    	}
    	d = Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    	return d;
    }

    非递归解法:O(n)O(n)。基本思想同LevelOrderTraversal。即用一个Queue,在Java里面可以用LinkedList来模拟。

    public static int getDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int currentLevelCount = 1; // 当前层的节点数量
        int nextLevelCount = 0; // 下一层节点数量
        int depth = 0; // 树的深度
    
        Queue<TreeNode> queue = new LinkedList<>(); // 对列保存树节点
        queue.add(root);
        while (!queue.isEmpty()) {
            TreeNode temp = queue.remove(); // 移除节点
            currentLevelCount--; // 当前层节点数减1
            if (temp.left != null) { // 添加左节点并更新下一层节点个数
                queue.add(temp.left);
                nextLevelCount++;
            }
            if (temp.right != null) { // 添加右节点并更新下一层节点个数
                queue.add(temp.right);
                nextLevelCount++;
            }
            if (currentLevelCount == 0) { // 如果是该层的最后一个节点,树的深度加1
                depth++;
                currentLevelCount = nextLevelCount; // 更新当前层节点数量并且重置下一层节点数量
                nextLevelCount = 0;
            }
        }
        return depth;
    }

    求二叉树第k层的节点个数

    递归解法: O(n)O(n)
    思路:求以root为根的k层节点数目,等价于求以root左孩子为根的k-1层(因为少了root)节点数目 加上以root右孩子为根的k-1层(因为 少了root)节点数目。即:

    如果二叉树为空或者k<1,返回0
    如果二叉树不为空并且k==1,返回1
    如果二叉树不为空且k>1,返回root左子树中k-1层的节点个数与root右子树k-1层节点个数之和

    public static int getNodeNumKthLevelRec(TreeNode root, int k) {
        if (root == null || k < 1) {
            return 0;
        }
        if (k == 1) {
            return 1;
        }
        return getNodeNumKthLevelRec(root.left, k - 1) + getNodeNumKthLevelRec(root.right, k - 1);
    }

    求二叉树中叶子节点的个数

    递归解法

    • 如果二叉树为空,返回0
    • 如果二叉树是叶子节点,返回1
    • 如果二叉树不是叶子节点,二叉树的叶子节点数 = 左子树叶子节点数 + 右子树叶子节点数
    public static int getNodeNumLeafRec(TreeNode root) {
        if (root == null) {
            return 0;
        }
        if (root.left == null && root.right == null) {
            return 1;
        }
        return getNodeNumLeafRec(root.left) + getNodeNumLeafRec(root.right);
    }

    非递归解法:基于层次遍历进行求解,利用Queue进行。

    public static int getNodeNumLeaf(TreeNode root){
        if (root == null) {
            return 0;
        }
        int leaf = 0; // 叶子节点个数
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            TreeNode temp = queue.poll();
            if (temp.left == null && temp.right == null) { // 叶子节点
                leaf++;
            }
            if (temp.left != null) {
                queue.add(temp.left);
            }
            if (temp.right != null) {
                queue.add(temp.right);
            }
        }
        return leaf;
    }

    判断两棵二叉树是否相同的树

    递归解法

    • 如果两棵二叉树都为空,返回真
    • 如果两棵二叉树一棵为空,另外一棵不为空,返回假
    • 如果两棵二叉树都不为空,如果对应的左子树和右子树都同构返回真,其他返回假
    public static boolean isSameRec(TreeNode r1, TreeNode r2) {
        if (r1 == null && r2 == null) { // 都是空
            return true;
        } else if (r1 == null || r2 == null) { // 有一个为空,一个不为空
            return false;
        }
        if (r1.val != r2.val) { // 两个不为空,但是值不相同
            return false;
        }
        return isSameRec(r1.left, r2.left) && isSameRec(r1.right, r2.right); // 递归遍历左右子节点
    }

    非递归解法:利用Stack对两棵树对应位置上的节点进行判断是否相同。

    public static boolean isSame(TreeNode r1, TreeNode r2){
        if (r1 == null && r2 == null) { // 都是空
            return true;
        } else if (r1 == null || r2 == null) { // 有一个为空,一个不为空
            return false;
        }
        Stack<TreeNode> stack1 = new Stack<>();
        Stack<TreeNode> stack2 = new Stack<>();
        stack1.add(r1);
        stack2.add(r2);
        while (!stack1.isEmpty() && !stack2.isEmpty()) {
            TreeNode temp1 = stack1.pop();
            TreeNode temp2 = stack2.pop();
            if (temp1 == null && temp2 == null) { // 两个元素都为空,因为添加的时候没有对空节点做判断
                continue;
            } else if (temp1 != null && temp2 != null && temp1.val == temp2.val) {
                stack1.push(temp1.left); // 相等则添加左右子节点判断
                stack1.push(temp1.right);
                stack2.push(temp2.left);
                stack2.push(temp2.right);
            } else {
                return false;
            }
        }
        return true;
    }

    判断二叉树是不是平衡二叉树

    递归实现:借助前面实现好的求二叉树高度的函数

    • 如果二叉树为空, 返回真
    • 如果二叉树不为空,如果左子树和右子树都是AVL树并且左子树和右子树高度相差不大于1,返回真,其他返回假
    public static boolean isAVLTree(TreeNode root) {
        if (root == null) {
            return true;
        }
        if (Math.abs(getDepth(root.left) - getDepth(root.right)) > 1) { // 左右子树高度差大于1
            return false;
        }
        return isAVLTree(root.left) && isAVLTree(root.right); // 递归判断左右子树
    }

    求二叉树的镜像

    递归实现:破坏原来的树,把原来的树改成其镜像

    • 如果二叉树为空,返回空
    • 如果二叉树不为空,求左子树和右子树的镜像,然后交换左右子树
    public static TreeNode mirrorRec(TreeNode root) {
        if (root == null) {
            return root;
        }
        TreeNode left = mirrorRec(root.right); // 递归镜像左右子树
        TreeNode right = mirrorRec(root.left);
        root.left = left; // 更新根节点的左右子树为镜像后的树
        root.right = right;
        return root;
    }

    递归实现:不能破坏原来的树,返回一个新的镜像树

    • 如果二叉树为空,返回空
    • 如果二叉树不为空,求左子树和右子树的镜像,然后交换左右子树
    public static TreeNode mirrorCopyRec(TreeNode root) {
        if (root == null) {
            return root;
        }
        TreeNode newRoot = new TreeNode(root.val); // 创建新节点,然后交换左右子树
        newRoot.left = mirrorCopyRec(root.right);
        newRoot.right = mirrorCopyRec(root.left);
        return newRoot;
    }

    判断两个二叉树是否互相镜像

    递归解法:与比较两棵二叉树是否相同解法一致(题5),非递归解法省略。

    • 比较r1的左子树的镜像是不是r2的右子树
    • 比较r1的右子树的镜像是不是r2的左子树
    public static boolean isMirrorRec(TreeNode r1, TreeNode r2) {
        if (r1 == null && r2 == null) {
            return true;
        } else if (r1 == null || r2 == null) {
            return false;
        }
        if (r1.val != r2.val) {
            return false;
        }
        // 递归比较r1的左子树的镜像是不是r2右子树
        // 和r1的右子树的镜像是不是r2的左子树
        return isMirrorRec(r1.left, r2.right) && isMirrorRec(r1.right, r2.left);
    }

    判断是否为二分查找树BST

    题目参考LeetCode(98)

    递归解法:中序遍历的结果应该是递增的

    public static boolean isValidBST(TreeNode root, int pre){
        if (root == null) {
            return true;
        }
        boolean left = isValidBST(root.left, pre);
        if (!left) {
            return false;
        }
        if(root.val <= pre) {
            return false;
        }
        pre = root.val;
        boolean right = isValidBST(root.right, pre);
        if(!right) {
            return false;
        }
        return true;
    }

     

    展开全文
  • 有C源码和VB调用DLL的源码 CPU:T6670 2.20GHZ 内存:2G 系统:WIN7 用VB调用DEV c++编译器编译的C编写二叉树排序DLL,10万个数排序只需要0.12秒,100万个数排序只需要2.49秒
  • 此为用vs2005编写的数据结构实习之二叉树经典算法,适合新手阅读使用
  • javascript算法(二叉树算法

    千次阅读 2018-02-08 18:22:12
    前景:js多应用于前端页面的一些交互,但是现在也用js实现服务器上的开发,甚至强于java或者是c++,吸取了前面技术的优点。 另外,js现在也用于移动端的开发,并且能够很好的兼容IOS和...二、排序二叉树算法的重要性...
  • 编写算法判别给定二叉树是否为完全二叉树,用递归实现
  • 二叉树算法总结

    千次阅读 2012-05-16 10:23:12
    三、二叉树 目录: 1.二叉树三种周游(traversal)方式: 2.怎样从顶部开始逐层打印二叉树结点数据 3.如何判断一棵二叉树是否是平衡二叉树 ...7.怎样编写一个程序,把一个有序整数数组放到二叉
  • 编写递归算法,计算二叉树中叶子结点的数目
  • (4):二叉树链表存储,编写算法,输出先序遍历中,第k个结点的值。(k不大于总结点数,data为char型) 分析:添加判断代码,确定指针p第一次经过该节点时的操作 代码: int ncount = 0; //定义全局变量...
  • 例题:设二叉树的存储结构为二叉链表,编写有关二叉树的递归算法 如有谬误或者不足还请批评指正! (1)统计二叉树中度为0、1、2的结点个数 int num_0 = 0, num_1 = 0, num_2 = 0; void CountNode(BiTree T) { if ...
  • 编写复制一棵二叉树的非递归算法编写复制一棵二叉树的非递归算法编写复制一棵二叉树的非递归算法编写复制一棵二叉树的非递归算法编写复制一棵二叉树的非递归算法编写复制一棵二叉树的非递归算法编写复制一棵二叉树的...
  • 文件名称:第十一周项目1 - 二叉树算法验证.cpp 作 者:滕健 完成日期:2016年11月10日 问题描述: 运行并重复测试教学内容中涉及的算法。改变测试数据进行重复测试的意义在于, 可以从更多角度体会算法,以达到...
  • 问题及代码: /* ...* All rights reserved....* 文件名称:1.cpp * 作 者:王修文 * 完成日期:2016年11月9日 ...*问题描述:实现二叉树二叉树构造算法的验证,并测试数据 *输入描述:无 *程序
  • 很多很好 很强大 二叉树算法 很经典的爱好错哦iaoiahv欧安会 搜狐偶的是红哦idsoishd哦ihsdhdshiodhsidshv撒vpjabiajvea颇具iehvoij
  • 编写按层次遍历二叉树算法

    千次阅读 2013-06-16 10:43:22
    原题:编写按层次遍历二叉树算法.(分析:显然这种问题适合用队列实现) #include #include #define ElemType char #define NodeNum 5 using namespace std; //二叉树的双链表存储结构 typedef struct BiTNode { ...
  • Python编写二叉树遍历

    2020-01-30 22:25:28
    二叉树 树的特征和定义   树是一种重要的非线性数据结构,直观来看,它是数据元素(在树中称为结点)按分支关系组织起来的结构,很像自然界中的树那样,树结构在客观世界中广泛存在,如人类社会的族谱和各种社会组织...
  • 文件名称:第十一周项目1 - 二叉树算法验证(2).cpp 作 者:刘春彤 完成日期:2016年11月7日 版 本 号:v1.0 问题描述: 运行并重复测试教学内容中涉及的算法。改变测试数据进行重复测试的意义在于, 可以从
  • 文件名称:二叉树算法验证.cpp 作 者:彭友程 完成日期:2016年11月10日 版 本 号:v1.0 问题描述: 运行并重复测试教学内容中涉及的算法。改变测试数据进行重复测试的意义在于, 可以从更多角度体会算法,以...
  • 用C语言编写二叉树

    2012-10-19 14:48:34
    二叉树的建立和递归遍历、非递归遍历算法根据前序遍历的顺序建立一棵二叉树,并根据遍历规则遍历二叉树
  • 用汇编语言编写二叉树的建立及其前序、中序、后序遍历 递归算法
  • 二叉树和二叉搜索树介绍 二叉树中的节点最多只能有2个子节点,一个是左侧子节点,一个是右侧子节点,这样定义的好处是有利于我们写出更高效的插入,查找,删除节点的算法。 二叉搜索树是二叉树的一种,但是它只允许...
  • 编写递归算法,计算二叉树中叶子结点的数目 //算法思想:后序遍历 先求左右子树的叶子结点,再加上根结点的情况 #include<iostream> #include<stack> using namespace std; #define TElemType double ...
  • 实现二叉树的层次遍历算法,并对用”A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))”创建的二叉树进行测试。  /* *COPYRIGTH (c) 2017, YTU CS *All rigth reserve *作者:王铭泽 *完成日期:2017.10.19 *版本号:v...
  • 判断正则二叉树算法

    2011-02-24 19:58:00
    STATUS normaltree(Bitree *bt){if(!bt)return TRUE;if(bt->lchild&&bt->rchild){if(normaltree(bt->lchild))if(normaltree(bt->rchild))return TRUE;return FALSE;}elseif((bt->...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 25,892
精华内容 10,356
关键字:

编写二叉树算法