精华内容
下载资源
问答
  • 给出中序遍历 +先序遍历/后序遍历 输出整个树的层次遍历左到右的结果: #include<iostream> #include<cstring> #include<cstdio> #include<queue> using namespace std...

    二叉树遍历:

    先序遍历:根左右

    中序遍历:左根右

    后序遍历:左右根

     

     

     给出中序遍历 +先序遍历/后序遍历     输出整个树的层次遍历左到右的结果:

    #include<iostream>
    #include<cstring>
    #include<cstdio>
    #include<queue>
    using namespace std;
    int le[55],ri[55];//前序 中序
    int lef[55],rig[55];//中序 后序
    int pre[55],in[55],la[55];//前序 中序 后序
    int ans[55];
    int p,post;
    int dfs(int l,int r){
    	if(l>r) return -1;
    	int t=pre[p];
    	p++;
    	int cnt=0;
    	for(int i=l;i<=r;i++){
    		if(t==in[i]){
    			cnt=i;
    			break;
    		}
    	}
    	le[t]=dfs(l,cnt-1);
    	ri[t]=dfs(cnt+1,r);
    	return t; 
    }
     
    int dfs1(int l,int r){
    	if(l>r) return -1;
    	int t=la[post];
    	post--;
    	int cnt=0;
    	for(int i=l;i<=r;i++){
    		if(t==in[i]){
    			cnt=i;
    			break;
    		}
    	}
    	rig[t]=dfs1(cnt+1,r);
    	lef[t]=dfs1(l,cnt-1);
    	return t;
    }
    int main(){
    	int n;
    	cin>>n;
    	for(int i=0;i<n;i++) cin>>pre[i];//先序 
    	for(int i=0;i<n;i++) cin>>in[i];//中序 
    	for(int i=0;i<n;i++) cin>>la[i];//后序 
    	p=0;post=n-1;
    	int cnt=0;
    	//前序 中序
    	int root=dfs(0,n-1);
    	queue<int> q;
    	q.push(root);
    	while(!q.empty()){
    		int u=q.front();q.pop();
    		if(u==-1) continue;
    		ans[cnt++]=u;
    		q.push(le[u]);
    		q.push(ri[u]); 
    	}
    	cout<<ans[0];
    	for(int i=1;i<cnt;i++) cout<<" "<<ans[i];
    	cout<<endl;
    	
    	//中序 后序
    	cnt=0;
    	root=dfs1(0,n-1);
    	q.push(root);
    	while(!q.empty()){
    		int u=q.front();q.pop();
    		if(u==-1) continue;
    		ans[cnt++]=u;
    		q.push(lef[u]);
    		q.push(rig[u]); 
    	}
    	cout<<ans[0];
    	for(int i=1;i<cnt;i++) cout<<" "<<ans[i];
    	cout<<endl;
    	return 0; 
    }
    /*
    8
    1 2 4 5 3 6 7 8
    4 2 5 1 6 3 7 8
    4 5 2 6 8 7 3 1
    11
    1 2 4 8 5 9 3 6 10 11 7
    4 8 2 5 9 1 10 6 11 3 7
    8 4 9 5 2 10 11 6 7 3 1 
    */

     

    展开全文
  • 在这里,主要贴一下树的先序遍历、后续遍历以及广度优先遍历。 TreeNode<T>是定义树的节点的接口,包含以下行为: 1、获取子节点列表 2、获取真正的类型 其中T为泛型,传入的应该是...

    树的遍历分为深度优先遍历和广度优先遍历。在二叉树中,深度优先遍历分为先序遍历、中序遍历和后续遍历;而在树中,因为子节点右多个,因此中序 遍历没有参考性,所以只有先序遍历和后序遍历。

    在这里,主要贴一下树的先序遍历、后续遍历以及广度优先遍历。

    TreeNode<T>是定义树的节点的接口,包含以下行为:

    1、获取子节点列表

    2、获取真正的类型

    其中T为泛型,传入的应该是节点的真正的实现类,为了通过getValue后返回实现类方便后续调用实现类的私有实现;

    package com.keronimbus.generic;
    
    
    import java.io.Serializable;
    import java.util.List;
    
    public interface TreeNode<T> extends Serializable {
    
        List<TreeNode<T>> getChildren();
    
        T getValue();
    
    }

    TreeVisitor<T>是三种遍历的实现,返回的结果是包含访问顺序的List

    package com.keronimbus.generic;
    
    import java.util.*;
    
    public class TreeVisitor<T> {
    
        /**
         * 先序遍历
         * @param root 树的根节点
         * @return
         */
        public List<T> preOrderTraversal(TreeNode<T> root){
            Stack<TreeNode<T>> stack = new Stack<>();
            if(root == null){
                return null;
            }
            Map<TreeNode<T>, Iterator<TreeNode<T>>> iteratorMap = new HashMap<>();
            Map<TreeNode<T>, Boolean> visitedFlag = new HashMap<>();
            stack.push(root);
            TreeNode<T> cursor = null;
            List<T> traversalOrder = new ArrayList<>();
            while(!stack.empty()){
                cursor = stack.pop();
                if (visitedFlag.get(cursor) == null) {
                    visitedFlag.put(cursor,Boolean.TRUE);
                    traversalOrder.add(cursor.getValue());
                }
                List<TreeNode<T>> childrenList = cursor.getChildren();
                if(childrenList== null || childrenList.size()<=0){
                    continue;
                }
                Iterator<TreeNode<T>> childIterator = iteratorMap.get(cursor);
                if(childIterator == null){
                    childIterator = childrenList.iterator();
                    iteratorMap.put(cursor, childIterator);
                }
                if(childIterator.hasNext()){
                    TreeNode<T> child = childIterator.next();
                    stack.push(cursor);
                    stack.push(child);
                }
    
            }
            return traversalOrder;
    
        }
    
        /**
         * 后序遍历
         * @param root 树的根节点
         * @return
         */
        public List<T> postOrderTraversal(TreeNode<T> root){
            Stack<TreeNode<T>> stack = new Stack<>();
            if(root == null){
                return null;
            }
            Map<TreeNode<T>, Iterator<TreeNode<T>>> iteratorMap = new HashMap<>();
            Map<TreeNode<T>, Boolean> visitedFlag = new HashMap<>();
            stack.push(root);
            TreeNode<T> cursor = null;
            List<T> traversalOrder = new ArrayList<>();
            while(!stack.empty()){
                cursor = stack.pop();
                List<TreeNode<T>> childrenList = cursor.getChildren();
                if(childrenList== null || childrenList.size()<=0){
                    traversalOrder.add(cursor.getValue());
                    continue;
                }
                Iterator<TreeNode<T>> childIterator = iteratorMap.get(cursor);
                if(childIterator == null){
                    childIterator = childrenList.iterator();
                    iteratorMap.put(cursor, childIterator);
                }
                if(childIterator.hasNext()){
                    TreeNode<T> child = childIterator.next();
                    stack.push(cursor);
                    stack.push(child);
                }else{
                    traversalOrder.add(cursor.getValue());
                }
    
    
            }
            return traversalOrder;
    
        }
    
        /**
         * 广度优先遍历
         * @param root 树的根节点
         * @return
         */
        public List<T> breadFirstTraversal(TreeNode<T> root){
            if(root == null){
                return null;
            }
            Queue<TreeNode<T>> queue = new ArrayDeque<>();
            queue.add(root);
            List<T> traversalOrder = new ArrayList<>();
            while(queue.size()>0){
                TreeNode<T> cursor = queue.poll();
                traversalOrder.add(cursor.getValue());
                List<TreeNode<T>> children = cursor.getChildren();
                if(children!= null && children.size()>0){
                    queue.addAll(children);
                }
            }
            return traversalOrder;
        }
    }

    在使用的时候,节点的需要实现TreeNode<T>接口,并且指定实现类的类型

    public static void main(String[] args){
           Department department1 = new Department(1,"1-1",1);
            Department department2 = new Department(2,"2-1",2);
            Department department3 = new Department(3,"3-1",3);
            Department department4 = new Department(4,"2-2",2);
            List<TreeNode<Department>> childrenList1= new ArrayList<>();
            childrenList1.add(department2);
            childrenList1.add(department4);
    
            List<TreeNode<Department>> childrenList2 = new ArrayList<>();
            childrenList2.add(department3);
    
            department1.setChildren(childrenList1);
            department2.setChildren(childrenList2);
            TreeVisitor<Department> visitor = new TreeVisitor<>();
            List<Department> preOrder = visitor.preOrderTraversal(department1);
            preOrder.forEach(item->System.out.println(item));
            System.out.println("--------------------");
            List<Department> postOrder = visitor.postOrderTraversal(department1);
            postOrder.forEach(item->System.out.println(item));
            System.out.println("--------------------");
            List<Department> breadFirstOrder = visitor.breadFirstTraversal(department1);
            breadFirstOrder.forEach(item->System.out.println(item));
    
        }

    结果:

    树的真实结构:

        1-1

       2-1       2-2

    3-1

     

    这种实现本身是为了不希望调用方在使用的时候用对象本身重新包装一个TreeNode,但是这种实现看来并没有很优雅,目前没有想到更好的实现办法。

    顺便一说,不知道Java中为什么没有树结构。

     

    转载于:https://www.cnblogs.com/less-is-more-record/p/10093746.html

    展开全文
  • 五次树的先序遍历和后序遍历,其他高次树的遍历只需改下孩子结点个数即可。 完整代码如下 #include &lt;stdio.h&gt; #include &lt;stdlib.h&gt; #define maxchild 5 typedef int DataType; struct ...

    五次树的先序遍历和后序遍历,其他高次树的遍历只需改下孩子结点个数即可。

    完整代码如下

    #include <stdio.h>
    #include <stdlib.h>
    #define maxchild 5
    typedef int DataType;
    struct treenode{
        DataType data;
        struct treenode *childs[maxchild];
    };
    typedef struct treenode *Tree,TreeNode;
    void init(TreeNode *node,DataType x);
    void PostTraverse(Tree T,int n);
    void PreTraverse(Tree T,int n);
    
    int main()
    {
        Tree T;
        TreeNode a,b,c,d,e;
        T = (TreeNode*)malloc(sizeof(TreeNode));
        T->data = 10;
        init(&a,11);
        init(&b,12);
        init(&c,13);
        init(&d,14);
        init(&e,15);
        T->childs[1] = &b;
        T->childs[2] = &c;
        T->childs[3] = &d;
        T->childs[4] = &e;
        T->childs[0] = &a;
    
        PostTraverse(T,5);
        printf("\n");
        PreTraverse(T,5);
        return 0;
    }
    
    void init(TreeNode *node,DataType x)
    {/*初始化一个结点*/
        node->data = x;
        for(int i = 0; i < maxchild;i++)
            node->childs[i] = NULL;
    }
    /*五次树后续遍历*/
    void PostTraverse(Tree T,int n)
    {
        int i;
        if(T == NULL)
            return;
        for(i = 0;i < n;i++)
            PostTraverse(T->childs[i],n);
        printf("%6d",T->data);
    }
    
    /*五次树先序遍历*/
    void PreTraverse(Tree T,int n)
    {
        int i;
        if(T == NULL)
            return;
        printf("%6d",T->data);
        for(i = 0;i < n;i++)
            PreTraverse(T->childs[i],n);
    }
    
    展开全文
  • 二叉树(递归实现先序遍历,中序遍历,后序遍历,非递归实现先序遍历,中序遍历,后序遍历,二叉树层序遍历,二叉树结点个数,二叉树叶子结点个数,判断一颗是否为完全二叉树) 1.构造二叉树:通过前序遍历数组eg:"ABD##E#H#...

    二叉树(递归实现先序遍历,中序遍历,后序遍历,非递归实现先序遍历,中序遍历,后序遍历,二叉树层序遍历,二叉树结点个数,二叉树叶子结点个数,判断一颗树是否为完全二叉树)
    1.构造二叉树:通过前序遍历的数组eg:"ABD##E#H##CF##G##"构建二叉树;
    2.递归实现二叉树的前中后序遍历;
    3.非递归实现二叉树的前中后序遍历;
    4.后序遍历销毁二叉树;
    5.层序遍历:借助队列实现;
    6.判断一颗二叉树是否为完全二叉树:有右没左,或有孩子且标记为1;
    7.二叉树结点个数的计数通过遍历实现;
    8.叶子结点的个数通过判断该结点的类型实现.
    BinaryTree.h

    #ifndef _BINARYTREE_H_
    #define _BINARYTREE_H_
    
    #define _CRT_SECURE_NO_WARNINGS
    
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #include <assert.h>
    
    typedef char BTDataType;
    
    typedef struct BinaryTreeNode
    {
    	BTDataType _data;
    	struct BinaryTreeNode* _left;
    	struct BinaryTreeNode* _right;
    }BTNode;
    
    // 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
    BTNode* BinaryTreeCreate(BTDataType* src);
    // 递归遍历
    void BinaryTreePrevOrder(BTNode* root);//先序遍历
    void BinaryTreeInOrder(BTNode* root);//中序遍历
    void BinaryTreePostOrder(BTNode* root);//后序遍历
    void BinaryTreeLevelOrder(BTNode* root);// 层序遍历
    void BinaryTreeDestory(BTNode** root);//销毁二叉树
    // 非递归遍历
    void BinaryTreePrevOrderNonR(BTNode* root);//先序遍历
    void BinaryTreeInOrderNonR(BTNode* root);//中序遍历
    void BinaryTreePostOrderNonR(BTNode* root);//后序遍历
    //递归实现
    int BinaryTreeLeafSize(BTNode* root);二叉树叶子结点个数
    int BinaryTreeLevelKSize(BTNode* root, int k);第K层结点个数
    //非递归实现
    int BinaryTreeSizeNonR(BTNode* root);二叉树结点个数
    int BinaryTreeLeafSizeNonR(BTNode* root);//二叉树叶子结点个数
    int BinaryTreeLevelKSizeNonR(BTNode* root, int k);//第K层结点个数
    int BinaryTreeComplete(BTNode* root);// 判断二叉树是否是完全二叉树
    #endif // !_BINARYTREE_H_
    
    

    Queue.h

    #ifndef _QUEUE_H_
    #define _QUEUE_H_
    #include "BinaryTree.h"
    
    typedef BTNode * QueueDataType;
    
    typedef struct QueueNode
    {
    	QueueDataType _data;
    	struct QueueNode* _next;
    }QueueNode;
    
    typedef struct Queue {
    	QueueNode * _head;
    	QueueNode * _real;
    }Queue;
    
    void QueueInit(Queue* plist);
    void QueueDestory(Queue* plist);
    void QueuePop(Queue* plist);
    void QueuePush(Queue* plist, QueueDataType x);
    QueueDataType QueueTop(Queue* plist);
    int QueueEmpty(Queue* plist);
    int QueueSize(Queue* plist);
    
    #endif //_QUEUE_H_
    

    Stack.h

    #ifndef _Stack_H_
    #define _Stack_H_
    
    
    #define _CRT_SECURE_NO_WARNINGS
    
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #include <assert.h>
    #include "BinaryTree.h"
    
    typedef BTNode* StDataType;
    
    typedef struct Stack
    {
    	StDataType* array; // 指向动态开辟的数组
    	size_t size; // 有效数据个数
    	size_t capicity; // 容量空间的大小
    }Stack;
    
    void StackInit(Stack* psl, size_t capacity);
    void StackDestory(Stack* psl);
    void CheckCapacity(Stack* psl);
    void StackPush(Stack* psl, StDataType x);
    void StackPop(Stack* psl);
    StDataType StackTop(Stack* psl);
    int StackEmpty(Stack* psl);
    
    #endif // _Stack_H_
    
    

    Binarytree.c

    #include "BinaryTree.h"
    #include "Queue.h"
    #include "Stack.h"
    
    // 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
    BTNode* BinaryTreeCreate(BTDataType* src) {
    	static int s_n = 0;
    	if (src[s_n] == '#') {
    		s_n++;
    		return NULL;
    	}
    	BTNode* cur = (BTNode*)malloc(sizeof(BTNode));
    	cur->_data = src[s_n];
    	s_n++;
    	cur->_left = BinaryTreeCreate(src);
    	cur->_right = BinaryTreeCreate(src);
    	return cur;
    }
    
    //递归遍历
    //前序遍历(递归)
    void BinaryTreePrevOrder(BTNode* root) {
    	//assert(root);
    	if (root) {
    		putchar(root->_data);
    		BinaryTreePrevOrder(root->_left);
    		BinaryTreePrevOrder(root->_right);
    	}
    }
    
    //中序遍历(递归)
    void BinaryTreeInOrder(BTNode* root) {
    	//assert(root);
    	if (root) {
    		BinaryTreeInOrder(root->_left);
    		putchar(root->_data);
    		BinaryTreeInOrder(root->_right);
    	}
    }
    
    //后序遍历(递归)
    void BinaryTreePostOrder(BTNode* root) {
    	//assert(root);
    	if (root) {
    		BinaryTreePostOrder(root->_left);
    		BinaryTreePostOrder(root->_right);
    		putchar(root->_data);
    	}
    }
    
    //层序遍历(队列实现)
    void BinaryTreeLevelOrder(BTNode* root) {
    	BTNode* cur;
    	Queue qu;
    	QueueInit(&qu);
    	QueuePush(&qu, root);
    	while (!QueueEmpty(&qu)) {
    		cur = QueueTop(&qu);
    		putchar(cur->_data);
    		if (cur->_left) {
    			QueuePush(&qu, cur->_left);
    		}
    		if (cur->_right) {
    			QueuePush(&qu, cur->_right);
    		}
    		QueuePop(&qu);
    	}
    	QueueDestory(&qu);
    }
    
    //销毁二叉树
    void BinaryTreeDestory(BTNode** root) {
    	assert(root);
    	if (root) {
    		BinaryTreePostOrder((*root)->_left);
    		BinaryTreePostOrder((*root)->_right);
    		free(*root);
    		*root = NULL;
    	}
    }
    
    //非递归遍历(均用栈实现)
    //前序遍历(非递归)
    void BinaryTreePrevOrderNonR(BTNode* root) {
    	assert(root);
    	BTNode* cur = root;
    	Stack st;
    	StackInit(&st, 100);
    	while (cur)	{
    		putchar(cur->_data);
    		if (cur->_right) {
    			StackPush(&st, cur->_right);
    		}
    		if (cur->_left) {
    			cur = cur->_left;
    		}
    		else {
    			cur = StackTop(&st);
    			StackPop(&st);
    		}
    	}
    	StackDestory(&st);
    }
    
    //中序遍历(非递归)
    void BinaryTreeInOrderNonR(BTNode* root) {
    	assert(root);
    	BTNode* cur = root;
    	Stack st;
    	StackInit(&st, 100);
    	while (!StackEmpty(&st) || cur) {
    		for (; cur; cur = cur->_left) {
    			StackPush(&st, cur);
    		}
    		cur = StackTop(&st);
    		putchar(cur->_data);
    		StackPop(&st);
    		cur = cur->_right;
    	}
    	StackDestory(&st);
    }
    
    //后序遍历(非递归)
    void BinaryTreePostOrderNonR(BTNode* root) {
    	assert(root);
    	BTNode* cur = root;
    	Stack st;
    	char tag[100];
    	StackInit(&st, 100);
    	do {
    		for (; cur; cur = cur->_left) {
    			StackPush(&st, cur);
    			tag[st.size - 1] = 0;
    		}
    		while (!StackEmpty(&st) && tag[st.size - 1]) {
    			cur = StackTop(&st);
    			putchar(cur->_data);
    			StackPop(&st);
    		}
    		if (!StackEmpty(&st)) {
    			cur = StackTop(&st);
    			tag[st.size - 1] = 1;
    			cur = cur->_right;
    		}
    	} while (!StackEmpty(&st));
    	StackDestory(&st);
    }
    
    //递归实现
    //二叉树叶子结点个数
    int BinaryTreeLeafSize(BTNode* root) {
    	if (root == NULL) {
    		return 0;
    	}
    	else if ((root->_left == NULL) && (root->_right == NULL)) {
    		return 1;
    	}
    	else {
    		return BinaryTreeLeafSize(root->_left) + BinaryTreeLeafSize(root->_right);
    	}
    }
    
    //第K层结点个数
    int BinaryTreeLevelKSize(BTNode* root, int k) {
    	if (root == NULL || k <= 0) {
    		return 0;
    	}
    	else if (root&&k == 1) {
    		return 1;
    	}
    	else {
    		return BinaryTreeLevelKSize(root->_left, k - 1) + BinaryTreeLevelKSize(root->_right, k - 1);
    	}
    }
    
    //非递归实现
    //二叉树结点个数
    int BinaryTreeSizeNonR(BTNode* root) {
    	assert(root);
    	int count = 0;
    	BTNode* cur = root;
    	Stack st;
    	StackInit(&st, 100);
    	while (cur)	{
    		count++;
    		//putchar(cur->_data);
    		if (cur->_right) {
    			StackPush(&st, cur->_right);
    		}
    		if (cur->_left) {
    			cur = cur->_left;
    		}
    		else {
    			cur = StackTop(&st);
    			StackPop(&st);
    		}
    	}
    	StackDestory(&st);
    	return count;
    }
    
    //二叉树叶子结点个数
    int BinaryTreeLeafSizeNonR(BTNode* root) {
    	assert(root);
    	int count = 0;
    	BTNode* cur = root;
    	Stack st;
    	StackInit(&st, 100);
    	while (cur)	{
    		if (cur->_left == NULL && cur->_right == NULL) {
    			count++;
    		}
    		//putchar(cur->_data);
    		if (cur->_right) {
    			StackPush(&st, cur->_right);
    		}
    		if (cur->_left) {
    			cur = cur->_left;
    		}
    		else {
    			cur = StackTop(&st);
    			StackPop(&st);
    		}
    	}
    	StackDestory(&st);
    	return count;
    }
    
    //第K层结点个数
    int BinaryTreeLevelKSizeNonR(BTNode* root, int k) {
    	if (root == NULL || k <= 0) {
    		return 0;
    	}
    	int cur_level_size = 0;
    	int cur_level = 0;
    	Queue qu;
    	QueueInit(&qu);
    	QueuePush(&qu,root);
    	while (!QueueEmpty(&qu)) {
    		cur_level++;
    		cur_level_size = QueueSize(&qu);
    		if (cur_level == k) {
    			break;
    		}
    		int tmp_count = 0;
    		while (tmp_count < cur_level_size) {
    			tmp_count++;
    			root = QueueTop(&qu);
    			QueuePop(&qu);
    			if (root->_left) {
    				QueuePush(&qu, root->_left);
    			}
    			if (root->_right) {
    				QueuePush(&qu, root->_right);
    			}
    		}
    	}
    	QueueDestory(&qu);
    	if (cur_level == k) {
    		return cur_level_size;
    	}
    }
    
    // 判断二叉树是否是完全二叉树
    int BinaryTreeComplete(BTNode* root) {
    	int tag = 0;
    	BTNode* cur;
    	Queue qu;
    	QueueInit(&qu);
    	QueuePush(&qu, root);
    	while (!QueueEmpty(&qu)) {
    		cur = QueueTop(&qu);
    		putchar(cur->_data);
    		if (root->_right&&root->_left == NULL) {
    			return 0;
    		}
    		if (tag && (root->_left || root->_right)) {
    			return 0;
    		}
    		if (cur->_left) {
    			QueuePush(&qu, cur->_left);
    		}
    		if (cur->_right) {
    			QueuePush(&qu, cur->_right);
    		}
    		else {
    			tag = 1;
    		}
    		QueuePop(&qu);
    	}
    	QueueDestory(&qu);
    	return 1;
    }
    

    Queue.c

    #include "Queue.h"
    
    #include <stdio.h>
    #include <stdlib.h>
    #include <assert.h>
    
    void QueueInit(Queue* plist) {
    	assert(plist);
    	plist->_head = NULL;
    	plist->_real = NULL;
    }
    
    void QueueDestory(Queue* plist)
    {
    	assert(plist);
    	QueueNode * tmp;
    	while (plist->_head) {
    		tmp = plist->_head;
    		plist->_head = plist->_head->_next;
    		free(tmp);
    	}
    }
    
    void QueuePop(Queue* plist)
    {
    	assert(plist);
    	QueueNode * tmp;
    	if (plist->_head) {
    		tmp = plist->_head;
    		plist->_head = plist->_head->_next;
    		free(tmp);
    	}
    }
    
    void QueuePush(Queue* plist, QueueDataType x) {
    	assert(plist);
    	QueueNode * cur = (QueueNode *)malloc(sizeof(QueueNode));
    	cur->_data = x;
    	cur->_next = NULL;
    	if (QueueEmpty(plist)) {
    		plist->_head = plist->_real = cur;
    		return;
    	}
    	plist->_real->_next = cur;
    	plist->_real = cur;
    }
    
    int QueueEmpty(Queue* plist) {
    	assert(plist);
    	return plist->_head == NULL;
    }
    
    QueueDataType QueueTop(Queue* plist) {
    	assert(plist);
    	if (QueueEmpty(plist)) {
    		return (QueueDataType)0;
    	}
    	return plist->_head->_data;
    }
    
    //队列长度
    int QueueSize(Queue* plist) {
    	assert(plist);
    	if (plist == NULL) {
    		return 0;
    	}
    	int count = 0;
    	QueueNode* cur;
    	for (cur = plist->_head; cur; cur = cur->_next) {
    		count++;
    	}
    	return count;
    }
    

    Stack.c

    #include "Stack.h"
    
    //初始栈
    void StackInit(Stack* psl, size_t capacity) {
    	assert(psl);
    	psl->capicity = capacity;
    	psl->array = (StDataType*)malloc(capacity*sizeof(StDataType));
    	assert(psl->array);
    	psl->size = 0;
    }
    
    //销毁栈
    void StackDestory(Stack* psl) {
    	assert(psl);
    	if (psl->array) {
    		free(psl->array);
    		psl->capicity = 0;
    		psl->size = 0;
    		psl->array = NULL;
    	}
    }
    
    //扩容栈
    void CheckCapacity(Stack* psl) {
    	assert(psl);
    	if (psl->size == psl->capicity) {
    		psl->capicity *= 2;
    		psl->array = (StDataType*)realloc(psl->size, psl->capicity*sizeof(StDataType));
    	}
    }
    
    //入栈
    void StackPush(Stack* psl, StDataType x) {
    	assert(psl);
    	CheckCapacity(psl);
    	psl->array[psl->size] = x;
    	psl->size++;
    }
    
    //出栈
    void StackPop(Stack* psl) {
    	assert(psl || psl->size);
    	psl->size--;
    }
    
    //返回栈顶元素
    StDataType StackTop(Stack* psl) {
    	assert(psl);
    	if (StackEmpty(psl)) {
    		return (StDataType)0;
    	}
    	return psl->array[psl->size - 1];
    }
    
    //判空
    int StackEmpty(Stack* psl) {
    	assert(psl);
    	return psl->size == 0;
    }
    
    

    main.c

    #include "BinaryTree.h"
    #include "Queue.h"
    #include "Stack.h"
    
    int main() {
    	int count;
    	Queue que;
    	//ABD##E#H##CF##G##
    	//ABD#GI##J###CE#HK###F##
    	BTNode* root = BinaryTreeCreate("ABD#GI##J###CE#HK###F##");
    	BinaryTreePrevOrder(root);
    	putchar('\n');
    	BinaryTreeInOrder(root);
    	putchar('\n');
    	BinaryTreePostOrder(root);
    	putchar('\n');
    	BinaryTreeLevelOrder(root);
    	putchar('\n');
    	BinaryTreePrevOrderNonR(root);
    	putchar('\n');
    	BinaryTreeInOrderNonR(root);
    	putchar('\n');
    	BinaryTreePostOrderNonR(root);
    	putchar('\n');
    	//printf("%d\n", BinaryTreeSize(root));
    	printf("%d\n", BinaryTreeLeafSize(root));
    	printf("%d\n", BinaryTreeSizeNonR(root));
    	printf("%d\n", BinaryTreeLeafSizeNonR(root));
    	printf("%d\n", BinaryTreeLevelKSize(root, 1));
    	printf("%d\n", BinaryTreeLevelKSize(root, 2));
    	printf("%d\n", BinaryTreeLevelKSize(root, 3));
    	printf("%d\n", BinaryTreeLevelKSize(root, 4));
    	printf("%d\n", BinaryTreeLevelKSize(root, 5));
    	printf("%d\n", BinaryTreeLevelKSizeNonR(root, 1));
    	printf("%d\n", BinaryTreeLevelKSizeNonR(root, 2));
    	printf("%d\n", BinaryTreeLevelKSizeNonR(root, 3));
    	printf("%d\n", BinaryTreeLevelKSizeNonR(root, 4));
    	printf("%d\n", BinaryTreeLevelKSizeNonR(root, 5));
    	BinaryTreeComplete(root);
    	putchar('\n');
    	system("pause");				   
    	return 0;
    }
    
    
    展开全文
  • 如何根据一棵二叉树的先序遍历和中序遍历得到一个后序遍历? 2.分析 先序遍历:永远最先得到根节点,然后是左子树的节点,然后是右子树的节点。 中序遍历:永远最先得到左子树的节点,然后是根节点,然后是右子树的...
  • void preorder(BTNode *p) //先序遍历 { if(p!=NULL) { cout<<p-data; preorder(p->lchild); preorder(p->rchild); } } void inorder(BTNode *p) //中序遍历 { if(p!=NULL) { inorder(p->...
  • 文章目录先序遍历中序遍历后序遍历层序遍历遍历应用例子 先序遍历 遍历过程为: ① 访问根结点;② 先序遍历其左子树; ③ 先序遍历其右子。 void PreOrderTraversal( BinTree BT ) { if( BT ) { printf(“%d”,...
  • 根据当前先序遍历的第一个元素可以确定该元素是当前树的根结点,从中序遍历中找到该结点,该结点左边是左子树,右边是右子树,递归上述过程,直到当前先序遍历序列长度为0 转化函数代码 static class Node { int ...
  • 这样再去先序遍历中找到左子树根节点,然后再依靠中序遍历找到左子树左子树(右子同理)。这样层层递归就能还原二叉树。之后求出后序遍历。 感谢原博主http://www.cnblogs.com/rain-lei/p/3576796.ht...
  • 先序遍历: 节点 - 左孩子 - 右...后序遍历 : 左孩子 - 右孩子 - 根结点 遍历结果: 先序:GDAFEMHZ 中序:ADEFGHMZ 后序:AEFDHZMG 非递归实现三种遍历: http://www.cnblogs.com/LZYY/p/3454778.html...
  • 先序中序后序遍历

    2016-08-31 14:55:38
    求一棵二叉树的前序遍历,中序遍历和后序遍历 输入描述 Input Description 第一行一个整数n,表示这棵树的节点个数。 接下来n行每行2个整数L和R。第i行的两个整数Li和Ri代表编号为i的节点的左儿子编号和右儿子...
  • } /** * 后序遍历:左右根 * 利用栈模拟递归调用 * 将根结点压入栈中,当栈不空时执行: * 弹出栈中结点,将其头插放入结果队列中 * 将该结点孩子依次放入栈中 * * * 其实后序遍历就是先序遍历逆序列 * 先序...
  • 以前大学学数据结果的时候,我们就知道,根据一棵树的先序遍历和中序遍历,或者后序遍历和中序遍历序列,都可以唯一地确定一棵树。
  • 二叉树的先序遍历,中序遍历和后序遍历一定是先左后右的 先序遍历的根节点在最前面,中序遍历的根节点在中间,后序遍历的根节点在最后 先序遍历 先序遍历二叉树的时候,先遍历根节点,然后遍历左子树,最后遍历右子...
  • 1、有一个二叉查找树,存储者字符'A','B','C','D','E','F','G','H',下面哪个结果是后序遍历结果A. ADBCEGFHB....二叉树的性质:1、左子树的值小于根节点,右子树的值大于根节点我们直接看C答案:...
  • 树的遍历 一、前序遍历 算法思想(递归过程): 访问根结点 先序遍历左子树 先序遍历右子树 //先序遍历的递归调用 void preTravel(BiTree T) { if(T != NULL) { printf("%d", T->data); preTravel(T->...
  • 对访问次数和压栈之间关系思考 一个节点如果只用访问一次,那么在一开始访问时候直接...后序遍历的三次访问: 1.作为当前节点左孩子或者右孩子被访问,因为后序遍历此时不能做任何操作,只能入栈等待以...
  • 前序遍历: (1)访问根节点 (2)先序遍历左子树 ...后序遍历二叉树规则: (1)后序遍历左子树 (2)后序遍历右子 (3)访问根节点 转载于:https://www.cnblogs.com/cccmon/p/9037134.html...
  • 本篇博客介绍二叉树的先序遍历、中序遍历、后序遍历以及层次遍历 先序遍历:根节点---左子树---右子 中序遍历:左子树---根节点---右子 后序遍历:左子树---右子---根节点 层次遍历:每一层按照从左到右...
  • 这里提出用非递归遍历的原因是:用递归遍历虽然方便,但是不能递归太深,否则会 stack overflow先序遍历这里有两种遍历方法void PreOrder1(Btree*b) { stack&lt;node*&gt;s; Btree *p; //...
  • 则X子树的先序遍历和后序遍历类似下图 先序遍历 X L … R … 后序遍历 … L … R X 可以发现我们可以轻松地找出两个儿子从而确定树的形态。 只有一个儿子的话这个儿子既可以是左儿子也可以是右儿子。 只需要...
  • 可能有多组测试数据,对于每组数据,将题目所给数据建立一个二叉排序,并对二叉排序进行前序、中序和后序遍历。 每种遍历结果输出一行。每行最后一个数据之后有一个空格。 输入中可能有重复元素,但是输出...
  • 二叉树链式结构的遍历 所谓遍历(Traversal)是指沿着某条...前序/中序/后序的递归结构遍历:是根据访问结点操作发生位置命名,遍历的路径都相同,只是访问顺序不同。 NLR:前序遍历(Preorder Traversal 亦称...
  • 后序)序列构建唯一二叉,其中贴出一些提供思路博客:二叉树前序中序后序遍历相互求法 但是这篇博客并没有给出(前序&amp;amp;后序)求解方法。事实上,根据前序和后序构建二叉树不唯一,理由是前序...
  • 对于给定的一个二叉树的先序遍历和后序遍历,输出有多少种满足条件的二叉树。 两棵二叉树不同当且仅当对于某个x,x的左儿子编号不同或x的右儿子编号不同。 Input 第一行一个正整数n(3<=n<
  • 0.1)本代码均为原创,旨在将树的遍历应用一下下以加深印象而已;(回答了学习树的遍历到底有什么用的问题?)你对比下linux 中的文件树 和我的打印结果就明理了; 0.2)我们采用的是 儿子兄弟表示法 来 表示树的...
  • 0.1)本代码均为原创,旨在将树的遍历应用一下下以加深印象而已;(回答了学习树的遍历到底有什么用的问题?)你对比下linux 中的文件树 和我的打印结果就明理了; 0.2)哥子第一次 使用着 丑到逼爆 的 编辑器,...
  • 首先得明白什么是二叉树的先序中序后序遍历: c++ 二叉树的创建 前中后序遍历 以及遇到的坑 给出先序和中序遍历重建二叉树: 思路: 1、二叉树的先序遍历的第一个结点是根节点; 2、中序遍历的根节点左边的序列是左...
  • 1,分别写了先序遍历,中序遍历和后序遍历以及层次遍历的非递归算法! [cpp] view plain copy   // 树的建立和遍历.cpp : 定义控制台应用程序的入口点。  //    #include ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 3,835
精华内容 1,534
关键字:

树的先序后序遍历